I'm trying to check if point x, y
is inside of polygon poly = {x1,y1, x2,y2, x3,y3 ...}
But something goes wrong:
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 -- fixed
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
Sometimes clockwise direction is right, but sometimes it says wrong direction.
The correct formula of the triangle signed area is (x1*y2 - x2*y1)/2
assuming the third vertex is at (0,0)
A point is inside a convex poly when all point-edge-traingle areas are of the same sign.
local function polyEdgeIterator(poly)
-- poly as {x1,y1, x2,y2, x3,y3, ...}
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 function getTriangleArea(x0,y0, x1,y1, x2,y2)
-- area of the triangle, its sign is determined by the triangle vertices sequence direction (CW/CCW)
return ((x1-x0) * (y2-y0) - (x2-x0) * (y1-y0)) * 0.5
end
local function pointInConvexPolygon(x, y, poly)
local minArea, maxArea = 0, 0
for x1,y1, x2,y2 in polyEdgeIterator(poly) do
local area = getTriangleArea(x,y, x1,y1, x2,y2)
minArea = math.min(minArea, area)
maxArea = math.max(maxArea, area)
if minArea * maxArea < 0 then
return false
end
end
return true
end
print(pointInConvexPolygon(2,1, {1,-1, 2,2, 4,1})) -- true
print(pointInConvexPolygon(3,0, {1,-1, 2,2, 4,1})) -- false