There is a simple mathematical problem that sometimes comes up in programming1. The problem is:

Given two one-dimensional2 line segments, determine whether they intersect, i.e. have points in common.

Here's a graphical representation of the problem. The two segments are drawn one above the other for demonstration purposes:

At first sight, this looks like a problem with many annoying corner cases that takes a lot of dirty code to implement. But it turns out that the solution is actually very simple and clean. The two segments intersect if and only if X2 >= Y1 and Y2 >= X1. That's it.

It may be difficult to convince yourself this works by simply looking at the image above, so here is another that makes it much clearer:

In this image we see all the possibilities of the positions of the second segment relatively to the first. It should take only a few seconds to verify that the algorithm returns a correct result for all 5 cases.

Here's Python code that implements this solution:

def segments_intersect(x1, x2, y1, y2):
    # Assumes x1 <= x2 and y1 <= y2; if this assumption is not safe, the code
    # can be changed to have x1 being min(x1, x2) and x2 being max(x1, x2) and
    # similarly for the ys.
    return x2 >= y1 and y2 >= x1

1 I ran into it while implementing a binary application format reader, that needed to support insertion data records. Each data record has a start and an end (memory address). The problem comes up when testing whether two records collide.

2 One-dimensional here means that they only have a single coordinate, i.e. all can be laid down on a line that's parallel to one of the axes.


comments powered by Disqus