# Know Any O(ln N) Convex Poly-Circle Overlap Tests?

This topic is 4344 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm interested in performing an overlap test between a convex polygon (with verts stored in clockwise order) and a circle. The test should return the depth and contact normal. There are a number of brute force methods that can be done in O(N) time (testing overlap on all the edges and all the verts, for instance), but I'd rather perform the test faster. One way would be to generate the Voronoi diagram for the poly (a la the Metanet tutorials) and then build a trapezoidal map on top of that, which can be used to determine which Voronoi region the circle's center is in in O(ln N) time. Once you know which Voronoi region the center's in, the rest is easy. The problems with that method are that it has a pretty big constant associated with it, and it doesn't sound too fun to program up. Does anyone know any simpler methods for doing the same thing? John Edwards

##### Share on other sites
use the Separating Axis Theorem,
and test it againts side of the convex polygon, because
end of the day, u'll be testing against the sides, so do it against the sides,
then, u can get the normal easily, via a normal to the side itself (I assume your doing 2D, sounds like it anyway! (-vy, vx)), that will be the collision normal. Then...
check whether the end of the penetration vector is inside the polygon and if it is, u can return that penetration length because it is now a valid collison.

Although this way will fail if parts of the circle is engulfing the polygon on oneside and the parts on another side of the same polygon. The trick to solve this is to get the shortest "valid" point from polygon (use SAT again!) and immediately place the circle there. so no penetration occurs.

Or u could make convex poly's using triangles and use metanets way of checking collision with triangles (n' other fancy shapes) using the tiles. I find using metanets solution of tiles in 2D very super. because its sooo fast in flash itself and when tried in C++ using ogl/dx or any api, its even faster (than flash) and u can make laaarge maps with super game play.

I really hope this helped man.

##### Share on other sites
The SAT is nice, and all. I'm using a version of it for swept circle vs. polygon collisions, but that method takes O(N), and I swear plain overlap (velocity = 0) tests don't need to take that long. Now, my polygons are all pretty simple (3-6 sides, in general), so it could be that O(ln N) methods have constants terms that are too large to make them worth while. If anyone has actually experimented with O(ln N) methods and discovered that they are slower than SAT-type methods for 3-6 sided polygons, I'd be glad to hear it. I'd be most glad, however, to hear about a slick O(ln N) algorithm that actually does increase collision detection speeds.

John Edwards

##### Share on other sites
Okay, I've figured out a method that more-or-less meets the criteria:

David Eberly defines a function called ExtremeVert in his game physics book that returns the index of the vertex with the largest projection onto a given direction vector in O(ln N) time for convex polygons with clockwise (or counter-clockwise) ordered vertices.

If you pass ExtremeVert the vector pointing from the polygon's center to the circle's center, it returns the vertex that (as much as we need it to be) is, or is in the edge that is the the closest feature to the center of the circle.

That means, to find the overlap, we just have to overlap-test against two edges and a vertex (which takes constant time).

This algorithm takes O(ln N) and doesn't require any elaborate data structures, so it satisfies my requirements. If people know better methods, I'd still be interested in hearing them, though.

John Edwards

##### Share on other sites
You probably could even adapt Eberly's algorithm to return point closest to circle center directly, without hacks... (i guess his method uses some kind of binary search that will work directly with distances too).

##### Share on other sites
Eberly uses a binary search to find where the direction vector dotted with the edge vector changes signs. It certainly would be nice to adapt the algorithm to find the closest point, though, since using ExtremeVert can break down when the circle's center is inside the polygon. Practically speaking, it's only a problem for oblong polygons with a lot of vertices, which won't come up too often, but it would still be nice to have an algorithm that works in all cases.

John Edwards

##### Share on other sites
I didn't read the whole thread, but if you're looking for an effective method for finding the closest point on a 2D convex polygon to a point (the first step in a discrete circle vs. polygon test), you might look into the Dobkin-Kirkpatrick hierarchy. In 3D it's a bit complicated, but the 2D version is quite straightforward. It's useful for other queries (such as extremal vertex) as well.

##### Share on other sites
Quote:
 Original post by PistachioProEberly uses a binary search to find where the direction vector dotted with the edge vector changes signs. It certainly would be nice to adapt the algorithm to find the closest point, though, since using ExtremeVert can break down when the circle's center is inside the polygon. Practically speaking, it's only a problem for oblong polygons with a lot of vertices, which won't come up too often, but it would still be nice to have an algorithm that works in all cases.John Edwards

