Re:An Algorithm for Polygon Intersections
by dahart on Sunday October 02, 2022 @10:47AM
(#33056303)
Writing collision detection is really fun. There’s enough in this article to take it and then build a tiny rigid body physics simulation - you only need to add gravity and then work out the forces two rectangles impart on each other when they collide. There’s a change to the center of mass velocity and a change to the rotation velocity.
One thing that makes it easier IMO is to use Y-up coordinates. Instead of putting the origin top-left like the article, use bottom-left. If you need, convert screen coordinates to your “world space” and back in some code that is outside of the collision & simulation. There’s no reason to be stuck with the default coordinates, or have to think upside down. (Intersection when “top bound of R1 is less than bottom bound of R2” sounds backwards to me.)
Another fun part is accelerating collision detection / simulation. This algorithm in the demo code is O(n^2) in total edges, I believe. But you don’t need to change the algorithm necessarily, you can speed it up dramatically with an acceleration structure of some kind. It’s a fun weekend project and satisfying to suddenly be able to add thousands of polygons to your sim without locking up the machine.
Re:An Algorithm for Polygon Intersections
by dvh on Sunday October 02, 2022 @04:55AM
(#33054205)
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.
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.
One thing that makes it easier IMO is to use Y-up coordinates. Instead of putting the origin top-left like the article, use bottom-left. If you need, convert screen coordinates to your “world space” and back in some code that is outside of the collision & simulation. There’s no reason to be stuck with the default coordinates, or have to think upside down. (Intersection when “top bound of R1 is less than bottom bound of R2” sounds backwards to me.)
Another fun part is accelerating collision detection / simulation. This algorithm in the demo code is O(n^2) in total edges, I believe. But you don’t need to change the algorithm necessarily, you can speed it up dramatically with an acceleration structure of some kind. It’s a fun weekend project and satisfying to suddenly be able to add thousands of polygons to your sim without locking up the machine.
https://www.flipcode.com/archives/Theory_Practice-Issue_01_C...
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.
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.