Re: Arrange points so polygon is not self intersecting

mek...@xxxxxxxxx wrote:
I was wondering if someone knows some sort of algorithm to find an
order for a set of points so that the polygon of those points is not
self-intersecting. Assume this is a 2-D plane with Euclidean geometry.

Michael Press wrote:
Find the convex hull of the points and draw a convex polygon.
[snip remainder]

I think that is far too complicated. A much simpler algorithm is this:

1. Connect all the points in some order to get a polygon, probably
self-intersecting.

2. Find a pair of edges AB and CD that intersect.

3. Replace those edges either by AC and BD, or by AD and BC. One of
these choices makes two loops, the other keeps it as one loop. Always
choose the single loop option.

4. repeat 2-3 until there are no intersecting edges.


This algorithm will terminate because the total edge length decreases
at each step and there are only finitely many possible values this
total length can have for any given set of points.

.

Relevant Pages

  • Re: Arrange points so polygon is not self intersecting
    ... self-intersecting. ... Connect all the points in some order to get a polygon, ... these choices makes two loops, the other keeps it as one loop. ... This algorithm will terminate because the total edge length decreases ...
    (sci.math)
  • Re: POLY2CW ??? what happened to it?
    ... Steve Eddins ... have to make the vertices of the polygon ordered clockwise. ... POLY2CW does not reorder the vertices of a self-intersecting polygon to make it non self-intersecting. ...
    (comp.soft-sys.matlab)
  • Re: GDI+ Z-order?
    ... same, a.k.a, I don't want to outline the polygon, as I would have used ... So I need to build my pts array in order to be able to draw my polygon, ... but while I loop for that, I thought 'why not draw the lines'...Now, I ... Dim pts(5) As Point ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: GDI+ Z-order?
    ... but while I loop for that, I thought 'why not draw the lines'...Now, I ... end up with my polygon drawn after, because I can only draw it once I ... Dim linesAs Point ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Point in Poly formula
    ... > Right, so they are a set of x,y co-ords that define one edge of the ... yes it means c= NOT c and in fact it effects the c value in the loop. ... Prev by Date: ...
    (comp.graphics.algorithms)