2
$\begingroup$

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.

  • 0
    In the diagram, $\theta$ is in the clockwise direction.2010-12-21
  • 0
    @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.2010-12-21

2 Answers 2

2

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$

  • 0
    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.2010-12-21
  • 0
    @picakhu, sorry. Actually I can't even be sure that your solution works *at all*, see the updated question.2010-12-21
  • 0
    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.2010-12-21
  • 0
    @picakhu, it's 2D only; I've fixed the example.2010-12-21
  • 0
    I have not checked your work, but just want to make sure you did $\sin\,\theta=\frac{|a\times b|}{|a||b|}$2010-12-21
  • 0
    Also try dot product.. $\cos\,\theta=\frac{a\cdot b}{||a|| ||b||}$2010-12-21
0

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