-- **************************************************
-- Provide Moho with the name of this script object
-- **************************************************

ScriptName = "AE_TriangulateShapes"

-- **************************************************
-- General information about this script
-- **************************************************

AE_TriangulateShapes = {}

function AE_TriangulateShapes:Name()
	return "Triangulate shapes"
end

function AE_TriangulateShapes:Version()
	return "1.0"
end

function AE_TriangulateShapes:UILabel()
	return "Triangulate shapes"
end

function AE_TriangulateShapes:Creator()
	return "Alexandra Evseeva"
end

function AE_TriangulateShapes:Description()
	return "Tries to triangulate each shape on a layer. Illegal shapes will be deleted."
end




-- **************************************************
-- Recurring values
-- **************************************************

-- AE_TriangulateShapes.value1 = false

-- **************************************************
-- Is Enabled
-- **************************************************

function AE_TriangulateShapes:IsEnabled(moho)
	return true
end


-- **************************************************
-- The guts of this script
-- **************************************************

function AE_TriangulateShapes:Run(moho)

	moho.document:PrepUndo(moho.layer)
	moho.document:SetDirty()
	
	--self.outputfile = io.open("p:/temp/test.txt", "w")
	--io.output(self.outputfile)
	
	local mesh = moho:Mesh()
	if not mesh then 
		LM.GUI:Alert(LM.GUI.ALERT_WARNING, "Select mesh layer")
		return 
	end
	
	local trianglesToBuild = {}
	
	local shapesToDelete = {}
	
	for s=0, mesh:CountShapes()-1 do
		local nextShape = mesh:Shape(s)
		local nPoints = nextShape:CountPoints()
		if nPoints < 3 then table.insert(shapesToDelete, nextShape)
		elseif nPoints > 3 then 
			self:TriangulateShape(moho, mesh, nextShape, trianglesToBuild)
			table.insert(shapesToDelete, nextShape)
		end
	end
	
	for k,v in pairs(shapesToDelete) do
		local id = mesh:ShapeID(v)
		mesh:DeleteShape(id)
	end
	
	for k,v in pairs(trianglesToBuild) do
		self:BuildTriangle(moho, mesh, v[1], v[2], v[3])
	end
	
	for p=0, mesh:CountPoints()-1 do 
		mesh:Point(p):SetCurvature(MOHO.PEAKED, 0)
	end 
	
	--io.close(self.outputfile)
	
end


function AE_TriangulateShapes:CheckIntersection(a1, a2, b1, b2)
	local v1 = (b2.x - b1.x)*(a1.y - b1.y) - (b2.y - b1.y)*(a1.x - b1.x)
	local v2 = (b2.x - b1.x)*(a2.y - b1.y) - (b2.y - b1.y)*(a2.x - b1.x)
	local v3 = (a2.x - a1.x)*(b1.y - a1.y) - (a2.y - a1.y)*(b1.x - a1.x)
	local v4 = (a2.x - a1.x)*(b2.y - a1.y) - (a2.y - a1.y)*(b2.x - a1.x)
	return (v1*v2<0) and (v3*v4<0)
end


function AE_TriangulateShapes:BuildEdge(mesh, p1ID, p2ID)
--[[
	mesh:AddLonePoint(mesh:Point(p1ID).fPos, 0)
	mesh:AppendPoint(mesh:Point(p2ID).fPos, 0)
	mesh:WeldPoints(mesh:CountPoints()-2, p1ID, 0)
	mesh:WeldPoints(mesh:CountPoints()-1, p2ID, 0)	
--]]
	local addVector = LM.Vector2:new_local()
	addVector:Set(0.05, 0.05)
	mesh:AddLonePoint(mesh:Point(p1ID).fPos + addVector, 0)	
	mesh:AppendPoint(mesh:Point(p1ID).fPos, 0)
	local d1 = mesh:Point(mesh:CountPoints()-2)
	local p1 = mesh:Point(mesh:CountPoints()-1)
	p1:SetCurvature(MOHO.PEAKED, 0)
	mesh:AppendPoint(mesh:Point(p2ID).fPos, 0)
	local p2 = mesh:Point(mesh:CountPoints()-1)
	p2:SetCurvature(MOHO.PEAKED, 0)
	mesh:AppendPoint(mesh:Point(p2ID).fPos + addVector, 0)
	local d2 = mesh:Point(mesh:CountPoints()-1)
	--io.write("Total: ", mesh:CountPoints(), "; New: ", mesh:PointID(d1), " ", mesh:PointID(p1), " ", mesh:PointID(p2), " ", mesh:PointID(d2), "\n") 
	local newCurve = p1:Curve(0)
	mesh:WeldPoints(mesh:PointID(p1), p1ID, 0)
	mesh:WeldPoints(mesh:PointID(p2), p2ID, 0)
	mesh:DeletePoint(mesh:PointID(d1))
	mesh:DeletePoint(mesh:PointID(d2))
	for i=0, newCurve:CountSegments()-1 do newCurve:SetSegmentOn(i, false) end
