2
$\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?

Improve this question
$\endgroup$
2
  • $\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$ – Tomilov Anatoliy Jan 18 '18 at 18:22
2
$\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.$$

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

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Just to be explicit: the above does not [express it] without comparisons. $\endgroup$ – greybeard May 13 '20 at 23:36

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.