**
Collision Detection Technique for 2D Rotating
**

**Convex Polygon**
By Joshua Cantrell
concept last updated: 10-25-99
page last updated: 11-14-00

**INTRODUCTION**

After coming up with a method to stop objects moving in straight lines
from colliding with each other (read Collision
Detection Technique for 2D (Convex Polygon)), I was reminded that
sometimes an object must *turn*. This can happen both while moving
forward, making an arc like motion, or simply turning in place. This
can be solved in two ways:
- If you make a wide arc (large radius), you can approximate it with
movement in straight lines.
- Calculate an algorithm to best approximate this effect.

In my discussion on straight line collision detection, I was able to
find out exactly (or a close approximation due to numerical quantization
errors) where the two objects collided with each other. For turning
the solution of this question becomes more difficult, which in turn
means it is computationally complex. The good news is that it is
possible if you really need the information for your simulation.

**IDEAS BEHIND THE METHOD**

Using my previous article on 2D collision
detection as an introduction to the topic, I will be continuing
from where I left off. The question about collision due to moving
in an arc and turning in one place is certainly something which
can happen in any type of simulation. In fact, moving in higher
order curves is also a possibility (but too complex to really be
feasible)! There are two ways of approaching this problem:
- Look at the picture without modifying the coordinate space,
leading to brute force calculations for the collision.
- Transform the coordinates of the objects in space, to convert the
arc problem into a line problem, and then perform the
calculations as though the displacement was straight.

The first approach is easier to see from our perspective, and is also the
first way I will solve the problem. The second approach is much more
approximate, but is practical when the approximation is *acceptable*.
Modifying the environment to accommodate the previous algorithm rather
than fitting an algorithm to the environment has the
added benifit that it can be applied to many other problems where
an algorithm with a line-path is available, yet an algorithm for an
arc-path is desired.

**FUNDAMENTAL MATH CONCEPTS USED**

For both the first brute force approach and object transformation
methods, simple polar coordinate and trigonometric
math is required. In the brute force approach, finding the point
of collision is done through an algorithm which recursively approximates
the point of collision until the error becomes satisfactorily low.
It should be noted that finding the point of collision due to
rotation or arcing can be a computationally expensive process
compared to the process of actually detecting a collision. I have
tried to think of ways around this problem, but have not thought
of an answer yet. (Considering that I am not researching this topic
either, it may be this way for awhile.)

**FEATURES OF ROTATING/ARCING A 2D LINE SEGMENT**

The brute force method is composed of finding the path a line segment
travels in and then finding out if this path conflicts with another
object. Of prime importance is whether this path can be easily computed
given a reasonable amount of overhead.
What we need for this computation are as follows:
- Position of the center of the arc of rotation
- Rotation/transformation matrix
- Endpoints of the line segement.

Most of this information is easy to come by because it is already
needed to simply move the object in an arcing pattern. The position
of the center of the arc (the center of the object for turning in
place) is required in producing the rotation/transformation matrix
which is required to move the points of an object from the original
position to the new position.
Observe that the endpoints of the line segment are each a particular
distance from the center of rotation. Also notice that they are
*always* this distance from the center of rotation. This tells
us that as the line segment rotates the two points will both rotate
about the center in a normal circular fashion through a number of
degrees (or radians). Anything within the circle that an inner
point follows will not cause a collision. Anything beyond the
circle that an outer point follows will also not cause a collision.
Finally we need to determine if a collision occurs between the two
circles of rotation created by the two endpoints. This can be done
using the original line and rotated line. Anything *between*
these two line positions and inside the carefully chosen circle
boundaries (to match the movement of the corresponding endpoint)
is a collision point.
What is *between* the two line segments can be found by using
the dot product. Each line segment has a vector that represents the
direction it points. The dot product between this vector and a vector
formed between a point on the line segment and a point on the object
will return a positive or negative number depending on whether the
point on the object is *inside* or *outside*.

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

The brute force collision detection is done by moving each line segment
on the first object (as described above) and seeing if any of the points of
the second object collide. If none collide, then the transpose of the
matrix can be aquired and each line segment of the second object can
be tested against the first object. Note that this will only find any possible
point that could have collided. It doesn't say whether the point was the
first to collide or not, it only says it would have collided if the movement
had been carried out.
If the object(s) are moving around the center of rotation rather than on it,
some of the edges can be culled if it is determined that they couldn't
possibly result in a collision. Obviously, if an edge is rotating *through*
where the object had been previously, some other edge will collide before this
edge. It can then be ignored and reduce the number of edges checked. These
edges can be found by finding the vector representing the initial direction
of movement of the shape (tangent to the arc) and culling those edges pointing
in an opposite direction.

**2D CONVEX POLYGON ARCING/ROTATING COLLISION POINT FINDING**

Once a collision has been found, if you wish to find out where it occurred,
each point where a collision is found to happen must be traced backwards
to the location on the edge which caused the collision. The position on
the edge is found by taking the distance from the point to the origin
of rotation and forming a circle with it. Where this circle intersects
the edge is where the collision took place. The arclength which separates
the point and the edge is the distance traveled before the collision took
place. To find the first point of collision, the shortest arclength must
be found and chosen.

**MAKING THE ARC LOOK LIKE A STRAIGHT LINE**

When objects are undergoing large arc like motions, the amount they rotate per
amount traveled forward is very little. This allows us to approximate the
turning as a straight line if we move and translate the objects accordingly.
If the problem is translated into a straight line of travel problem, then we
can easily find out if there is a collision and the points of collision by
the old 2D collision detection method.
If we are given two objects, *O1* and *O2*, where *O2* is moving
in an arc towards *O1*, we can reposition *O1* so that moving *O2*
in a straight line closely mimics the same effects as encountered along the arc.
Here is what we need to do to *O1*:
- Rotate
*O1* to face *O2* in the same direction as it does when
*O2* sweeps by.
- Translate
*O1* to a position before *O2* where *O2* is closest
to *O1* while traveling in a straight line as it would be in an arc.
- Translate
*O1* to a position to the side of *O2*'s path so *O1*
is as distant from *O2* at the closest point in the arc as it is in the
straight line path.

The amount to rotate *O1* can be determined by the angle between the center
of *O1* to the origin of rotation and the center of *O2* to the
origin of rotation. Once this is found, simply rotate *O1* to face
*O2* using the proper 2D rotation matrix.
How far to place *O1* in front of *O2* can be determined by the
distance between the origin of rotation and the center of *O2* multiplied
by the number of radians that *O1* needed to be rotated in order to face
*O2*. This finds the arc length between *O2*'s position and the closest
point it swings by *O1*.
How far to place *O1* off to the side of *O2* can be determined by
the difference in the distances of each one's center from the origin of rotation.
It can be seen that this represents the closest that *O2* ever comes to
*O1*

**2D CONVEX POLYGON ARCING/ROTATING COLLISION DETECTION
(2nd Way)**

To find out if a collision occurs, simply do the transformation described
above, and use the standard straight line displacement collision detection.
Using this method, you can find a point of collision, and simply do a
reverse transformation on the point to find out where it is approximately
in the real world.

joshuacantrell@yahoo.com

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