Given n line segments and a circular sector, find the leftmost and the rightmost segments

algorithmscomputational geometrycomputer sciencegeometry

Suppose we are given an array of n 2D line segments as [l_1, l_2,...,l_n], where l_k = (s_k, e_k) for each k=1,2,...,n, and a circular sector centered at the point c, determined by the triplet (a_left, a_right, r), where 0 <= a_left, a_right <= 2pi, r >= 0.

We want to either find the leftmost and the rightmost segments l_left, l_right, or determine that no such segments exists. The leftmost segment is that line segment which either intersects the radius originating from c at angle a_left, or alternatively that line segment which intersects the radius originating from c at the greatest rotation angle measured from the positive x-axis. Similarly, the rightmost segment is that line segment which is either intersected by the radius (originating from c) at angle a_right, or that segment which has the lowest rotation angle measured from the positive x-axis.

Note: Here we want a line segment (s_k, e_k) to be oriented such that the point c is to the right of the colinear line through s_k to e_k.

We can assume that an efficient method exists for determining the orientation of a line segment (s_k, e_k), and if necessary we can re-order the points so that the they are oriented as we want.

Picture: Example situation, where points A, B, C determine the circular sector.

So far my attempt was to form an array of tuples arr = [<first, second>_1, <first, second>_2,...,<first, second>_n], where first is the rotation angle of the leftmost point of a given line segment, and second is the index of the said segment in the original array. Then I could simply sort the tuples in an ascending order by the rotation angle, and determine by a linear search whether any segment l_k indicated by the kth pair in the array intersects the ray originating from c.

Struggle: To my understanding, my current problem is the discontinuity of the rotation angle I get from my API. Specifically, consider the case represented here. Clearly the segment (D, E) has the greatest rotation angle of the segments, when double angles are allowed, but the API I have available gives D and E angles such that a_D < a_E. I tried to fixes this issue by first checking whether the rotation angle of the beginning vertex is less than that of the end vertex:a_s_k < a_e_k of a given segment (s_k, e_k). But this did not solve the problem. Any pointers on what I should do?

Best Answer

Note: Here we want a line segment $(s_k, e_k)$ to be oriented such that the point $c$ is to the right of the colinear line through $s_k$ to $e_k$.

(BTW, "colinear line" is redundant.) This is a key property. As long as you choose $s_k$ and $e_k$ this way (so $(s_{ky}-c_y)(e_{kx}-c_x) \ge (s_{kx}-c_x)(e_{ky}-c_y)$), the problem has a simple solution. If travelling from $s_k$ to $e_k$ has the circle center on your right, then you are travelling clockwise, and the angle should be decreasing. That is, the argument for $e_k$ should always be less than or equal to the argument for $s_k$.

If this isn't true, there are two ways we can correct it: either add $2\pi$ to the argument of $s_k$ or subtract $2\pi$ from the argument of $e_k$. Which technique makes sense depends on whether we are looking for the rightmost or leftmost segment. And just to be clear, I assume that these mean:

  • "Rightmost segment" is, among all segments with at least one end in the sector, the one with the most clockwise argument of all ends (include one outside the sector, provided the other end is in).
  • "Leftmost segment" is, among all segments with at least one end in the sector, the one with the most counter-clockwise argument of all ends (include one outside the sector, provided the other end is in).

Note that if the sector happens to open downward (instead of upward as in your examples), the "Rightmost segment" will be on the left and the "Leftmost segment" will be on the right (this is why "clockwise" and "counter-clockwise" are the better terminology for rotational phenomena).

Initialize variables

MinIndex = -1
MaxIndex = -1
MinAngle = 13   # > 4 * pi
MaxAngle = -7   # < -2 * pi

Pass through your segments, skipping over any segment without at least one endpoint in the sector. For the rest,

  • If $\arg s_k \ge \arg e_k$, then
    • if $\arg s_k >\text{ MaxAngle}$, then $\text{MaxAngle } = \arg s_k, \text{ MaxIndex } = k$.
    • if $\arg e_k <\text{ MinAngle}$, then $\text{MinAngle } = \arg e_k, \text{ MinIndex } = k$.
  • If $\arg s_k < \arg e_k$, then
    • if $\arg s_k + 2\pi >\text{ MaxAngle}$, then $\text{MaxAngle } = \arg s_k + 2\pi, \text{ MaxIndex } = k$.
    • if $\arg e_k - 2\pi <\text{ MinAngle}$, then $\text{MinAngle } = \arg e_k - 2\pi, \text{ MinIndex } = k$.

When you are finished, MinIndex will point to the Leftmost segment and MaxIndex will point to the Rightmost.

Related Question