Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  hardmooth Sep 11 '12 at 12:52
    
@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? –  Henning Makholm Sep 11 '12 at 20:18
    
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. –  hardmooth Sep 18 '12 at 11:23
add comment

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

share|improve this answer
    
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. –  hardmooth Sep 11 '12 at 12:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.