Computational Geometry primer

In this series of tutorials we will try to cover some basic mathematic algorithms needed in computer graphics and games. No need to be afraid if math is not your strong point. We will not delve with high level calculus and any scary science. We will instead use some high school math and geometry in order to explain the algorithms and then the code we will develop will be ready to use as is. Just copy and paste into your projects and you are done. Here we go then.

1. Line segments intersection

The first thing we are going to cover is the intersection of two line segments. Many of the algorithms in computer graphics are based on this, so I believe that it is one of the most important algorithms.

First let's see the possible relative positions of two line segments. As shown in the figure there are six possible positions. The first three produce an intersection point and the other three don't. In the first case the intersection lies within either segment. In the other two the intersection point is the end point of at least one segment. Among the three cases that the segments do not intersect the first two represent lines that intersect but outside the segments while the third represents parallel lines.

Depending on the problem we want to solve we either care if the two segments intersect or even for the exact intersection point. When we check for collision between objects it is enough to know if we have intersection. But when we want to calculate the damage we need to know the exact point of the collision hence the intersection point.

From geometry we know that two points determine a line. The equation of the line between points p1 and p2 is

pa = p1 + na * (p2-p1)  (1)

Equally for the other line we have

pb = p3 + nb * (p4-p3)  (2)

If the intersection point lies within both segments then ua and ub must be between 0 and 1. Solving the two equations for ua and ub we find:

We notice that both factors have the same denominator. If it is 0 the intersection point is infinite aka the lines are parallel. If any of the values na or nb is less than 0 or greater than 1 the intersection point lies outside the corresponding segment. The coordinates of the intersection point are given by the formulas:

class clf_point2D{
public:
	float x;
	float y;
	clf_point2D():x(0.f), y(0.f){
	}
	clf_point2D(float _x, float _y):x(_x), y(_y){
	}
	clf_point2D(clf_point2D& p) : x(p.x), y(p.y){
	}
	~clf_point2D(){
	}
};

bool intersect(const clf_point2D& p1, const clf_point2D& p2, const clf_point2D& p3, const clf_point2D& p4, clf_point2D& p0)
{
	// first calculate the common denominator
	float d = (p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y);
	if (fabs(d) < 0.00001) // almost 0 (compensate for computer accuracy
		return false;
	// calculate fractional part for x coordinate
	float na = ((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x))/d;
	if (na < 0 || na > 1.f)  // beyond limits in x, search no more
		return false;
	// calculate y fraction
	float nb = ((p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x))/d;
	if (nb < 0 || nb > 1.f)  // beyond limits in y, search no more
		return false;
	// we have intersection, calculate actual coordinates
	p0.x = p1.x+na*(p2.x-p1.x);
	p0.y = p1.y+na*(p2.y-p1.y);
	// return true
	return true;
}

This little algorithm is very useful when checking for collision between objects in two dimensions. There are also many problems in the three dimensional world than can be simplified to two dimensional collision detection. For these reasons and any more you can think of this algorithm is one of the most basic algorithms in computational geometry.

Continue to part 2, Point in polygon check