Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Polygon algorithm needed

Skip to first unread message

Steve Gray

Sep 9, 2004, 5:39:13 PM9/9/04
I have plane polygons with many sides. They are self-crossing to an arbitrary degree. For
each vertex I need to know its "depth," that is, the smallest number of edges that must be crossed
by a path, not necessarily straight, to get to the outside.
A ray from the vertex far to the right will cross either an odd or even number of edges, but
this tells me only whether the depth is odd or even, that is, its low order bit. Vertices with even
depth can be on the outside (depth 0). I need the other bits too.
I will appreciate any algorithms, references, or ideas about this. Thank you in advance.

Steve Gray

0 new messages