Compare two atan2

Question

I tried to implement points location algorithm using Fortune's algorithm to get Voronoi diagram and another sweepline algorithm to locate many points in $O(n\cdot\log(n))$. If there are multiple concentric points on some step I get a pencil of radius vectors origins from the center of a circle. I need to sort them by angle (or at least to find minmax elements). I use the next formula to compare raduis vectors $\mathbf{v_i} = (x_i, \;y_i)$ and $\mathbf{v_j} = (x_j, \;y_j)$:

$$ atan2(y_i, \;x_i) < atan2(y_j, \;x_j) $$

I sure result can be achieved avoiding trigonometric functions. Can it be expressed without comparisons?

Currently I can sort them by quadrants, if both points are in the same quadrant, then I just look at cross product sign, otherwise I compare quadrant numbers.

PS: can someone create point-location tag?

Answer 1

The following answer is based on the following graph, taken from Wikipedia:

If $x_i,x_j > 0$ then you can use the monotonicity of the arctangent to get the equivalent condition $y_i/x_i < y_j/x_j$, or $y_ix_j < y_jx_i$.

If $x_i < 0$ and $x_j > 0$ then the answer depends only on the sign of $y_i$, and if $x_i > 0$ and $x_j < 0$ then the answer depends only on the sign of $y_j$.

If $x_i,x_j < 0$ and $y_i,y_j$ have different signs, then again the answer depends only on the sign of $y_i$. If $y_i,y_j$ have the same sign, then once again you can use monotonicity.

---

It is a good guess that the answer depends only on the sign of the determinant $$ \begin{vmatrix} x_i & y_i \\ x_j & y_j \end{vmatrix} = x_i y_j - x_j y_i.$$

Answer 2

Just to summarize the answer above as a computer programme (the determinant method does not work):

def atan2_lt( a, b, c, d ):
    """
    Test atan2(a,b) < atan2(c,d) without computing either.
    """
    if b*d < 0: return a < 0 if b < 0 else c > 0
    elif b > 0 or a*c > 0: return a*d < b*c 
    else: return a < 0 and c > 0

Edit: the above does not handle edge cases where a, b, c, or d is 0. I need to refine this.