How to turn complex polygon into simple polygon?

[Eric Fowler]

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.

It is easy enough to find intersecting segments, but here is the rub - how
to flip the segments without breaking up your polygon into 2 subpolygons?
Each intersection offers 2 ways to flip the lines, but only one will NOT cut
the polygon Visualize a figure - 8 polygon. You need the intersecting
segments to swap endpoints. There are two ways to do it. One way gets you a
simple large polygon, the other way gets you two little ones. How do I
distinguish them?

I could test for closure of either proposed new polygons, but I want to
avoid that because it might be costly.

So, is there a cheap test for whether an edge flip cuts up a polygon?

Oh, and I assume for any given set of n >= 3 points there exists a simple
polygon connecting them ...

Eric


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