**
Collision Detection Technique for 2D
**

**Convex Polygon**
By Joshua Cantrell
previously updated: 9-22-99
minor update: 2-28-03

**INTRODUCTION**

Even with the event of graphics acceleration cards, I don't know of any
helper cards for collision detection. (I assume that is the next step.)
For this reason, it makes sense that I must design my own routines to
detect and handle collisions of freeform objects moving in a dynamic
world. I certainly don't want object bouncing around at great distances
from each other, or just as bad, flying right through each other without
flinching!

**IDEAS BEHIND THE METHOD**

After much thought on the issue, I decided to go back to basic 2D math
relationships. This has to do with points, lines, and vectors. The
reason why I decided to start simple was that sometimes I find it easier
to build complex algorithms from simpler identities and algorithms. If
you can be assured of successful implementation of simple algorithms and
build upward with success at each step, then the finished product
is sure to work! :-)
My discussion starts with the intersection of two line segments. Then I
move on to whether or not a point exists within a bounded convex polygon.
Then I finally discuss how collision detection can be done given a
displacement vector.

**FUNDAMENTAL MATH CONCEPTS USED**

Without the understanding of certain math concepts, it may hard to
understand everything that goes into collision detection. This is one
reason why I think good programmers should feel comfortable with math.
(It's only an opinion, so don't jump on me if you hate math.)
Recall that the *dot product*, *u*.*v*, is equal to
**||***u*||*||*v*||*cos(theta) where **||***u*||
represents the magnitude of the vector *u* and **theta**
is the angle between the vectors *u* and *v*.
The *cross product*, which I'll symbolize as *u*X*v*
results in a vector that is orthogonal (perpendicular) to the vectors involved
in in the operation. The magnitude of the vector is given by
**||***u*||*||*v*||*sin(theta) where **theta** is the
angle between the vectors moving in the direction from *u*
to *v* (the right hand rule). The cross product doesn't
have much meaning in 2D, but the magnitude is extremely useful because
of the sin(theta). Since any two vectors (not pointing in the same
direction) on the 2D xy-plane will always point along the z-axis, the
cross product easily provides us with the magnitude and direction of
the vector. If the resultant vector points along increasing z, then
**theta** must be between 0 and 180 degrees (0 and PI radians).
A vector pointing along decreasing z means **theta** must be between
180 and 360 degrees (PI and 2*PI radians).
The cross product can be understand by using the the right-hand rule. Point
your hand in the direction of the *u* vector, then bend your fingers
in the direction of the *v* vector, and keep your thumb pointing up,
perpendicular to your hand and finger directions. Unless you are double
jointed (bending your fingers backward), you'll either have to point your
thumb up or down. :) Up is positive, and down is negative. Remember to use
your *right* hand! Doing this might help you visualize how some of
the vector math works.

To find the point where two lines intersect, simply solve the system
of equations. You have two equations and two unknowns. This can be
solved through either substitution (my favorite), or setting up the
following linear algebra equation and solving for **x** and **y**.

** [A1, B1] [x] [C1]
[A2, B2] * [y] = [C2]
**

**INTERSECTION OF 2D LINE SEGMENTS**

There are two steps to find an interesection of two 2D line segments.
They are:

**1)** Find the intersection of the two lines.
(Solve system of linear equations.)

**2)** Determine if the point is between the endpoints of both line
segments.

**POINT IN 2D CONVEX POLYGON**

For each side of the 2D Convex Polygon, you must determine if the point
is on the inside or outside of a side. This is done using the cross
product. If we move clockwise around the polygon forming vectors,
and take the cross product of these with a vector formed from a point
on the same side to the desired point, we can know if it is on the
inside or outside by the sign of the resultant vector's direction along
the z-axis.

If it's increasing (symbolized by the dot with a circle around
it) it's coming towards us, and it's outside. If it's decreasing (symbolized
by a cross with a circle around it) it's going away from us, and it's inside.
If the point is found to be inside all of the sides, it is inside the
polygon, otherwise it is outside the polygon.

**2D CONVEX POLYGON COLLISION DETECTION (1st Way)**

Collision detection can be done in two ways. Either determine whether
two polygons overlap after being moved, or if a moving polygon intersects
another polygon.
I prefer the latter because it insures that objects will not skip through
other objects if they travel at extraordinary speeds.

Given the two objects and their displacement vector, all sides pointing
away from the direction of displacement are culled away. We can do this
in part because we make the assumption that the objects are not already
intersecting each other. This means only a change in position could
cause them to collide and whatever doesn't move won't make a difference.
The endpoints from the culled sides then become points of new sides formed
by moving all the remaining points by the displacement vector.

The last step is simply to first check and see if any of the line segments
forming the sides intersect. If any of them do, a collision was detected.
If none intersect, there is still one possibility which is that the object's
region of displacement enveloped the other object, so simply test to see
if one of the other object's points is in the region of displacement. If one
of them is in there, they must all be in there and a collision occured!

**2D CONVEX POLYGON COLLISION DETECTION (2nd Way)**

There is yet a second way to find out if two polygons have collided with each
other. First cull the vertices from both objects which are not connected to
a side that can cause a collision. The moving object
has the sides pointing away from the motion removed, and the stationary object
has the sides pointing in the direction of motion removed.

To perfrom the culling, you take the cross product of the edge's vector with
the displacement vector, you'll get either a positive or negative value. If
all the edge vectors are aligned in the same direction around the polygon, then
this cross product will produce one sign for facing the displacement and the
other sign for facing away from the displacement. You only need to be concerned
with the ones facing the displacement.
Line segments are now created starting from each remaining vertice. The
line segments are created by finding a second point through the following
processes: (1) Vertices on the moving object are added to the displacement
vector. (2) Vertices on the stationary object are added to the negative of
the displacement.

These line segments are then tested for collision with the unremoved sides.
Any intersection means that a collision has occured. The bonus about this
method of collision detection is that you can find out where the collision
occured. By comparing the distances from the points of collision to the
original vertices that caused the them, you can find out which vertice
was the first to collide. The vertice that traveled the shortest distance
wins!

**2D CONVEX POLYGON COLLISION REGION FINDING**

Once a collision has been found, if you wish to find out where it occurred,
the second collision detection technique should be used. This not only
tells you that the collision occured, but where it occured.

joshuacantrell@yahoo.com

(My Home Page)
- (My Computer Science Page)
- (My Personal Page)
- (My Resume)