Sign in to follow this  

2D collision detection of a region

Recommended Posts

bkenwright    122
Hi all, I'm wondering about how I do a collision detection of a closed region...a shape for example made up of lots of points..... and how I would go about checking if a point is within this closed region. Is there any tutorials or specific algorithms on this topic? Or an idea of how I would go about doing it. Thanx Ben

Share this post

Link to post
Share on other sites
RabidCow    181
Here's a couple algorithms I can think of off the top of my head:

Assuming your points define a convex polygon, you can use the use the Z-value of the cross product to determine what side of each edge your point is on.

Or you could trace a line from your point out to infinity, and if that line crosses an odd number of edges, then it is inside the region.

Other than that, you might want to search Google for filling algorithms. The second one I mentioned is based on parity filling, and I think the first one is called the turns algorithm, but I'm not sure.

Hope that helps.

Share this post

Link to post
Share on other sites
bkenwright    122
Hi RC,
well I've been trying to do a demo in 2D...something simple...was trying simple you could determine which side of the line the point was on etc...but this only seems to work for simple square like shapes...won't work for complex wormy paths.
Now I'm looking around for some simple algorithms on convex testing....just thought there might be an easy solution it it :-/

Share this post

Link to post
Share on other sites
tekno    124
So now you are looking for an algorithm for convex testing?

Well if P[1..N] are the corners of your polygon, then if for all i, 1 less or equal i less or equal N, the following holds:
Q[i] times Q[i+1] > 0
With Q[i]=(P[i]-P[i-1])x(P[i+1]-P[i]).
With P[I+N] = P[I] and P[0] = P[N]
Then the polygon is convex, else it is concave.

For a convex polygon one can easily check if a point is inside the polygon:
A given point X is inside the convex polygon if for all i, 1 less or equal i less or equal N, Q[i] has the same sign.
with Q[i] = (P[i]-X)x(P[I+1]-X)
With P[I+N] = P[I]
Else it is outside the polygon.

If the polygon is concave, you can try to split it up in multiple convex polygons and test if the point is in one of the convex polygons.
Or you can use the odd-even rule, which says:
Given a point X, draw a line from X to a point far away and count the number of times you go through an edge of the polygon. If the number of edges you cross is even, then the point is outside of the polygon. If the number of edges you cross is odd, the point is inside the polygon.

When Implementating this algorithm you should note that problems can occur if your line goes (almost) through one of the corners of the polygon. The corner should only be counted as one edge! Floating point approximation faults could cause unintended behaviour ! But that just implementation :).

Then the last thing I will enter here:
Splitting a concave polygon into convex polygons.
When looking at a polygon from a given view, with a given order of vertices, polygons will either flow clockwise or counter-clockwise as the edges are traversed. If you take the sum of all the cross products of each pair of adjacent edges, this vector sum will point in the direction of the surface normal. If a polygon has a concave portion, two edges in this concavity will have a cross product that is in the opposite direction of the convex surface, given that there is a surface normal direction specified for the convex surface in creation. If such a 'concave corner vertex' is reached, a temporary edge is constructed between the 'concave' vertex and the starting vertex. If the resultant polygon containing the traversed edges and the new edge is a concave polygon (again using cross product testing), or if the new edge intersects an existing edge anywhere in the polygon, the starting vertex is dropped from the traversal list, and the remaining polygon is recursively tested for convexity. If the resultant polygon is convex, the next vertex outside the traversal list next to the starting vertex is added to the list and becomes the new starting vertex, and the polygon is recursively tested for convexity. The newly formed polygon is now in its largest convex form containing the original starting vertex. This polygon is output from the algorithm and the remaining vertices are recursively tested in this manner.

This methode does produce convex polygons, but it does not always give the mathematically perfectly minimal polygon count in many cases. When you start the algorithm at every vertex, then you can compare the number of polygons and use the one with the best result.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this