How to turn complex polygon into simple polygon?

[jsbm at ams.sunysb.edu]

Eric,

If I understand your question correctly, you can just do this:
sort the points by angle about any one of the points (actually,
do this using the "left" test, without arc-tangents, etc).
Join the points in this order, giving you a star-shaped simple
polygon.  (This also gives you a proof that a simple
polygonalization always exists for any set of points, as you
suspect.)

See
``On the Reflexivity of Point Sets'', 
Esther M. Arkin, Sandor Fekete, Ferran Hurtado, Joseph S. B. Mitchell,
Marc Noy, Vera Sacristan, and Saurabh Sethia,
http://arXiv.org/abs/cs.CG/0210003
for related discussions about polygonalizations and some
references to earlier work.

Best,

Joe Mitchell


On  8 Mar, Eric Fowler 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.
> 
> 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.