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

It's unclear what you mean by "find an order"
so that "the polygon of those points" is not
self-intersecting.

Perhaps you mean that the points themselves
are fixed in R^2, and you are free to impute
any cyclic ordering to produce a closed path
or polygon by connecting the points in that
order.

The convex hull of the points identifies which
of them are "outermost". You could start by
connecting these in the order determined by
that convex polygon. The remaining points
will lie in the convex closure of those outer
points.

As a general approach you can add these
remaining points one at a time provided that
at each step the unassigned points are not
in the exterior of the resulting polygon.
Any that fall on the boundary are happily
assigned a place in the ordering, but
there's a lot of flexibility in choosing
where the interior points are inserted
in the ordering.

If you aren't picky about the geometry,
I suppose a fairly expeditious approach
would be to recursively apply the convex
hull to all the remaining points, thereby
arranging them into a nested hierarchy.
A resulting proper polygon would typically
resemble a sort of circular labyrinth.

There are a variety of fast algorithms
for finding the convex hull of a set of
points in 2D, e.g.

http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm

regards, chip

.

Relevant Pages

  • Re: Smallest 4-sided polygon surrounding convex hull ( smallest convex quadrilateral)
    ... "Finally the smallest 4-sided polygon surrounding the segmented code [ ... This is a special case of convex hull ... And I can't find an algorithm for that, ... I believe I'm looking for the minimal enclosing quadrilateral ...
    (comp.graphics.algorithms)
  • Re: modification of convex hull
    ... It doesn't have to be convex. ... I had to make a little break in making this algorithm but now I am ... If you have too few sides, look for a point internal to the current polygon such that if you "push in" the polygon to make that point a vertex you don't make any other point EXTERNAL to the new polygon. ... Neither will guarantee the MINIMAL area polygon. ...
    (comp.graphics.algorithms)
  • Re: How can I count the area of any polynomes??
    ... vertex of some polygon and I must count the area of this polygon!! ... Assuming this polygon is convex, Gib Bogle's algorithm can be used, ...
    (sci.math)
  • Re: modification of convex hull
    ... My goal is to get polygon of minimum space. ... It doesn't have to be convex. ... I had to make a little break in making this algorithm but now I am ...
    (comp.graphics.algorithms)
  • Arrange points so polygon is not self intersecting
    ... 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 ... Assume this is a 2-D plane with Euclidean geometry. ...
    (sci.math)
Loading