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.