end

function AE_TriangulateShapes:BuildTriangle(moho, mesh, p1, p2, p3)
	local edges = {{p1,p2}, {p2,p3}, {p3,p1}}
	for k,v in pairs(edges) do
		if not self:CheckEdge(moho, mesh, v[1], v[2]) then
			self:BuildEdge(mesh, mesh:PointID(v[1]), mesh:PointID(v[2]))
		end
	end
	mesh:SelectNone()
	p1.fSelected = true
	p1:SetCurvature(MOHO.PEAKED, 0)
	p2.fSelected = true
	p2:SetCurvature(MOHO.PEAKED, 0)
	p3.fSelected = true
	p3:SetCurvature(MOHO.PEAKED, 0)
	moho:CreateShape(true)
end

function AE_TriangulateShapes:CheckEdge(moho, mesh, p1, p2)
	for c=0, p1:CountCurves()-1 do
		local where = -1
		local curve, where = p1:Curve(c, where)
		if where < curve:CountPoints()-1 or curve.fClosed then 
			if curve:IsPointOnSegment(mesh:PointID(p2), where) then return true end
		end
		if where > 0 or curve.fClosed then
			where = where - 1
			if where < 0 then where = curve:CountPoints()-1 end
			if curve:IsPointOnSegment(mesh:PointID(p2), where) then return true end
		end
	end
	return false
end

