Difference between revisions of "PointInConvexPolygon"
(→Second solution) |
|||
Line 40: | Line 40: | ||
== Second solution == | == Second solution == | ||
<source lang="lua"> -- from https://stackoverflow.com/questions/77904973/check-if-point-is-in-convex-polygon | <source lang="lua"> -- from https://stackoverflow.com/questions/77904973/check-if-point-is-in-convex-polygon | ||
− | local function | + | local function pointInConvexPolygon (x, y, poly) |
-- poly as {x1,y1, x2,y2, x3,y3, ...} | -- poly as {x1,y1, x2,y2, x3,y3, ...} | ||
local function polyEdgeIterator(poly) | local function polyEdgeIterator(poly) |
Latest revision as of 07:45, 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 pointInConvexPolygon (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