Delaunay.luau

--[[

Copyright 2024 Cameron Campbell

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

]]

--[[

Copyright 2024 Cameron Campbell

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

]]

--!strict
--!native
--!optimize 2


--> Types ---------------------------------------------------------------------------------------------
type Edge = { Vector3 } -- { Vector3, Vector3 }

type Triangle = { Edge }  -- { Edge, Edge, Edge }
-------------------------------------------------------------------------------------------------------


--> Functions -----------------------------------------------------------------------------------------
---- Circumcircle -------------------------------------------------------------------
local function StandFormLinEq(pointA: Vector3, pointB: Vector3)
	local deltaX = pointB.X - pointA.X
	local deltaZ = pointB.Z - pointA.Z

	local a = deltaZ
	local b = -deltaX
	local c = a * pointA.X + b * pointA.Z

	return a, b, c
end

local function PerpendicularLineAt(a1: number, b1: number, c1: number, point: Vector3)
	local a2 = -b1
	local b2 = a1
	local c2 = a2 * point.X + b2 * point.Z

	return a2, b2, c2
end

local function GetCrossingPoint(a1: number, b1: number, c1: number, a2: number, b2: number, c2: number)
	-- Cramers rule.
	local determinant = a1 * b2 - a2 * b1
	local determinantX = c1 * b2 - c2 * b1
	local determinantZ = a1 * c2 - a2 * c1

	local x, z = determinantX / determinant, determinantZ / determinant

	return Vector3.new(x, 0, z)
end

local function Circumcircle(pointA: Vector3, pointB: Vector3, pointC: Vector3)
	local a1, b1, c1 = StandFormLinEq(pointA, pointB)
	local a2, b2, c2 = StandFormLinEq(pointB, pointC)

	local midPointAB = pointA:Lerp(pointB, .5)
	local midPointBC = pointB:Lerp(pointC, .5)

	local perpAB_a, perpAB_b, perpAB_c = PerpendicularLineAt(a1, b1, c1, midPointAB)
	local perpBC_a, perpBC_b, perpBC_c = PerpendicularLineAt(a2, b2, c2, midPointBC)

	local circumcentre = GetCrossingPoint(perpAB_a, perpAB_b, perpAB_c, perpBC_a, perpBC_b, perpBC_c)
	local circumradius = (circumcentre - pointA).Magnitude

	return circumcentre, circumradius
end
-------------------------------------------------------------------------------------


-- Draw Utils -----------------------------------------------------------------------
local function CreateWedge()
	local wedge = Instance.new("WedgePart");
	wedge.Anchored = true;
	wedge.TopSurface = Enum.SurfaceType.Smooth;
	wedge.BottomSurface = Enum.SurfaceType.Smooth;

	return wedge
end

local function Draw3dTri(a: Vector3, b: Vector3, c: Vector3, color: Color3?, parent: Instance?, w1: WedgePart?, w2: WedgePart?)
	parent = parent or workspace
	local ab, ac, bc = b - a, c - a, c - b;
	local abd, acd, bcd = ab:Dot(ab), ac:Dot(ac), bc:Dot(bc);

	if (abd > acd and abd > bcd) then
		c, a = a, c;
	elseif (acd > bcd and acd > abd) then
		a, b = b, a;
	end

	ab, ac, bc = b - a, c - a, c - b;

	local right = ac:Cross(ab).Unit;
	local up = bc:Cross(right).Unit;
	local back = bc.Unit;

	local height = math.abs(ab:Dot(up));

	w1 = w1 or CreateWedge();
	(w1 :: WedgePart).Size = Vector3.new(0, height, math.abs(ab:Dot(back)));
	(w1 :: WedgePart).CFrame = CFrame.fromMatrix((a + b)/2, right, up, back);

	w2 = w2 or CreateWedge();
	(w2 :: WedgePart).Size = Vector3.new(0, height, math.abs(ac:Dot(back)));
	(w2 :: WedgePart).CFrame = CFrame.fromMatrix((a + c)/2, -right, up, -back);

	if color then
		(w1 :: WedgePart).Color = color;
		(w2 :: WedgePart).Color = color;
	end

	(w1 :: WedgePart).Parent = parent;
	(w2 :: WedgePart).Parent = parent;

	return w1 :: WedgePart, w2 :: WedgePart;
end


local function DrawPoint(point: Vector3, color: Color3?)
	local part = Instance.new("Part")
	part.Size = Vector3.one * 2.5
	part.Shape = Enum.PartType.Ball
	part.Color = color or Color3.new(1, 0, 0)
	part.Position = point
	part.Anchored = true
	part.Parent = workspace
end

local function DrawPoints(points: { Vector3 }, color: Color3?)
	for _,point in points do DrawPoint(point, color) end
end

local function DrawTriangles(triangles: { Triangle })
	for _,tri in triangles do
		Draw3dTri(tri[1][1], tri[2][1], tri[3][1], BrickColor.random().Color)
	end
end
-------------------------------------------------------------------------------------


