I recently stumbled upon an elementary problem: I had to compute the intersection points of a line — actually, an affine function — and a rectangle. For that kind of simple geometric problem, I do not rush toward Google. I prefer to try to solve it myself, to keep my problem-solving mind sharp!
I made some drawings, found the corner cases, then an algorithm, and it was finished in no time.
I found the algorithm was simple and elegant, so I decided to check how it compared to other methods. Google led me to a Wikipedia list of algorithms solving this problem. I discovered that my solution was very close to Liang-Barsky algorithm apart from the fact that I was working with an infinite line when other methods are dealing with finite segments.
I was, however, surprised to see that the explanation of the algorithm was way more complicated than the naive intuition I had in mind when solving the problem myself. Here is an attempt to explain how I see Liang-Barsky algorithm and how one can code it with 3 lines of Python.
Note: That kind of geometric operation is typically used in graphics engines. In this context, the implementation needs to be as efficient as possible and leverage all kinds of tricks to be faster. The goal of this post is to focus on intuition and understanding rather than efficient implementation.
Let’s put some letters on the problem. I have an affine function parametrized by and that can be written as:
And a rectangle define by two points: .
On the figure, we see that the black line (our affine function) intersects with the rectangle when it crosses the vertical line and the horizontal line . The tricky point is that our function can cross any of the sides of the rectangle, and therefore we need to determine the ones in which we are interested. This is what the Liang-Barsky algorithm does.
Warning: A perfectly horizontal or vertical line is parallel to some of the rectangle sides. This known corner case is traditionally treated apart because its solution is straightforward. I did not mention it here to keep the code as simple as possible.
If we consider our function infinite, it always crosses all the sides of the rectangles — if we consider them infinite too. We have therefore 4 intersections, with , , , and .
From left to right along the -axis, the first and last intersections are always outside of the rectangle. This is the principle on which relies the Liang-Barsky algorithm.
And that’s it!
Note: I assume here that the line does not miss the rectangle. A simple trick can test this. Looking at the first two points, sorted from left to right again, one of them must cross a -line, and the other an -line, in any order. If the line cross two -lines first, it means that it is evolving in the domain above or below the rectangle for the rest of the graph.
Let’s now code it! Using the sorted function of Python, this is trivial!
def line_x_rectangle(a, b, x_min, y_min, x_max, y_max): # Intersections of f(x) = ax + b with the rectangle. (x, y, axis) p1, p2 = (x_min, a * x_min + b, 'x'), (x_max, a * x_max + b, 'x'), p3, p4 = ((y_min - b) / a, y_min, 'y'), ((y_max - b) / a, y_max, 'y') # Python sorts them using the first key p1, p2, p3, p4 = sorted([p1, p2, p3, p4]) # Check if there is an intersection, returns the points otherwise if p1 == p2: return None return p2[:2], p3[:2]
Now that you have this intuition in mind, I invite you to take a look at the Wikipedia implementation and it should appear clearer. Do not hesitate also to compare this explanation to other available on the web, it is always better to find the explanation that better suits you.