Fast detecting of line segment and rectangle intersection, trough Cohen–Sutherland algorithm

Question

I have joined the community inspired by the following question/answers: Line intersection with AABB Rectangle?

There, the original poster asked for a way to detect intersection between a line and a rectangle. One of the answers mentioned that using Cohen–Sutherland algorithm would be much faster than doing 4 Line-to-Line intersections. However, the explanation on how to do was absent (or at most, vague), and while I could find info on that theorem, I didn't find any further explanation/code examples on how to adapt it for the question at hand.

So, I come to you asking a charitable soul for more information, possibly a C#, JavaScript or pseudo-code example, of how could one use Cohen–Sutherland algorithm to efficiently detect the intersection between a line and a rectangle. If there is another fast way of doing that with other algorithm that I am not aware of, I would welcome enlightenment.

Many thanks

There are numerous references on the web,even the link wo the wiki article in the original reference... What are you exactly looking for then? — , Sep 28 '15 at 01:00
Hi, thanks for your comment. So, there are numerous code references about many other uses of Cohen-Sutherland algorithm, like for screen clipping. Not for what I described, i.e. for testing if a line intersects a rectangle. — MAnd, Sep 28 '15 at 04:52
But... for this algorithm screen is just rectangle, isn't it? — MBo, Sep 28 '15 at 06:37
Hi @Yves Daoust, hmm I thought I had mentioned it's line segment. Sorry If it ended up being confusing. — MAnd, Sep 28 '15 at 10:12

score 1 · Answer 1 · 2015-09-28T10:32:21.650

My favorite solution is not classical. It relies on the concept of Minkowski sum, aka dilation.

The main idea is that detecting intersection of the rectangle with a line segment is the same as detecting inclusion of a segment endpoint in the sum of the rectangle and the segment. (You erode the segment in the direction of the line at the same time as you dilate the rectangle).

As you see, the sum is an axis-aligned hexagon, which can be seen as a bigger rectangle (the original window enlarged by the size of the segment bounding box) frow which two triangles have been cut out.

By a process of dichotomy, you can tell if the point is inside the hexagon by three tests exactly (checking on what side you are of the line through opposite vertices; hexagon => quadrilateral => triangle). This is not the preferred way as most of these lines are oblique and have a full equation.

It is usually better to first check insideness to the bigger rectangle, which allows fast rejection in four comparisons, then compare against the two hypothenuses of the triangles.

For the segment AB and window [X0,X1]x[Y0,Y1], the discussion will be like

if Xb > Xa and Yb > Ya:
    # NW-SE segment
    Dx= Xb - Xa; Dy= Yb - Ya
    if Xb < X0 or X1 + Dx < Xb or Yb < X0 or Y1 + Dy < Yb:
        # No intersection (no overlap between the bounding boxes)
    else
        if LeftOf(Xb, Yb, X0, Y0, X1 + Dx, Y0 + Dy):
            # No intersection, inside the NE triangle
        else if LeftOf(Xb, Yb, Dx, Y1 + Dy, X0, Y1):
            # No intersection, inside the SW triangle
        else:
            # Intersection, inside the hexagon
...

The function LeftOf computes the sign of the area of the triangle formed by three points (well-known determinant formula).

The discussion must be continued for all quadrants, and simplifications are possible for horizontal/vertical segments. Also note that

X1 + Dx < Xb

is just

X1 < xa

Many thanks, Yves, for your solution. I will put it to test. Still, I am afraid it sounds more costly in terms of processing time than the usual Cohen–Sutherland. Take, for instance, the LeftOf(), that would be called eight times at total. Let's see. In any case, I would upvote you, but the website doesn't allow me for the lack of reputation — MAnd, Sep 28 '15 at 22:25
Not at all. The block of code needs to be replicated four times, but only one instance is ever invoked. In addition, the big bounding box test avoids calling LeftOf in a significant proportion of the cases (say 50%). Lastly, if the first LeftOf returns true, the other is unnecessary. This put together, LeftOf is invoked less than once per segment on average (not 8 times) ! Contrary to your belief, this algorithm is much more efficient than Cohen–Sutherland. It doesn't even perform divisions ! — , Sep 28 '15 at 22:39
Update: as the triangle hypothenuses are parallel, the second LeftOf test can be computed a little faster (if at all). — , Sep 29 '15 at 07:32
Ha, thanks for the additional explanation. I will give it a try. However, I have to admit that I am struggling to properly understand a few things. The first is the first part, on how to get the window given the position and rotation o the rectangle and of the line. Second thing, I am still a bit confused on how to extend the discussion to the other quadrants, but I can still do some try-and-error there. To sum up, I am still trying to put this up; it's not as intuitive to put in code as it sounds. I will be back later — MAnd, Sep 29 '15 at 15:39
The window computation is in the code (Dx, Dy). Unfortunately I have no time for the moment to provide a complete version. — , Sep 29 '15 at 15:42

score 0 · Answer 2 · answered Sep 28 '15 at 22:30

While I wait for more answers to drop in, I thought I should bring the solution I myself have implemented in the meanwhile. I'm not 100% sure it works perfectly (i.e. that it handles all cases), but so far it seems to have worked for me. Notice it is a quite simple solution, so criticism is welcome..

Let r[1:4] be the vertices of the rectangle and p[1:2] be the vertices of the line segment. Then, in C#:

bool DoLineRecIntersect(Vector2 p1, Vector2 p2, Vector2 r1, Vector2 r2, Vector2 r3, Vector2 r4)
{

    if(p1.x > r1.x && p1.x > r2.x && p1.x > r3.x && p1.x > r4.x && p2.x > r1.x && p2.x > r2.x && p2.x > r3.x && p2.x > r4.x ) return false;
    if(p1.x < r1.x && p1.x < r2.x && p1.x < r3.x && p1.x < r4.x && p2.x < r1.x && p2.x < r2.x && p2.x < r3.x && p2.x < r4.x ) return false;
    if(p1.y > r1.y && p1.y > r2.y && p1.y > r3.y && p1.y > r4.y && p2.y > r1.y && p2.y > r2.y && p2.y > r3.y && p2.y > r4.y ) return false;
    if(p1.y < r1.y && p1.y < r2.y && p1.y < r3.y && p1.y < r4.y && p2.y < r1.y && p2.y < r2.y && p2.y < r3.y && p2.y < r4.y ) return false;


    float f1 = (p2.y-p1.y)*r1.x + (p1.x-p2.x)*r1.y + (p2.x*p1.y-p1.x*p2.y);
    float f2 = (p2.y-p1.y)*r2.x + (p1.x-p2.x)*r2.y + (p2.x*p1.y-p1.x*p2.y);
    float f3 = (p2.y-p1.y)*r3.x + (p1.x-p2.x)*r3.y + (p2.x*p1.y-p1.x*p2.y);
    float f4 = (p2.y-p1.y)*r4.x + (p1.x-p2.x)*r4.y + (p2.x*p1.y-p1.x*p2.y);

    if(f1<0 && f2<0 && f3<0 && f4<0) return false;
    if(f1>0 && f2>0 && f3>0 && f4>0) return false;

    return true;

}

Fast detecting of line segment and rectangle intersection, trough Cohen–Sutherland algorithm

2 Answers2