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?


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.

| cite | improve this answer | |
  • $\begingroup$ Thanks Henning, I like your approach, but for $$p_0=(0,0), ~ p_1=(1,0), ~ q=(1,1), ~ r=(-1,1)$$ I think it's faulty. now I think, after your step 2 (rotating) we could look, whether $q$ and $r$ lie in different quadrants - a higher quadrant means a larger angle. Else (same quadrant): rotate $q$ and $r$ again to the first quadrant and continue with your solution. $\endgroup$ – hardmooth Sep 11 '12 at 12:52
  • $\begingroup$ @hartmooth: I don't see any problem with the approach in the situation you describe. Since $|y_r|=|y_q|=1$ nothing happens in step 4, so in step 5 your're comparing $x_q=1$ with $x_r=-1$. Since $x_q$ is the larger of these, $\angle p_1 p_0 q$ is the smaller angle. What do you think is wrong here? $\endgroup$ – hmakholm left over Monica Sep 11 '12 at 20:18
  • $\begingroup$ 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. $\endgroup$ – hardmooth Sep 18 '12 at 11:23

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

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – hardmooth Sep 11 '12 at 12:42

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.