2d visibility - segment sorting

from Red Blob Games
July 2012

While working on the 2d visibility demo, I wrote some code in Visibility.hx that I wasn’t sure about. I had written it as:

   private function _segment_in_front_of(a:Segment, b:Segment, relativeTo:Point):Bool {
        var A1 = leftOf(a, b.p1);
        var A2 = leftOf(a, b.p2);
        var A3 = leftOf(a, relativeTo);
        var B1 = leftOf(b, a.p1);
        var B2 = leftOf(b, a.p2);
        var B3 = leftOf(b, relativeTo);

        // NOTE: this algorithm is probably worthy of a short article
        // but for now, draw it on paper to see how it works. Consider
        // the line A1-A2. If both B1 and B2 are on one side and
        // relativeTo is on the other side, then A is in between the
        // viewer and B. We can do the same with B1-B2: if A1 and A2
        // are on one side, and relativeTo is on the other side, then
        // B is in between the viewer and A.
        if (B1 == B2 && B2 != B3) return true;
        if (A1 == A2 && A2 == A3) return true;
        if (A1 == A2 && A2 != A3) return false;
        if (B1 == B2 && B2 == B3) return false;


I had convinced myself on paper that this was correct, at least in the cases I care about. However, John N asked about this function and I decided to look at the function again to see if I could find any bugs and maybe write it to be more clear.

Here’s the original algorithm. You can adjust the A and B lines (which determine a1, a2, b1, b2), and then it shows you the areas where relativeTo might be (which determines a3, b3):

There are definitely places where neither A nor B is closer, but the algorithm arbitrarily decides. Here’s an algorithm that is better about this, although I think it doesn’t work any better in practice in the context of the visibility algorithm:

(Note: for this diagram I didn’t spend the time to make all cases work; I just wanted to write something quickly that showed how this function works.)

Note that although this code is simple, in practice it may have artifacts. See these notes to understand why.

Email me at , or tweet to @redblobgames, or post a public comment: