How to turn complex polygon into simple polygon?

[David Eppstein]

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
> polygon.

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
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.