# Comparison of two line segments along a ray

I have a point $q$, a ray $L$ (halfline which is cast from $q$) and two non-intersecting (intersection is only possible at endpoints) line segments $s_1, s_2$. I want to efficiently compute which of the two line segments along the ray $L$ is visible ("comes first").

I found the following description of a possible solution:

Why are at most five orientation predicates sufficient? I tried it on a few examples but can't convince myself fully.

The best way to see this is to describe the algorithm more carefully:

Pick one of the segments, say $s_1$. First, we test the orientation of the points $a_2,b_2$ w.r.t. $s_1$. If both lie on the same side of $s_1$, we test the orientation of $q$ w.r.t. $s_1$. Then, we have two cases:

1. $q$ lies on the same side as $a_2,b_2$. This means $s_1$ is further away, as your figure shows.
2. $q$ lies on the other side as $a_2,b_2$. This means $s_2$ is further away, which can also be seen from the figure, with a little imagination.

If $a_2$ and $b_2$ do not lie on the same side w.r.t. $s_1$, note that, since $s_1$ doesn't intersect $s_2$, it follows that $a_1,b_1$ are on the same side w.r.t. $s_2$!

So, we now only need to test whether $q$ lies on the same side as $a_1$, w.r.t. $s_2$: If it does, $s_2$ is further. If it doesn't, $s_1$ is further.

So, we have exhausted all possibilities and determined which segment is further using only four orientation tests! (In the first case, we test $a_2,b_2,q$ w.r.t. $s_1$ and in the second $a_2,b_2$ w.r.t. $s_1$ and $q,a_1$ w.r.t. $s_2$) So, we were able to improve upon the given $5$ in the description, by postponing the testing of $q$, such that $q$ only has to be compared to one segment and not $2$.

(Note that in the given configuration, if we assume $q$ isn't collinear with any of the segments, no points are on the linear extension of the segment, which means they are always on exactly one side.)