2D visibility - segment sorting

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^[1] 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^[2] to understand why.

Links