0
$\begingroup$

I' m looking for an efficient (in terms of lowest number of additions/multiplications) way to compare two (directed) angles $\measuredangle p_1 p_0 q$, $\measuredangle p_1 p_0 r$ in a plane.

For example, the orientation of $r$ in respect of the line $g(p_0,p_1)$ can be efficiently obtained by calculating the third coordinate of the cross product $(p_1-p_0) \times (q-p_0)$ - if it's positive, $r$ lies left of $g(p_0,p_1)$, if it's 0, $r$ is on the line and right, if negative.

Is there a comparable way for determining which angle is bigger?

2 Answers 2

1

I think the computationally cheapest way forward would be something like

  1. Translate everything to make $p_0=(0,0)$.

  2. Multiply by the matrix $\begin{bmatrix} x_1 & y_1 \\ -y_1 & x_1\end{bmatrix}$ to rotate the plane so $p_1$ lies on the positive $x$-axis (all while scaling by an irrelevant factor).

  3. Handle the special cases where $q$ and/or $r$ are on the $x$ axis.

  4. Scale $q$ by $|y_r|$ and $r$ by $|y_q|$. Now $p$ and $q$ both have the same $y$-coordinate, up to their sign.

  5. Compare the $x$-coordinates of $q$ and $r$. Larger $x$-coordinate means smaller angle.

This uses no square roots, no divisions, and 10 multiplications if you avoid computing intermediates that are not used for anything anyway.


I see now that the question asks about directed angles. In that case step 3 should handle the case where the $y$-coordinates have different sign. In step 4 the absolute values can be omitted, which should make the comparison in step 5 give the right result even in the case that the $y$-coordinates in step 3 were both negative.

  • 0
    yes, that's right. I had a sign error. And even for the other problematic case like $p_0 = (0,0), p_1=(1,0), q=(1,1), r=(1,-1)$ handling different $y$-values separately solves this. Thanks, all objections were unnecessary.2012-09-18
2

Since $\cos\theta$ is monotonically decreasing for $\theta\in[0,\pi]$, and the dot product of two vectors ${\bf p}$ and ${\bf q}$ is ${\bf p}\cdot{\bf q}=pq\cos\theta_{pq}$, you can simply compare the appropriately normalized dot products. Specifically, you can look at the sign of $({\bf p}_1 - {\bf p}_0)\cdot\left[\frac{{\bf q} - {\bf p}_{0}}{||{\bf q} - {\bf p}_{0}||} - \frac{{\bf r} - {\bf p}_{0}}{||{\bf r} - {\bf p}_{0}||}\right].$

  • 0
    well, it works for $\theta\in[0,\pi]$, but for $p_0=(0,0), ~ p_1=(1,0), ~ q=(1,1), ~ r=(-1,1)$ it indicates both angles to be equal, while they're not.2012-09-11