How to turn complex polygon into simple polygon?
eppstein at ics.uci.edu
Mon Mar 10 07:39:41 PST 2003
On 3/8/03 2:57 PM -0800 Eric Fowler <efowler at seanet.com> wrote:
> I need a simple algo for creating a simple polygon from a complex one,
> i.e., a list of segments with adjoining endpoints, some of the segments
> being colinear or crossing each other. I don't care about finding a given
> unique or optimal way to get to a simple poly, any old simple polygon
> will do, but it has to have all the points from the parent complex
The usual way to do this is to ignore the input segments, find the
bottommost point, sort the other points radially around the bottommost
points, connect them in the sorted order, and attach the bottommost point
to both ends of the sorted chain. Unless there is some structure from the
original polygon that is not sufficiently preserved by this?
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce