There is a simple mathematical problem that sometimes comes up in programming^{1}. The problem is:

Given two one-dimensional

^{2}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

comments powered by Disqus