You don't need to compute angles
You just need to be able to
compare angles. That is easier because you just need to compute the sin and cos of the angles and compare those. Let me walk you through that calculation and then comparison.
Suppose that
p0,
p1, and
p2 are points, represented by ordered pairs of coordinates,
(p0x, p0y),
(p1x, p1y), and
(p2x, p2y). Suppose that you're interested in the angle at
p0 between the lines from
p0->p1 and
p0->p2. That is the angle between the vectors
\n v1 = p1 - p0\n = (p1x, p1y) - (p0x, p0y)\n = (p1x-p0x, p1y-p0y)\n = (v1x, v1y)\n
and
\n v2 = p2 - p0\n = (p2x, p2y) - (p0x, p0y)\n = (p2x-p0x, p2y-p0y)\n = (v2x, v2y)\n
Now let me introduce the dot product. Suppose that
v and
w are two vectors. Then the definition of the dot product is
\n v dot w = (vx, vy) dot (wx, wy)\n = vx*wx + vy*wy\n
Seems simple, why do you care? Well because of the following geometric fact (good in any number of dimensions):
The dot product of two vectors is the product of their lengths and the angle between them! In other words if we define:
\n |v| = length of v\n = sqrt(vx*vx + vy*vy)\n
then
\ncos(angle from v to w)\n = (v dot w)/ ( |v| * |w| )\n
all of which we know how to calculate. In your problem you can just calculate
v1 and
v2, then drop them in as
v and
w. (In fact the same calculation works in any number of dimensions.)
So we can compute the cos of the angle. What about the sin? Well that needs a 2-dim piece of trivia. Suppose that
v1' is
v1 rotated 90 degrees counter-clockwise. Then the sin of the angle from
v1 to
v2 is the cos of the angle from
v1' to
v2. So what is
v1'? Well it turns out to be
(v1y, -v1x). So to calculate the sin, drop
v1' and
v2 in as
v and
w in the formula above.
Now that we have sin and cos, you can figure out how to calculate angles with appropriate invocations to the inverse functions.
But you don't need to do that! Just remember this fact. Going from 0 degrees to 180 degrees, sin(angle) >= 0 and cos(angle) decreases from 1 to -1. Between 180 and 360 degrees, sin(angle) < 0 and cos(angle) increases from -1 back to 1. You can therefore compare angles to see which is greater without actually calculating them.
If you don't want to do pairs of comparisons, though, you don't have to. Instead you can write a cheesy function like this (untested but it compiles) one in Perl to get something that increases from 0 to 4 as the angle goes from 0 to 360 degrees (though not evenly):
\n# Given 3 points p0, p1, and p2, this returns a\n# number from 0 to 4 that increases monotonically as\n# the angle p1->p0->p2 goes from 0 to 360 degrees.\n#\n# This therefore isn't the angle, but can be used to\n# compare the angles.\nsub angle_proxy {\n my ($p0, $p1, $p2) = @_;\n\n my $v1 = subtract_vectors($p1, $p0);\n my $v2 = subtract_vectors($p2, $p0);\n\n if (vector_cos(rotate_90($v1), $v2) >= 0) {\n return 1 - vector_cos($v1, $v2);\n }\n else {\n return 3 + vector_cos($v1, $v2);\n }\n}\n\n# Returns the cos of the angle between 2 vectors.\nsub vector_cos {\n my ($v, $w) = @_;\n return dot($v, $w) / sqrt(dot($v, $v)) / sqrt(dot($w, $w));\n}\n\n# From here on down functions rely on the internal\n# representation that I have chosen, an array\n# reference in Perl. If the functions or notations\n# do not make sense, refer to the math explanation\n# above.\n#\n# You should be able to guess most of the notation\n# except $#$foo. $#array is the last index of an\n# array. If $foo is a reference to an array, then\n# 0..$#$foo is the set of possible indexes. I'm\n# using that just to show what can be generalized\n# easily to more than 2 dimensions.\n#\n# I've left out various sanity checks that one might\n# want to insert.\n\n# Subtracts the second from the first.\nsub subtract_vectors {\n my ($v, $w) = @_;\n my $difference = [];\n for my $i (0..$#$v) {\n $difference->[$i] = $v->[$i] - $w->[$i];\n }\n return $difference;\n}\n\n# Returns the dot product of two vectors.\nsub dot {\n my ($v, $w) = @_;\n my $answer = 0;\n for my $i (0..$#$v) {\n $answer += $v->[$i] * $w->[$i];\n }\n return $answer;\n}\n\n# Rotates a vector 90 degrees counter-clockwise.\n# Only works for 2-D vectors.\nsub rotate_90 {\n my $v = shift;\n return [$v->[1], -$v->[0]];\n}\nCheers,
Ben
