1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean by 'express'? A closed formula to get result of the inequality? An algorithm? $\endgroup$ – Discrete lizard Jan 18 '18 at 18:03
  • $\begingroup$ 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. $\endgroup$ – Orient Jan 18 '18 at 18:22
1
$\begingroup$

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

Graph of atan2

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

$\endgroup$
  • $\begingroup$ Counterexample for determinant: ((1, 1), (-1, -1)) and ((1, 1), (1, 1)). Signed area will have mirror symmetry. $\endgroup$ – Orient Jan 18 '18 at 18:45

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.