Difference between revisions of "PointInConvexPolygon"

(Created page with "A function returning True if the given point is inside the given convex polygon. <source lang="lua"> local function pointInConvexPolygon(x, y, poly) -- poly as {x1,y1, x2,y2...")
 
Line 1: Line 1:
 
A function returning True if the given point is inside the given convex polygon.
 
A function returning True if the given point is inside the given convex polygon.
  
 +
 +
 +
== First solution ==
 
<source lang="lua">
 
<source lang="lua">
 
local function pointInConvexPolygon(x, y, poly)
 
local function pointInConvexPolygon(x, y, poly)
Line 34: Line 37:
 
</source>
 
</source>
  
Example
+
 
 +
== Second solution ==
 +
<source lang="lua"> -- from https://stackoverflow.com/questions/77904973/check-if-point-is-in-convex-polygon
 +
local function pointInConvexPolygon2 (x, y, poly)
 +
-- poly as {x1,y1, x2,y2, x3,y3, ...}
 +
local function polyEdgeIterator(poly)
 +
local i, imax = 0, #poly
 +
local x2, y2 = poly[imax-1], poly[imax]
 +
return function()
 +
i = i + 2
 +
if i <= imax then
 +
local x1, y1 = x2, y2
 +
x2, y2 = poly[i-1], poly[i]
 +
return x1, y1, x2, y2
 +
end
 +
end
 +
end
 +
 
 +
local minArea, maxArea = 0, 0
 +
for x1,y1, x2,y2 in polyEdgeIterator(poly) do
 +
local area = (x1-x) * (y2-y) - (x2-x) * (y1-y)
 +
minArea = math.min(minArea, area)
 +
maxArea = math.max(maxArea, area)
 +
if minArea * maxArea < 0 then
 +
return false
 +
end
 +
end
 +
return true
 +
end
 +
</source>
 +
 
 +
== Example ==
 +
 
  
 
<source lang="lua">
 
<source lang="lua">
 
 
function love.load()
 
function love.load()
 
poly = {100, 100, 400, 150, 200, 300}
 
poly = {100, 100, 400, 150, 200, 300}

Revision as of 07:34, 1 February 2024

A function returning True if the given point is inside the given convex polygon.


First solution

local function pointInConvexPolygon(x, y, poly)
	-- poly as {x1,y1, x2,y2, x3,y3, ...}
	local imax = #poly

	local function isVerticesClockwise(poly)
		local sum = 0
		local imax = #poly
		local x1, y1 = poly[imax-1], poly[imax]
		for i = 1, imax - 1, 2 do
			local x2, y2 = poly[i], poly[i + 1]
			sum = sum + (x2 - x1) * (y2 + y1)
			x1, y1 = x2, y2
		end
		local isClockwise = sum < 0
		love.window.setTitle(isClockwise and 'clockwise' or 'counterclockwise')
		return isClockwise
	end

	local sign = isVerticesClockwise(poly) and 1 or -1
	local x1, y1 = poly[imax-1], poly[imax]
	for i = 1, imax - 1, 2 do
		local x2, y2 = poly[i], poly[i + 1]
		local dotProduct = (x - x1) * (y1 - y2) + (y - y1) * (x2 - x1)
		if sign * dotProduct < 0 then
			return false
		end
		x1, y1 = x2, y2
	end
	return true
end


Second solution

 -- from https://stackoverflow.com/questions/77904973/check-if-point-is-in-convex-polygon
local function pointInConvexPolygon2 (x, y, poly)
-- poly as {x1,y1, x2,y2, x3,y3, ...}
	local function polyEdgeIterator(poly)
		local i, imax = 0, #poly
		local x2, y2 = poly[imax-1], poly[imax]
		return function()
			i = i + 2
			if i <= imax then
				local x1, y1 = x2, y2
				x2, y2 = poly[i-1], poly[i]
				return x1, y1, x2, y2
			end
		end
	end

	local minArea, maxArea = 0, 0
	for x1,y1, x2,y2 in polyEdgeIterator(poly) do
		local area = (x1-x) * (y2-y) - (x2-x) * (y1-y)
		minArea = math.min(minArea, area)
		maxArea = math.max(maxArea, area)
		if minArea * maxArea < 0 then
			return false
		end
	end
	return true
end

Example

function love.load()
	poly = {100, 100, 400, 150, 200, 300}
	local x, y = 400, 300
	inside = pointInConvexPolygon (x, y, poly)
end

local function drawArrow(x1, y1, x2, y2)
	local angle = math.atan2(y2 - y1, x2 - x1)
	local arrowSize = 20
	local x3 = x2 - arrowSize * math.cos(angle - math.pi / 16)
	local y3 = y2 - arrowSize * math.sin(angle - math.pi / 16)
	local x4 = x2 - arrowSize * math.cos(angle + math.pi / 16)
	local y4 = y2 - arrowSize * math.sin(angle + math.pi / 16)
	love.graphics.line(x3, y3, x2, y2, x4, y4)
end

function love.draw()
	love.graphics.setLineStyle ('rough')
	love.graphics.setLineWidth (1)
	love.graphics.setLineJoin ('none')
	if inside then
		love.graphics.setColor (1,1,0)
	else
		love.graphics.setColor (0,1,1)
	end
	if #poly > 4 then
		love.graphics.polygon ('line', poly)
		local imax = #poly
		local x1, y1 = poly[imax-1], poly[imax]
		for i = 1, imax - 1, 2 do
			local x2, y2 = poly[i], poly[i + 1]
			drawArrow(x1, y1, x2, y2)
			x1, y1 = x2, y2
		end
	elseif #poly > 2 then
		love.graphics.line (poly)
		drawArrow(poly[1], poly[2], poly[3], poly[4])
	end
	love.graphics.setColor (1,1,1)
	love.graphics.print ('Left mouse botton to add new point', 14, 14)
	love.graphics.print ('Right mouse botton to remove last point', 14, 2*14)
	love.graphics.print ('Is inside: '..tostring(inside), 14, 4*14)
end


function love.mousepressed( x, y, button, istouch, presses )
	if button == 1 then -- left mouse button
		table.insert (poly, x)
		table.insert (poly, y)
	elseif button == 2 then -- right mouse button
		table.remove (poly)
		table.remove (poly)
	end
	inside = pointInConvexPolygon (x, y, poly)
end

function love.mousemoved( x, y, dx, dy, istouch )
	inside = pointInConvexPolygon (x, y, poly)
end