Re: Arrange points so polygon is not self intersecting

On Jul 9, 7:01 pm, mek...@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.

Thanks!
Dan

CLOCK Alogrithm:

1) Call your set of points S. Find the convex hull of S.

2) Pick any point P within the convex hull that is not coincident with
one of the points in S.

3) Sweep a ray R emminating from P through 360 degrees. Each time R
sweeps through a point in S, put that point next in your ordered list.

Claim: Line segments connecting adjacent points in the list created by
Step 3, plus the line segment connecting the first and last points in
the list, form a (generally star) polygon with non-intersecting sides.

- MO

.

Relevant Pages

  • 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)
  • 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)