-- **************************************************
-- 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