# 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? – Discrete lizard Jan 18 '18 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. – Orient Jan 18 '18 at 18:22 ## 1 Answer 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. – Orient Jan 18 '18 at 18:45