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