Jeff Massung wrote:
Michael,
Sorry, but the problem you are running into is that (in your second example)
The examples were from me (Alex) not Michael :-)
you are working with a concave polygon instead of convex.
Yes. Exactly. There *are* polygons which are concave. We could all look
at them and agree on where the inside of the polygon is, and therefore
all agree on whether the perimeter is defined clockwise or
anti-clockwise around that interior.
I promise, using
the cross-product is correct.
If you define the problem space to be limited to convex polygons, then
it is correct. But if you want to handle all (or almost all - see below)
polygons, then it is not correct.
Concave polygons get tricky, because the winding actually does - in fact -
change direction. You - as a human - are simply looking at the resulting,
whole polygon and making a determination from that, which is actually
wrong.
The conclusion that you arrive at from looking at the whole polygon is
correct; the winding around the interior is consistent; the direction
change in co-ordinate space changes, but not relative to the interior.
You have a couple options:
1. Perform the cross product across all points from last to first - exactly
as I originally described, and count the winding directions of each, taking
the greater of the two.
Sorry, that doesn't work consistently either. Picture a regular 12-sided
figure, with two sides vertical, and defined counter-clockwise. The c-p
will give the same answer for all 12 vertices. Then draw a much larger
square around it, such that one of the vertical sides of the square
overlaps the vertical side of the shape (and the square encloses the
shape). Now "erase" the line segment which is shared - we now have a
16-sided figure, and let's define it in the order that the points from
the original 12-sided figure remain counter-clockwise. (Note that the
area inside the original figure is now outside this new figure). This
new figure is actually (according to humans :-) defined clockwise - but
the c-p will still give the same answer for all those original points,
so it would have 10 saying counter-clockwise, and only the 6 new ones
would say clockwise - and hence get the wrong answer.
2. If you know the majority of your polygons are shaped a particular way, an
often-used trick is to take P(N), P(2), and P(1) and simply use those as a
quick and dirty test.
Option #1 will produce the desired, correct result, but takes more time.
Option #2 can very often be wrong, but given your use-cases could be right
100% of the time.
Option #1 gives unreliable answers in some cases, such as the example above.
Option #2 gives very unreliable answers
And there are simple (though not super-fast) solution that get the
answer correct (i.e. agreeing with what a person would say) for all
cases where people would agree.
There are more complex cases (e.g. self-inverting polygons, which you
could argue are malformed polygons) where there is probably no correct
answer.
-- Alex.
_______________________________________________
use-revolution mailing list
[email protected]
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-revolution
