Re: Arrange points so polygon is not self intersecting

On Wed, 11 Jul 2007 04:27:57 GMT, Michael Press <rubrum@xxxxxxxxxxx>
wrote:

In article
<hvj693pj2ijl1qf2i5jpq8cbsn6ulcvka3@xxxxxxx>,
quasi <quasi@xxxxxxxx> wrote:

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.

I expect ray tracing from the interior of the newly formed
convex polygon can be made to discover candidate edges for joining.

Another scheme goes like this.

Let P be the set of all points.
Form the convex hull of all points.
If this contains all points we are done.
Sort the points by y-coordinate.
Let A be a point with maximum y-coordinate.
Let Z be a point with minimum y-coordinate.
A and Z are part of the convex hull.
Let arc(AZ) be a set of points in the convex hull joining A and Z.
Let S = P \ arc(AZ)
Run a horizontal sweep line over S.
This sweep line visits each point of S in order of its y-coordinate.
In case of multiple points with equal y-coordinates,
sort on the x-coordinate.
The points can be joined in the order of visitation,
into a serpentine polygonal arc with no self intersection.
Finally, join the serpentine and arc(AZ).

This works very well.

You can avoid having to worry about whether or not points have equal
y-coordinates by choosing the axes at the start so that the
y-coordinates of all points are distinct.

quasi
.

Relevant Pages

  • Re: Arrange points so polygon is not self intersecting
    ... Find the convex hull of the points and draw a convex polygon. ... Let A be a point with maximum y-coordinate. ...
    (sci.math)
  • Re: From Triangle tiles to convex Polygons.
    ... all internal edges that don't have a connection to a convex vertex. ... You don't get the minimal convex decomposition that way. ... like metric to avoid all the long and thin triangles. ... the polygon with holes to a simple polygon. ...
    (comp.graphics.algorithms)
  • Re: overlapping area of two ellipses
    ... A sweep-algorithm works for 2). ... intersection of a polygon an a rectangle. ... the same idea can be generalized to clipping inside a convex polygon. ... It might even be possible to develop a closed form solution, ...
    (comp.graphics.algorithms)
  • Re: 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 ... that convex polygon. ... resemble a sort of circular labyrinth. ...
    (sci.math)
  • Re: From Triangle tiles to convex Polygons.
    ... I start out with a complicated non-convex polygon with holes. ... it into OpenGL GLU, and I get back a few hundred triangles that ... problem is that a few hundred triangles is way too many, ... I think you can do this by taking your triangulation and merge triangles to build multiple convex polygons from it. ...
    (comp.graphics.algorithms)