3
$\begingroup$

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:

https://arxiv.org/pdf/1403.3905.pdf

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

$\endgroup$
1
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.