Fastest way to compare angles

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.

-
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

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

-
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