function AE_TriangulateShapes:TriangulateShape(moho, mesh, existingShape, trianglesToBuild)
	--io.write("triangulation started for shape ", mesh:ShapeID(existingShape),"\n")
	local legalShape, vertices = self:CollectShapeVertices(moho, mesh, existingShape)
	--io.write("shape is ", legalShape and "" or "not", " legal","\n")
	if not legalShape then return end
	i = 1
	while #vertices > 3 do
		local success = true
		while success and #vertices > 3 do 
			--io.write("run with i = ", i,"\n")
			success, IDs = self:BuildAnEar(moho, mesh, vertices, i)
			if success then 
				table.insert(trianglesToBuild, {vertices[IDs[1]], vertices[IDs[2]], vertices[IDs[3]]})
				table.remove(vertices, IDs[2])
				if IDs[2]<i then i = i-1 end
				--io.write("remove id ", IDs[2], " Now array has ", #vertices,"\n")
			end
		end
		if #vertices > 3 then
			i = i + 1
			if i > #vertices then i = 1 end
		end
	end
	if #vertices == 3 then table.insert(trianglesToBuild, vertices) end
end

function AE_TriangulateShapes:CollectShapeVertices(moho, mesh, shape)
	--io.write("Shape ", mesh:ShapeID(shape), " check started","\n")
	local returnTable = {}
	local edges = {}
	for p=0, shape:CountPoints()-1 do
		local meshID = shape:GetPoint(p)
		local nextPoint = mesh:Point(meshID)
		local segmentsInShape = 0
		local nextPointInfo = {["point"] = nextPoint, ["edges"]={}}
		--io.write("Point ", p, "(number ", meshID, " in mesh) has ", nextPoint:CountCurves(), " curves","\n")
		for c=0, nextPoint:CountCurves()-1 do
			local pointOnCurve = -1
			local nextCurve, pointOnCurve = nextPoint:Curve(c)			
			local curveSegsInShape = 0
			if pointOnCurve < nextCurve:CountPoints()-1 or nextCurve.fClosed then
				if shape:ContainsEdge(mesh:CurveID(nextCurve), pointOnCurve) then 
					curveSegsInShape = curveSegsInShape + 1 
					table.insert(nextPointInfo.edges, {["curve"]= nextCurve, ["seg"]= pointOnCurve, ["self"] = 0})
				end
			end
			if pointOnCurve > 0 or nextCurve.fClosed then
				local seg = pointOnCurve - 1
				if seg < 0 then seg = nextCurve:CountPoints()-1 end
				if shape:ContainsEdge(mesh:CurveID(nextCurve), seg) then 
					curveSegsInShape = curveSegsInShape + 1 
					table.insert(nextPointInfo.edges, {["curve"]= nextCurve, ["seg"]= seg, ["self"] = 1})
				end
			end
			if nextCurve:CountPoints() == 2 and curveSegsInShape == 2 then curveSegsInShape = 1 end
			--io.write("Curve ", c, "/", mesh:CurveID(nextCurve), "( ", pointOnCurve, " point on curve, total ", nextCurve:CountPoints(), " points in curve) has ", curveSegsInShape, " segs in Shape","\n")
			segmentsInShape = segmentsInShape + curveSegsInShape
		end
		--io.write(segmentsInShape, " segments in shape","\n")
		if segmentsInShape ~= 2 then return false end
		table.insert(edges, nextPointInfo)
	end
	
	local sorted = {}
	local currentEntry = edges[1]
	local nextEntry = nil
	local previousPoint = nil
	table.insert(sorted, currentEntry)
	repeat 
		nextEntry = self:FindNextEntry(moho, mesh, edges, previousPoint, currentEntry)
		if nextEntry then
			table.insert(sorted, nextEntry)
			previousPoint = currentEntry.point
			currentEntry = nextEntry
		end
		--io.write("now first condition is ", (nextEntry == nil)and "true" or "false", " second is ", (nextEntry.point == sorted[1].point) and "true" or "false", "\n")
	until nextEntry == nil or nextEntry.point == sorted[1].point
	--io.write("Now sorted has ", #sorted, " and edges has ", #edges, "\n")
	
	if #sorted < #edges then return false end
	if sorted[1].point == sorted[#sorted].point then table.remove(sorted, #sorted) 
	else return false 
	end
	
	for k,v in pairs(sorted) do
		table.insert(returnTable, v.point)
	end
	
	--[[
	local lastConnectToFirst = false
	for k,v in pairs(edges[shape:CountPoints()-1]) do
		if v.curve:IsPointOnSegment(shape:GetPoint(0), v.seg) then lastConnectToFirst = true end
	end
	if not lastConnectToFirst then return false end
	--]]
	
	--io.write("Last connect to first checked","\n")
	
	for e=0, shape:CountEdges()-1 do
		curveID, segID = shape:GetEdge(e, curveID, segID)
		local nextCurve = mesh:Curve(curveID)
		local pa1 = nextCurve:Point(segID)
		segID = segID + 1
		if segID > nextCurve:CountPoints()-1 then segID = 0 end
		local pa2 = nextCurve:Point(segID)
		for ee = e+1, shape:CountEdges()-1 do
			curveID, segID = shape:GetEdge(ee, curveID, segID)
			nextCurve = mesh:Curve(curveID)
			local pb1 = nextCurve:Point(segID)
			segID = segID + 1
			if segID > nextCurve:CountPoints()-1 then segID = 0 end
			local pb2 = nextCurve:Point(segID)	
			if self:CheckIntersection(pa1.fPos, pa2.fPos, pb1.fPos, pb2.fPos) then return false end
		end
	end

	return true, returnTable
end

function AE_TriangulateShapes:FindNextEntry(moho, mesh, edgesArray, previousPoint, currentEntry)
	--io.write("Entering FindNextEntry with point no ", mesh:PointID(previousPoint), " as previous, point no ", mesh:PointID(currentEntry.point), " as current\n")
	for i=1,2 do
		local edge = currentEntry.edges[i]
		--io.write("edge no ", i, " is curve no ", mesh:CurveID(edge.curve), " seg no ", edge.seg, " self is ", edge.self, "\n")
		local otherPoint = edge.curve:Point(edge.seg + 1 - edge.self)
		--io.write("other point is ", mesh:PointID(otherPoint), "\n")		
		if otherPoint ~= previousPoint then 
			for k,v in pairs(edgesArray) do
				--io.write("Check point no ", mesh:PointID(v.point), "\n")
				if v.point == otherPoint then
					--io.write("found\n")
					return v 
				end
			end
		end
	end
	--io.write("not found\n")
	return nil
end

function AE_TriangulateShapes:BuildAnEar(moho, mesh, vertices, i)

	local k1 = i
	local k2 = k1 + 1
	if k2 > #vertices then k2 = 1 end
	local k3 = k2 + 1
	if k3 > #vertices then k3 = 1 end
	local a1 = vertices[k1]	
	local a2 = vertices[k3]
	
	local a3pos = (a1.fPos + a2.fPos)/2
	local a4pos = (a1.fPos + vertices[k2].fPos)/2
	local a4etern = a3pos + ((a4pos - a3pos) * 1000)
	local numIntersects = 0
	
	for k, b1 in pairs(vertices) do
		local kk = k + 1
		if kk > #vertices then kk = 1 end
		b2 = vertices[kk]
		if self:CheckIntersection(a1.fPos, a2.fPos, b1.fPos, b2.fPos) then return false end
		if self:CheckIntersection(a3pos, a4etern, b1.fPos, b2.fPos) then numIntersects = numIntersects + 1 end
	end
	--io.write("first check passed","\n")
	if math.fmod(numIntersects, 2) == 0 then return false end	
	
	return true, {k1, k2, k3}
end

AE Trangulate Shapes
Listed

Script type: Button/Menu

Uploaded: Sep 15 2020, 10:34

Alternative to built-in Triangulate 2D Mesh, not deleting existing edges
This script, and all other scripts on this site are distributed as free software under the GNU General Public License 3.0 or later.
Downloads count: 3