Check if point is in or on the edge of a polygon

BULK_BROGAN · August 4, 2019, 5:27pm

So I’ve implemented an even-odd algorithm to detect if a point is within a simple polygon which works. The problem I’m facing now is checking if its on the edge of the polygon, which I want to return true but an even-odd check returns as false.

So the possibilities I’ve considered to do this is to do either one of the following tests:
1.
Let the line of the polygon I’m testing be defined as the vector B-A, and the point I’m checking C. I would just simply do

return (A-C).magnitude + (C-B).magnitude == (A-B).magnitude

Thats rather simple, but this equation would be used on every frame so I’d probably use the more complex…
2.
Convert the vector to a y=mx+c line, and go from there

But I’m interested if there is an algorithm which will do it without a lot of different tests? Because my two solutions require me to first run the regular even-odd check, and then follow up with some more (potentially expensive) maths.

Any help would be greatly appreciated

IdiomicLanguage · August 4, 2019, 5:42pm

You can use my GJK distance and intersection algorithm here:

github.com

TylerRHoyer/GJK-3D-Intersection/blob/master/GJK.lua

--Gilbert-Johnson-Keerthi distance and intersection tests
--Tyler R. Hoyer
--11/20/2014

--May return early if no intersection if found. If it is primed, it will run in amortized constant time (untested).

--If the distance function is used between colliding objects, the program
--may loop a hundred times without finding a result. If this is the case, 
--it will throw an error. The check is omited for speed. If the objects
--might intersect eachother, call the intersection method first.

--Objects must implement the :getFarthestPoint(dir) function which returns the
--farthest point in a given direction.

--Used Roblox's Vector3 userdata. Outside implementations will require a implementation of the methods of
--the Vector3's. :Dot, :Cross, .new, and .magnitude must be defined.

local abs = math.abs
local min = math.min
local huge = math.huge

This file has been truncated. show original

This algorithm can find the distance and intersection of any convex shape in up to 3 dimensions. It currently returns intersections including touching, although this could be easily changed by changing the inequality on line 86 to be <=.

You can search my profile for example usage and take a look at Checking if a part is touching another part every .1 seconds?