RiK0 Tech Temple: Geometry/graphics algorithms: segment intersection

With modern gaming libraries dealing with most geometric/graphics issues, it is probably possible to create simple (and not so simple) games without a clue on the basics of computational geometry. However, the elementary algorithms are really so simple that it is worth to keep them in mind nonetheless.
First, I will briefly review some mathematical concepts we will be using, then I will present the algorithms. In this post I will present algorithms to find if two consecutive segments represent a left or a right turn and to discover whether two segments intersect.
The segment intersection is probably the single most important operation: for example it can be used as a building block to detect collisions in a 2D-game and can be generalized to work with 3D games as well.

Magic of the cross product

For those who thought that they belonged to somewhere else during the geometry classes (or who profoundly hated trigonometry) this will be short. Moreover, we won't use sin and cos since they are extremely slow operations. Nor will we use divisions (as they are both slow and yield to potentially badly conditioned algorithms).

Let A and B two vectors, that is to say two segments with the origin in the origin of the system (0, 0). Their cross product A x B is defined as:

Physics (and mathematicians) would say that A x B is a vector perpendicular to both A and B (thus not contained in the considered 2D plane) according to the right hand rule and with magnitude |x_Ay_B-x_By_A|. However, we are only interested in the sign:

If the cross-product is negative, then A is counterclockwise from B
If the cross-product is 0, then A and B are collinear
If the cross-product is positive, then A is clockwise from B

Our second step is to consider pairs of segments with one end in common. Let s=CA and t=CB (CA and CB should have a bar above, but I can’t do that for typographical reasons) be the segments, where A=( x’s, y’s), B=( x’t, y’t) and C=(x, y).
We know how to compute whether the segment CA is clockwise from the segment CB, that is to say:
As a consequence:

If the cross-product is negative, then CA is counterclockwise from CB
If the cross-product is 0, then CA and CB are collinear
If the cross-product is positive, then CA is clockwise from CB

Turn left or turn right?

Now, given the consecutive segments AB and BC, we want to find out whether going into BC is a left or a right turn. A simple schema clarifies the thing.

Essentially we can compute the cross product ACxAB in order to discover if BC is a left or right turn with respect to AB. This is a very important building block to compute the segment intersection.
We notice how we did not use sin, cos or divisions. We have simply a bunch of multiplications, sums and subtractions. It is even likely that some architecture can perform the determinant of a matrix with a single operation.

Segment intersection

At this stage, we can introduce the code to compute the segment intersection. First I present the function computing the direction between two given segments. Considering that we do not want to make this functions dependent from the specific representation of segments, we just let it take the points A, B and C.
The function uses only multiplications, additions and other elementary inexpensive operations (no divisions, no cos or sin). The basic idea is using the simple function we defined in the last section and eventually deal with the special case when one segment end lies on the other segment.

So, the function is:

def direction(origin, first, second):
    return cross_product(second-origin, first-origin)

provided that we represented points like that:

import collections

def cross_product(lhs, rhs):
    return lhs.x * rhs.y - lhs.y * rhs.x

class Point(collections.namedtuple('Point', 'x y')):
    def __add__(self, other):
        return Point(self.x+other.x, self.y+other.y)

    def __sub__(self, other):
        return Point(self.x-other.x, self.y-other.y)

def direction(origin, first, second):
    return cross_product(second-origin, first-origin)

Notice the use of named tuples here. We have efficiency of tuples and ease of use of regular classes. But this is another story. Then, we have the real thing:

def does_intersect(first_start, first_end, second_start, second_end):
    direction_1 = direction(second_start, second_end, first_start)
    direction_2 = direction(second_start, second_end, first_end)
    direction_3 = direction(first_start, first_end, second_start)
    direction_4 = direction(first_start, first_end, second_end)

    if (direction_1 * direction_2 < 0
        and direction_3 * direction_4 < 0):
        return True
    elif direction_1 == 0 and on_segment(second_start, second_end, first_start):
        return True
    elif direction_2 == 0 and on_segment(second_start, second_end, first_end):
        return True
    elif direction_3 == 0 and on_segment(first_start, first_end, second_start):
        return True
    elif direction_4 == 0 and on_segment(first_start, first_end, second_end):
        return True
    else:
        return False

What do we mean? direction_1 tells us "on which side" the start of the first segment is with respect to the second segment. On the other hand, direction_2 tells us on which side the second segment end lies. If both points are on the same side (they are both left turns or right turns), then the two segments do not intersect. But if the extremes of the first segment are on different side of the second segment and the extremes of the second segment are on different sides of the first segment, then it means that the two segments must have an intersection. The rest of the procedure deals with collinear segments: in this case some extreme of one segment must lie on the other segment. The last procedure is:

def on_segment(origin, first, second):
    if (min(origin.x, first.x) <= second.x <= max(origin.x, first.x)
        and min(origin.y, first.y) <= second.y <= may(origin.y, first.y)):
        return True
    return False