if you mostly have polygons with few vertices, O(n) algorithms may be overally faster than O(log(n)) (that's because actual times will be like a*n_b versus c*log(n)+d ; this "O" only tells you how it behaves with large n)

Try finding the edge where difference of distances between edge vertices and circle center changes sign(i.e. distance(vertice1,circle_center)-distance(vertice2, circle_center)) (like this dot product it changes sign on closest and farthest).

As for cases when circle center is on inside, the problem is that a: this way circle could be not intersecting any edges at all, b: from inside, it is concave and not convex.

[Edited by - Dmytry on April 2, 2006 4:05:37 AM]

##### Share on other sites
@ jyk: I've looked around for information on Dobkin-Kirkpatrick hierarchies, and I found a lot of papers using them, but no information on how to build them. Do you have a link?

@Dmytry: Yeah, I know that when dealing with small input sizes O(ln N) algorithms are often slower than O(N), but I figured there might be some simple binary search-type method for finding the closest vertex to a point that would shave off a few dot products from the overlap calculation (which might reduce total collision calculation time by 10%, or more).

As far as searching on distance(vertice1,circle_center)-distance(vertice2, circle_center) is concerned, I don't know how to do that, since that value isn't strictly increasing or decreasing around the polygon.

Unless it turns out I can get a hold of an explanation of Dobkin-Kirkpatrick hierarchies, and it looks like they're worthwhile, I'll probably just do an O(N) search through all the vertices for the one that has the smallest squared distance to the circle center.

Thanks for the suggestions, though. This has been an interesting exercise.

John Edwards

##### Share on other sites
yep, it doesn't strictly increase or decrease but the point is that on one side it is positive and on other side it is negative, and it crosses zero on closest and farthest points. Same as with this dot product in the Eberly's algorithm you told about(btw, unless edge vector is normalized, it too isn't strictly increasing or decreasing). For binary search you only need sign, i.e. what vertice on the edge is closest to the circle center, value itself does not matter. Binary search works like that: take an interval that has positive value on one end and negative on other, split it in two halves and check whever value in center has positive value or negative. Use sub-interval that has different signs on ends. To find closest and not farthest point you need to choose "side" of interval that has closer distances.

Since you have Eberly's algorithm, i would recommend to try to look into it and understand. It should be trivial to change it to do what you want; i don't have this book nearby, but know approximately how it works.

##### Share on other sites
i did some searching and found algorithm that is mostly one you are referring to:
the algorithm
to adapt it to find edge that is closest to your point, instead of "edge vector points up", or "edge vector points down" just use "head of edge is closer to circle center than tail" and "head of edge is farther from circle center than tail" etc.
(and adapt algorithm to give out closest and second closest so you get edge (if you don't know how to do that, you can check what one of two vertices ajacent to closest vertices is closer, it'll be the second closest vertice))
edit: note, it will not work well for cases when circle center is inside polygon.

[Edited by - Dmytry on April 2, 2006 9:38:57 AM]

##### Share on other sites
Quote:
 Original post by PistachioPro@ jyk: I've looked around for information on Dobkin-Kirkpatrick hierarchies, and I found a lot of papers using them, but no information on how to build them. Do you have a link?
The only detailed references I'm aware of are books; I don't know of any good online references. In any case, the aforementioned binary search method might be just as effective.

There's also the question of whether the optimization is necessary; given an appropriate broad-phase step, it seems brute force might suffice.

##### Share on other sites
@Dmytry: I'm glad you showed me that link. I think one of my biggest problems figuring all this stuff out is that I must have misinterpreted the original David Eberly ExtremeVert function, because my code looks like this:

int ExtremeVert( const CVector2D& v ) const{    // Returns the index of the vertex whose projection is farthest along    // the given vector.    int i0 = 0, i1 = 0;    for( ;; ) {        int mid = MiddleIndex( i0, i1 );        if( v.Dot( m_vecBodyEdges[mid] ) > 0.0f ) {            if( mid != i0 ) { i0 = mid; }            else            { return i1; }        }        else {            if( v.Dot( m_vecBodyEdges[(m_nVerts+mid-1)%m_nVerts] ) < 0.0f ) { i1 = mid; }            else                                                            { return mid; }        }    }}

This works on many polygons (all the polygons I tested with), but it seems to break down when there are unequal numbers of "backwards"- and "forwards"- facing edges. When I tried to apply the same search framework to criteria other than "v.Dot( m_vecBodyEdges[mid] ) > 0.0f", the problem cropped up a lot more often. Since I thought the framework was right, I blamed the problem on the criteria, which has probably turned me away from several correct solutions.

@jyk: I figured you probably got it from a book ... oh well. As far as whether or not optimization is necessary, I figured that in a physics system such as the one described by Thomas Jakobsen, where constraints are satisfied through a method of relaxation that requires repeated overlap queries, a simple O(ln N) algorithm would save at least some time, overall. However, since it appears that there aren't any well known O(ln N) algorithms, and I'm getting kind of anxious to move on, I do plan on using an O(N) method.

Thanks again for the input, guys,

John Edwards