Polygon Intersection in 2d

Hi,

If you're concerned about the cost of projecting the vertices for the SAT test, there are several optimizations that can be made.

The first comes from the observation that for the i'th normal of a polygon, the vertices of that polygon with the maximum and minimum projections will always be the same. In fact, relative to the center of the polygon, the projections themselves are always the same, and can be precalculated and stored with the polygon. As is often the case, there is a trade-off between efficiency and memory consumption with this approach.

For projecting polygon A onto the normals of polygon B and vice versa, you obviously need a generic 'project onto axis' function. This too can be accelerated. Approaches to this include:

1. Hill climbing
2. Dobkin-Kirkpatrick hierarchy
3. Binary partitioning

I'll be glad to provide references or additional information on any of the above if you're interested.

Quote:

Original post by jyk 1. Hill climbing 2. Dobkin-Kirkpatrick hierarchy 3. Binary partitioning I'll be glad to provide references or additional information on any of the above if you're interested.

Oh, by all means, please do ():-)

Quote:

Oh, by all means, please do ():-)

Ok :-)

Here are some books that touch on one or more of the above topics:

1. 'Real-Time Collision Detection', Christer Ericson
2. 'Collision Detection...', Gino van den Bergen
3. 'Game Physics', Dave Eberly

If you're not in a position to run out and buy a new book, google might be helpful, although these particular topics don't seem to turn up that much. You might also try the 'documentation' section at geometrictools.com. However, although there is a paper there on SAT, I don't know that it discusses optimizations.

In the meantime, here's a brief summary.

1. Hill climbing

This is probably the easiest to implement. Let's say you're looking for the maximum projection of a polygon. Start with an arbitrary vertex i and find its projection. Also, find the projections for this vertex's left and right neighbors.

If both the left and right neighbors have a lesser projection, than i is the maximum and you're done. If one of the neighbors has a greater projection, make that neighbor i and repeat the process. This will 'climb' towards the vertex of maximal projection.

Further optimization can be made by avoiding projecting the same vertex more than once. Also, there are some 'gotchas' with colinear or nearly colinear vertices.

2. Dobkin-Kirkpatrick

The Dobkin-Kirkpatrick hierarchy for a convex polygon or polyhedron can be used to accelerate a number of queries, such as intersection, distance, projection, etc. It's probably overkill for this particular problem, though. I would instead recommend:

3. Binary partitioning

The only place I've seen this discussed is in Eberly's 'Game Physics'. If you can get a hold of that book you'll have all the info you need. The general idea is to imagine a circle, with the normals of the polygon as the 'spokes'. You can see that any axis will fall 'between' two of the spokes, as determined by the perp-dot product. Furthermore, each arc between the endpoints for two neighboring normals corresponds to a vertex of the polygon. By performing a binary search, you can quickly find in which arc the axis lies, and therefore which vertex projects onto it maximally.

Another general observation is that for two polygons A and B, the axis 'a' that separated them at time t is likely to also separate them at time t+dt. If 'a' does not separate them at time t+dt, a normal that is a neighbor of the normal used to generate 'a' is a good place to start looking for a new separating axis.

I know that's all a little vague. Again, I'll be glad to discuss it further if you're interested in the binary search approach. I'm pretty sure I have some code for this lying around, although it's just sketch work, nothing production-quality.

Oh, that is more than enough for now.

You've been very helpful. Thanks millions!

you could also use a 2D version of the GJK algo.