Re:An Algorithm for Polygon Intersections
by Someone on Sunday October 02, 2022 @10:18AM
(#33056068)
For 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.
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.