# Find the Outgoing Edge with the Smallest Angles, Given one Incident Edges and Multiple Outgoing Edges

I have one incident edges and multiple outgoing Edges, for which I want to pick an outgoing edge such that the angles between the outgoing edge and the incoming edge is the smallest of all. We know the coordinates for the vertex $V$ .

The angle must start from the incoming edge ($e_1$) and ends at another edge ($e_2$, $e_3$, $e_4$).

Also, the angle must be form in such a way that the face constructed from $e_1$ to $e_2$ must be in counter-close-wise direction. In other words, the face that you construct when you link all the vertexes $V$ in $e_1$ and $e_i$ together, must be a counter clockwise cycle.

So in the case below, edge $e_2$ must be picked because the $\theta$ is the smallest.

Is there an algorithm that does this elegantly? The few algorithms I devise are just plain ugly and requires a lot of hacks.

Update: One method that I think of ( and proposed below) is to use the cross product for each edge against the incoming edge $e_1$, and get the minimum $\theta_{i}$. i.e.,

$$e_{1} \times e_{i} = |e_{1}||e_{i}| \sin\, \theta_{i}$$

But the problem of this is it doesn't really work. Consider the following test cases: $$e_1=(1,0)$$ $$e_2=(-1/\sqrt(2),1/\sqrt(2) )$$ $$e_3=(1/\sqrt(2),-1/\sqrt(2))$$

One would find that

$$\theta_2 = -45^o$$ $$\theta_3=-45^o$$

Both are equal-- even though we know that $e_2$ should be selected.

-
In the diagram, $\theta$ is in the clockwise direction. – PEV Dec 21 '10 at 3:39
@Tervor, I didn't say that $\theta$ must be in counter clockwise direction. I'm saying that the face, when you link all the vertexes in $e_1$ and $e_i$ together, must be a counter clockwise cycle. – Graviton Dec 21 '10 at 3:49

Assuming that finding the coordinates(of your vectors) is not too difficult.

You can use the definition of dot and or cross products, and then solve for the angles.

So you can for example use $| a \times b | = |a||b| \sin\, \theta$

-
Not sure whether your solution works; although I can get the edge with minimum $\theta$, but I can't reject the face with clock wise cycle; see the updated question. – Graviton Dec 21 '10 at 6:18
@picakhu, sorry. Actually I can't even be sure that your solution works at all, see the updated question. – Graviton Dec 21 '10 at 6:31
I made a small mistake. Ill fix it. Try it again. By the way, your example is in 3 dimensions. Which complicated things.. You will have to use some kind of projection. – picakhu Dec 21 '10 at 7:29
@picakhu, it's 2D only; I've fixed the example. – Graviton Dec 21 '10 at 7:33
I have not checked your work, but just want to make sure you did $\sin\,\theta=\frac{|a\times b|}{|a||b|}$ – picakhu Dec 21 '10 at 7:36

If you are trying to put this into code you may want to consider the function atan2(y,x), it is available in most languages. Note that it takes the y coordinate as the first parameter. Since atan2 takes two parameter it can figure out in which quadrant your vector lies, and it can output the angle in the range $-\pi$ to $\pi$.

Here is a perl snippet to demonstrate how it works for your two angles:

#!/usr/bin/perl

use Math::Trig;

$t_rad = atan2(1/sqrt(2),-1/sqrt(2));$t_deg = $t_rad * 180 / pi; print "theta_2 =$t_deg\n";

$t_rad = atan2(-1/sqrt(2),1/sqrt(2));$t_deg = $t_rad * 180 / pi; print "theta_3 =$t_deg\n";


And here is the output when you run it for the two examples above:

theta_2 = 135
theta_3 = -45

-