Re: Arrange points so polygon is not self intersecting

In article
<1184022077.952496.276860@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>
,
mekmon@xxxxxxxxx wrote:

Hi all,

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.

Find the convex hull of the points and draw a convex polygon.

Find the convex hull of the remainder of the points
and draw a convex polygon.

Remove an edge from each polygon and connect the two
polygonal arcs into a polygon without self intersections.

Find the convex hull of the remainder of the points
and draw a convex polygon.

Continue until all points are incorporated.

--
Michael Press
.

Relevant Pages

  • Re: Creating a shape from a set of points
    ... I have a bunch of points ... Are you looking for the convex hull? ... Polygon is a particularly convenient ... home dot woh dot rr dot com slash jbmatthews ...
    (comp.lang.java.programmer)
  • Re: modification of convex hull
    ... polygon X which contains all points of P. ... don't know how to reduce properly it's number of verticies. ... Perhaps you can say why you were disappointed by starting with the convex hull and reducing it. ... did you experiment with different criteria for choosing the edge to eliminate? ...
    (comp.graphics.algorithms)
  • Re: Novice 2D question: How to find points in a convex hull/polygon in a 2D grid (including points
    ... but perhaps a normal polygon rasterizing algorithm can do ... > checks all the points in a set to find the convex hull but I already ... > convex hull that lie on 2D grid points and their maximum number (the ... > with S that should be 0 if it's on the border, ...
    (microsoft.public.win32.programmer.directx.graphics)
  • Re: Arrange points so polygon is not self intersecting
    ... Call your set of points S. Find the convex hull of S. ... form a polygon with non-intersecting sides. ... If the C language implements the type long long int ... typedef long long int2; ...
    (sci.math)
  • Re: Arrange points so polygon is not self intersecting
    ... Call your set of points S. Find the convex hull of S. ... Sweep a ray R emminating from P through 360 degrees. ... Line segments connecting adjacent points in the list created by ... form a polygon with non-intersecting sides. ...
    (sci.math)
Loading