How to turn complex polygon into simple polygon?

jsbm at jsbm at
Mon Mar 10 09:01:05 PST 2003


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

``On the Reflexivity of Point Sets'', 
Esther M. Arkin, Sandor Fekete, Ferran Hurtado, Joseph S. B. Mitchell,
Marc Noy, Vera Sacristan, and Saurabh Sethia,
for related discussions about polygonalizations and some
references to earlier work.


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
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list