local function BoundingBox(points: { Vector3 })
	local minX, minZ = points[1].X, points[1].Y
	local maxX, maxZ = points[1].X, points[1].Y

	for i = 2, #points do
		local point = points[i]
		local pointX, pointZ = point.X, point.Z

		if pointX < minX then minX = pointX
		elseif pointX > maxX then maxX = pointX end

		if pointZ < minZ then minZ = pointZ
		elseif pointZ > maxZ then maxZ = pointZ end
	end

	return minX, minZ, maxX, maxZ
end

local function Triangle(vert1: Vector3, vert2: Vector3, vert3: Vector3)
	local edge1 = { vert1, vert2 }
	local edge2 = { vert2, vert3 }
	local edge3 = { vert3, vert1 }
	
	return { edge1, edge2, edge3 }
end

local function SuperTri(points: { Vector3 }): Triangle
	local minX, minZ, maxX, maxZ = BoundingBox(points)
	
	local dx = (maxX - minX) * 10
	local dy = (maxZ - minZ) * 10

	local vert1 = Vector3.new(minX - dx, 0, minZ - dy * 3)
	local vert2 = Vector3.new(minX - dx, 0, maxZ + dy)
	local vert3 = Vector3.new(maxX + dx * 3, 0, maxZ + dy)

	return Triangle(vert1, vert2, vert3)
end

local function EdgesAreEqual(edgeA: Edge, edgeB: Edge)
	local edgeAStart, edgeAEnd = edgeA[1], edgeA[2]
	local edgeBStart, edgeBEnd = edgeB[1], edgeB[2]

	return (
		(edgeAStart == edgeBStart and edgeAEnd == edgeBEnd) or
    (edgeAStart == edgeBEnd and edgeAEnd == edgeBStart)
	)
end

local function FindEdgeIdx(edges: { Edge }, edge): number?
	for idx, edgeB in edges do
		if EdgesAreEqual(edge, edgeB) then return idx end
	end

	return nil
end

local function GetUniqueEdges(edges: { Edge })
	local uniqueEdges = {}

	for iIdx, iEdge in edges do
		local isUnique = true

		for jIdx, jEdge in edges do
			if (iIdx ~= jIdx and EdgesAreEqual(iEdge, jEdge)) then
				isUnique = false
				break
			end
		end

		if isUnique then table.insert(uniqueEdges, iEdge) end
	end

	return uniqueEdges
end

local function DeTri(points: { Vector3 })
	local superTri = SuperTri(points)
	local superTriVert1, superTriVert2, superTriVert3 = superTri[1][1], superTri[2][1], superTri[3][1]

	local triangles: {Triangle } = { superTri }

	for _,point in points do
		local edges: { Edge } = {}

		-- Removes all invalid triangles and adds their edges to a table.
		for triIdx = #triangles, 1, -1 do
			local tri = triangles[triIdx]
			local triEdge1, triEdge2, triEdge3 = tri[1], tri[2], tri[3]

			local circumcentre, circumradius = Circumcircle(triEdge1[1], triEdge2[1], triEdge3[1])
			if (point - circumcentre).Magnitude <= (circumradius - .00001) then
				table.insert(edges, triEdge1)
				table.insert(edges, triEdge2)
				table.insert(edges, triEdge3)
				table.remove(triangles, triIdx)
			end
		end

		local uniqueEdges = GetUniqueEdges(edges)

		for _,edge in uniqueEdges do
			table.insert(triangles, Triangle(edge[1], edge[2], point))
		end
	end

	for triIdx = #triangles, 1, -1 do
		local tri = triangles[triIdx]
		local triVert1, triVert2, triVert3 = tri[1][1], tri[2][1], tri[3][1]

		if (
			triVert1 == superTriVert1 or triVert1 == superTriVert2 or triVert1 == superTriVert3 or
			triVert2 == superTriVert1 or triVert2 == superTriVert2 or triVert2 == superTriVert3 or
			triVert3 == superTriVert1 or triVert3 == superTriVert2 or triVert3 == superTriVert3
		) then
			table.remove(triangles, triIdx)
		end
	end

	return triangles
end
-------------------------------------------------------------------------------------------------------


return {
  DeTri = DeTri,

	-- Draw Helpers
	DrawPoints = DrawPoints,
	DrawTriangles = DrawTriangles
}

Example Usage

local Delaunay = require(Modules.Delaunay)
local PoissonDiscSampling = require(Modules.PoissonDiscSampling)

local DeTri, DrawPoints, DrawTriangles = Delaunay.DeTri, Delaunay.DrawPoints, Delaunay.DrawTriangles

local points = PoissonDiscSampling(
  30,   -- Radius between points.
  Vector3.new(150, 0, 150),   -- The 2d region to place points in (uses Vector3 as they are faster than Vector2).
  150,   -- The number of samples to take (Higher = More precise but slower).
  Random.new()  -- The `Random` object to use.
)

DrawPoints(points)

local triangles = DeTri(points)

DrawTriangles(triangles)

PoissonDiscSampling algorithm can be found here: https://gist.github.com/MightyPart/6fc0649261957261abd5b8c4acfe459b