Icarus Sparry
5/15/2016 7:44:00 PM
On Sun, 15 May 2016 12:53:22 -0400, George Neuner wrote:
> On Sun, 15 May 2016 05:05:10 +0000 (UTC), Kaz Kylheku
> <545-066-4921@kylheku.com> wrote:
>
>>On 2016-05-14, Bigos <ruby.object@googlemail.com> wrote:
>>> I try compare vectors to see if a polygon is convex.
>>>
>>> My approach tries to measure angles of polygon and check if the angle
>>> goes beyond 180 degrees. Current method of calculating vector angles
>>> does not provide this information.
>>
>>You don't need to calculate the angle. Treat the polygon as a directed
>>path, whose edges are vectors. You can take the cross product of two
>>successive vectors; its sign tells you whether the next edge turns left
>>or right relative to the previous one.
>
> I think you meant 'dot product' ... the cross product is area.
>
> George
I'm with Kaz.
One way of looking at the dot product of 2 vectors ('u' and 'v' in the
conventions I learned) is that it is the magnitude ('length') of u times
the magnitude of v * the cosine of the angle between them. Since we only
care if the value is positive, negative or zero, and we can ignore zero
length vectors, this amounts to just looking at the cosine function.
Since the cosine function is non negative in the range -90 degrees to 90
degrees, this doesn't help determine if the second vector is "left" or
"right" relative to the first.
On the other hand, the cross product of two vectors is a new vector at 90
degrees to both vectors with magnitude = magnitude u * magnitude v * the
sine of the angle between them. The ambiguity between the two possible
directions is resolved by the "right hand rule". Again just being
interested in the sign of the result, and ignoring zero sized vectors,
this is the sign of the sine function. It is positive if the angle is
between 0 and 180 degrees, and negative between -180 and -0 degrees. In
other words it can tell left from right (whilst cosine can tell forward
from backward)
So if the OP's polygon is restricted to 2 dimensions, we can say the
given two vectors [u1,u2,0] and [v1,v2,0] their cross product is
[0, 0, u1*v2-u2*v1]. So the OP just needs to work out u1*v2-u2*v1 for
each successive pair of vectors, and ensure that the values are either
all positive or all negative, or a mixture of positive and negative. If
there is a mixture then the polygon is not convex, otherwise it is.
Notes.
[1] If there are any zero values then two edges are linear. Probably in
terms of "convex" the zero values can be ignored unless they are all
zero, but it depends on the exact requirements.