Line Segments

Heim kommt man nie. Aber wo befreundete Wege zusammenlaufen, da sieht die ganze Welt für eine Stunde wie Heimat aus.

– Hermann Hesse, Demian

The Intersection Problem

In this tutorial, we want to improve on the collision detection algorithm used in the Kicker-demo from previous tutorials. The issue can easily be restated as a line, or segment, intersection problem: As an object moves with a certain velocity, the velocity vector, with origin at the current position of the moving object, leads the way to wherever the object is going to.

Once we know that two line segments actually intersect, computing the intersection point is as trivial as solving a system of two linear equations. The hard part is to determine whether two line segments actually intersect, as segments are finite, thus, while the lines they run along on might intersect, the actual segments might not, as shown in the next figure:

Parametric Representation

To facilitate working with line segments, we will use the parametric representation of lines and segments. Basically, you can imagine a segment as the way between two points. Let be the start of a segment and the vector joining the point to its designated end point, also called a direction vector, think of your home and a grocery store, for example, then, at the time you are at home and at the time you are at the grocery store. For all values in between, you are en route to the store. In formulas, this idea looks as follows:

basically defines an offset, i.e. where the segment starts, away from the centre of the coordinate system, and encodes how far we have to run along a given direction vector. Refer to this GeoGebra applet by Tim Brzezinski to see a parametric representation in action.

Intersection

To figure out whether two segments and , with and are intersecting each other, it is enough to solve the equation and check whether and are both between and :

In matrix notation, this reads as follows: , where , with , , and .

Colinearity

Now if and are linearly dependent, there is no need to test for intersection if and aren’t already on the same line. It is thus enough to check whether lies on or vice versa, which means that it is enough to check whether there exists a such that , i.e. it is enough to check whether the directional vector between the two points and is collinear with the vector .

If the determinant of the matrix is not zero, then the vectors can’t be collinear. If the determinant is zero, all that is left to do is to check whether there exists such a between and .

Linear Independence

Now if the two directional vectors are linearly independent, the matrix is regular and the above matrix equation can easily be solved by computing the inverse of the matrix :

Example

Let , , and , as depicted in the figure below:

In this example, we have and . The inverse of is

thus

Plugging into the equation of , we get

as desired, which tells us that if we run three quarters of the length of the segment from to its end point, we intersect the other segment .

Implementation

To define line segments in C++, we use a small class:

class LineSegment2D
{
private:
  Vector2F startPoint, endPoint;      // the start and ending point of the line segment
  Vector2F directionVector;        // the vector joining those two points
  Vector2F normalVector;          // the normal vector of the line segment

public:
  LineSegment2D();
  LineSegment2D(Vector2F startPoint, Vector2F endPoint);
  LineSegment2D(Vector2F startPoint, Vector2F endPoint, Vector2F normalVector);
  ~LineSegment2D() {};

  void setStartingPoint(Vector2F vector) { startPoint = vector; };
  void setEndPoint(Vector2F vector) { endPoint = vector; };
  void projectToVector(const Vector2F& vectorToProjectOn);
  void recomputeDirectionalVector(float radius = 1.0f);

  const Vector2F getDirectionalVector() const { return directionVector; };
  const Vector2F getNormalVector() const { return normalVector; };
  const Vector2F getStartPoint() const { return startPoint; };

  friend class Geometry;
};

Both constructors compute the directional vector and the first constructor computes the normal vector (clockwise) as well:

LineSegment2D::LineSegment2D(Vector2F startPoint, Vector2F endPoint, Vector2F normalVector) : startPoint(startPoint), endPoint(endPoint), normalVector(normalVector)
{
  this->directionVector = endPoint - startPoint;

  // normal vector: (-dy,dx)
  this->normalVector = Vector2F(-directionVector.y, directionVector.x);
  this->normalVector.normalize();
}

LineSegment2D::LineSegment2D(Vector2F startPoint, Vector2F endPoint) : startPoint(startPoint), endPoint(endPoint)
{
  this->directionVector = endPoint - startPoint;

  // normal vector: (-dy,dx)
  this->normalVector = Vector2F(-directionVector.y, directionVector.x);
  this->normalVector.normalize();
}

The recomputeDirectionalVector method is used to get the direction vector from the centre of a ball to the edge of its radius:

void LineSegment2D::recomputeDirectionalVector(float radius)
{
  this->directionVector = this->endPoint - this->startPoint;
  if (this->directionVector.x == 0 && this->directionVector.y == 0)
    return;
  this->directionVector.normalize();
  this->directionVector *= -1.0f*radius;
}

Note the negative sign in the normalization of the vector. This is due to the base change between standard coordinates and screen coordinates.

The actual test for intersecting between two segments follows the mathematics explained above:

bool Geometry::segmentIntersection2D(const LineSegment2D& segment1, const LineSegment2D& segment2, Vector2F* t)
{
  // compute the determinant of the 2x2 matrix
  float det = segment1.directionVector.x * segment2.directionVector.y - segment1.directionVector.y * segment2.directionVector.x;

  // if det is 0, the directional vectors are colinear
  if (det == 0)
    return false;

  // compute directional vector between the two starting points
  Vector2F directionalVector = Vector2F(segment2.startPoint.x - segment1.startPoint.x, segment2.startPoint.y - segment1.startPoint.y);

  // compute t1
  float t1 = segment2.directionVector.y * directionalVector.x - segment2.directionVector.x * directionalVector.y;
  t1 /= det;

  // if t1 is not between 0 and 1, the segments can't intersect
  if (0 > t1 || t1 > 1)
    return false;

  // compute t2
  float t2 = -segment1.directionVector.y * directionalVector.x + segment1.directionVector.x * directionalVector.y;
  t2 /= det;

  // if t2 is not between 0 and 1, the segments can't intersect
  if (0 > t2 || t2 > 1)
    return false;

  // else return true
  if (t != NULL)
  {
    t->x = t1;
    t->y = t2;
  }
  return true;

}

And all of this greatly simplifies the collision detection test of the Kicker-demo:

util::Expected<void> PlayState::update(const double deltaTime)
{
  if (isPaused)
    return { };

  // update the ball and table
  ball->update(deltaTime, table->frictionCoeffK);

  // check wall intersections
  int i = -1;
  for (auto wall : table->walls)
  {
    i++;
    if (i != collision)
    {
      if (mathematics::Geometry::segmentIntersection2D(*wall, *ball->direction))
      {
        mathematics::reflectionVector(ball->velocity, wall->getNormalVector());
        collision = i;
        break;
      }
    }
  }

    ...

    // return success
  return { };
}

---

While these new ideas greatly improved on the previous algorithms, this is far from being the entire story. In a later series of tutorials about Computational Geometry, we will explore topics such as this in greater mathematical detail.

---

References

• Geogebra
• Tricks of the Windows Programming Gurus, by A. LaMothe
• Wikipedia