4 ms·
Neat algorithm to detect if point is inside polygon is too draw a random line and count intersections, if it's odd the point is inside polygon. I use a lot of
by dvh 4y ago
Neat algorithm to detect if point is inside polygon is too draw a random line and count intersections, if it's odd the point is inside polygon.
I use a lot of operations with basic geometric primitives and whenever I use stackoverflow it takes years to iron out all the special cases in which top stackoverflow answer fails.
- EGreg 4y agoDon’t you mean a random ray (line going only in one direction from the point)?
- dvh 4y agoYep
- Someone 4y agoFor convex polygons, I would think checking that it’s on the correct side of each oriented edge of the polygon is faster. It allows for an early exit. Best-case, you’d only need to check that for a single edge. That’s especially true if many points being tested lie far away from the polygon. If your polygon isn’t convex, splitting it in multiple convex ones may be the better choice. You can then use the lines you used to divide the polygon to quickly discard some of the partial polygons. Whatever you do, numerical errors may bite you. If that ray happens to pass close to a vertex, tiny calculation errors may make you decide it intersects an edge while it doesn’t or vice versa. For the algorithm you propose, you can fairly easily detect that and pick another random ray if it does. I don’t think that makes up for the inefficiency of always having to check all edges, though.