Re: Arrange points so polygon is not self intersecting

On Tue, 10 Jul 2007 01:17:50 -0700, Michael Press <rubrum@xxxxxxxxxxx>
wrote:

In article
<3f4693hbnrev4prjvpl3irnjo3ke90r13e@xxxxxxx>,
quasi <quasi@xxxxxxxx> wrote:

On Mon, 09 Jul 2007 20:10:54 -0700, Michael Press <rubrum@xxxxxxxxxxx>
wrote:

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.

This seems similar to Chip Eastham's construction, but I think your
version, by ending up as a closed polygon at each stage, appears more
careful about making sure that you can get back.

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

Continue until all points are incorporated.

There are still a few issues.

One issue is that the innermost hull might not be a polygon. It might
be a line segment or a point. I don't think that presents a problem
but it needs to be at least thought through.

Another issue is the loss of convexity.

A four by four square grid of points cannot be connected
into a convex polygon.

You misunderstood what I was worrying about. I wasn't trying to imply
that you can make a convex polygon out of any finite point set. My
concern has to do with how you connect from the polygon after a given
ring is finished to the next inner ring. The polygon is only convex
right after the outer ring is done. As long as the lack of convexity
of a polygon after a given stage doesn't affect your argument, then
there's no problem. I'm not doubting that you can do it -- I just feel
you need to specify more fully how to connect to the next inner ring.

quasi
.

Relevant Pages
Loading