How to turn complex polygon into simple polygon?

David Eppstein eppstein at
Mon Mar 10 07:39:41 PST 2003

On 3/8/03 2:57 PM -0800 Eric Fowler <efowler at> 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            
Univ. of California, Irvine, School of Information & Computer Science

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