[HN Gopher] An Algorithm for Polygon Intersections
___________________________________________________________________
An Algorithm for Polygon Intersections
Author : lnyan
Score : 105 points
Date : 2022-10-02 06:07 UTC (16 hours ago)
(HTM) web link (gorillasun.de)
(TXT) w3m dump (gorillasun.de)
| dahart wrote:
| 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.
| EGreg wrote:
| 22 years ago I wrote this for the special case of rectangles:
|
| https://www.flipcode.com/archives/Theory_Practice-Issue_01_C...
| pixelpoet wrote:
| Nice to see more flipCode people around :) So much great
| information back in those days!
| lemonade5117 wrote:
| The blog looks really nice! Definitely gonna read the other posts
| when I have time.
| dvh wrote:
| 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.
| Someone wrote:
| 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.
| EGreg wrote:
| Don't you mean a random ray (line going only in one direction
| from the point)?
| dvh wrote:
| Yep
___________________________________________________________________
(page generated 2022-10-02 23:02 UTC)