Cut polygon with line

[darkfrei]

Hi all!

I've tried a lot of time to make the system, where you can draw infinity lines and subtract the infinity area with infinity lines.

Here is one of them, please help me to fix it, it works normally good, but sometimes not good.

Legend:
White: segment;
Yellow - infinity line or ray;
Green: temporary line, that is drawn by user.

Press mouse, move and release mouse button and draw the line to add the line/ray/segment.

Code: Select all

segments = {
	{
		pointA = {x=50, y=50},
		limitedA = false,
		pointB = {x=700, y=110}, 
		limitedB = false,
	},
	{
		pointA = {x=750, y=50},
		limitedA = false,
		pointB = {x=740, y=400}, 
		limitedB = false,
	},
--	{
--		pointA = {x=700, y=550},
--		limitedA = false,
--		pointB = {x=100, y=500}, 
--		limitedB = false,
--	},
--	{
--		pointA = {x=120, y=600},
--		limitedA = false,
--		pointB = {x=100, y=100}, 
--		limitedB = false,
--	},
}


local function getCutPoint(tDataA, tDataB)
	local x1, y1, x2, y2 = tDataA.pointA.x, tDataA.pointA.y, tDataA.pointB.x, tDataA.pointB.y
	local x3, y3, x4, y4 = tDataB.pointA.x, tDataB.pointA.y, tDataB.pointB.x, tDataB.pointB.y

	local limidedAStart, limidedAEnd = tDataA.limitedA, tDataA.limitedB
	local limidedBStart, limidedBEnd = tDataB.limitedA, tDataB.limitedB

	local dx1, dy1, dx2, dy2 = x2 - x1, y2 - y1, x4 - x3, y4 - y3

	if dx1*dx1 + dy1*dy1 == 0 or dx2*dx2 + dy2*dy2 == 0 then return end -- zero length
	local denominator = dx1 * dy2 - dy1 * dx2
	if denominator == 0 then return end -- parallel

	local dx13, dy13 = x1 - x3, y1 - y3
	local t = (dx13 * (y3 - y4) - dy13 * (x3 - x4)) / denominator
	local u = (dx13 * (y1 - y2) - dy13 * (x1 - x2)) / denominator

	if (not limidedAStart or t > 0) and (not limidedAEnd or t < 1) and
	(not limidedBStart or u > 0) and (not limidedBEnd or u < 1) then
		return {x = x1 + t * dx1, y = y1 + t * dy1}
	end
end

local function isRightDirection(tDataA, tDataB)
	local dxA, dyA = tDataA.pointB.x - tDataA.pointA.x, tDataA.pointB.y - tDataA.pointA.y
	local dxB, dyB = tDataB.pointB.x - tDataB.pointA.x, tDataB.pointB.y - tDataB.pointA.y
	return dxA * dyB - dyA * dxB > 0
end


local function modifyEndings (tDataA, tDataB, point)
	tDataA.pointB = point
	tDataA.limitedB = true
	tDataA.next = tDataB

	tDataB.pointA = point
	tDataB.limitedA = true
	tDataB.prev = tDataA
end

local function solveSegment (segments, tDataA)

	for indexB, tDataB in ipairs (segments) do
		local point = getCutPoint(tDataA, tDataB)
		if point then
			if isRightDirection(tDataA, tDataB) then
				modifyEndings (tDataA, tDataB, point)
			else
				modifyEndings (tDataB, tDataA, point)
			end
		end
	end

	-- found at least start and end (A und B points)
--	return tDataA.limitedA and tDataA.limitedB
	return tDataA.limitedA or tDataA.limitedB
end

local function filterSegments (segments)
	for index, tData in ipairs (segments) do
		tData.valid = tData.prev and tData.next and true or false
		tData.index = index
	end

	for index = #segments, 1, -1 do
		local tData = segments[index]
		local listNext = {tData}
		local first_tData = tData
		while tData.valid do
--			print ('tData.index', tData.index..':', tostring (tData.next.index), tostring (tData.prev.index))
			if tData.next and tData.next.prev and tData.next.prev == tData 
			and tData.prev and tData.prev.next and tData.prev.next == tData then
--				print (tData.index, tData.next.index, tData.prev.index)
--				print ('tData.index', tData.prev.index, tData.index, tData.next.index, tostring (tData.valid))
				if tData.next == first_tData then
					table.insert (listNext, tData.next)
					local str = ""
					for i, v in ipairs (listNext) do
						str = str .. ' '.. v.index
					end
					print ('cycle', str)
					break
				else
					table.insert (listNext, tData.next)
					tData = tData.next
				end
			else
--				no next; all list is not cycled
				for i, v in ipairs (listNext) do
					v.valid = false
					print ('not valid:', i)  
				end
			end

		end

		if not tData.valid and not (not tData.limitedA or not tData.limitedB )then
			print('removed filter:', tData.index)
			table.remove (segments, index)
		end
	end
end

local function updateSegments (segments)
	for indexA = #segments, 1, -1 do
		local tDataA = segments[indexA]
		if tDataA.valid == nil then
			tDataA.valid = true
		end
		if not solveSegment (segments, tDataA) then
			-- no collisions for this segment
			print('removed', indexA)
--			table.remove (segments, indexA)
			table.valid = false
		end
	end

	filterSegments (segments)
end

updateSegments (segments)

local function drawSegment (tData, index)
	if tData.valid then
		love.graphics.setColor (1,1,1)
	else
		love.graphics.setColor (1,1,0)
	end
	love.graphics.line (tData.pointA.x, tData.pointA.y, tData.pointB.x, tData.pointB.y)

	if tData.valid then

		if tData.limitedA then
			love.graphics.circle ('line', tData.pointA.x, tData.pointA.y, 2)
		end
		if tData.limitedB then
			love.graphics.circle ('line', tData.pointB.x, tData.pointB.y, 4)
		end
end
		love.graphics.print (index, tData.pointA.x, tData.pointA.y)
		love.graphics.print (index, tData.pointB.x, tData.pointB.y+14)
	
end



function love.draw ()
	for i, tData in ipairs (segments) do
		drawSegment (tData, i)
	end

	if tempLine and #tempLine == 4 then
		love.graphics.setColor (0,1,0)
		love.graphics.line (tempLine)
	end
end


function love.mousepressed (x, y)
	tempLine = {x, y}
end

function love.mousemoved (x, y)
	if tempLine then
		tempLine[3] = x
		tempLine[4] = y
	end
end

function love.mousereleased (x, y)
	if #tempLine == 4 then
		local segment = {
			pointA = {x=tempLine[1], y=tempLine[2]},
			limitedA = false,
			pointB = {x=tempLine[3], y=tempLine[4]}, 
			limitedB = false,
		}
		table.insert (segments, segment)
		updateSegments (segments)
		tempLine = nil
	end
end

function love.keypressed(key, scancode, isrepeat)
	if key == "escape" then
		love.event.quit()
	end
end