# Compare two atan2

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?

• What do you mean by 'express'? A closed formula to get result of the inequality? An algorithm? Jan 18, 2018 at 18:03
• I mean closed formua, like $(\mathbf{v_i} \cdot \mathbf{v_j}) / [\mathbf{v_i} \times \mathbf{v_j}] or something else terse and computationaly effective. Jan 18, 2018 at 18:22 ## 2 Answers 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.$$

• Counterexample for determinant: ((1, 1), (-1, -1)) and ((1, 1), (1, 1)). Signed area will have mirror symmetry. Jan 18, 2018 at 18:45

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.

• Just to be explicit: the above does not [express it] without comparisons`. May 13, 2020 at 23:36