# 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[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.

Email me , or tweet @redblobgames, or comment: