Validity of algorithm for creation of a non self-intersecting polygon_问答_开发者

As an extension and partial answer to my thread I wrote a simple algorithm that given a set of points(with xy coordinates) can form a non self-intersecting polygon.

Claim: Given an arbitrary set of points with different coordinates it is always possible to construct a regular or irregular, non self-intersecting polygon.

The algorithm:

Assume there is a set V containing all the vertices

1) Sort all vertices in V by x-coordinate

2) Imagine a straight line (we'll call that "the divider") parallel to the x-axis which starting from the first node expands to infinity and divides/splits the vertices into two sets.

3) Now consider the two sets:

A = The set of all vertices above or on the divider line

B = The set of all remaining vertices

4) Starting at the leftmost vertex of A connect all vertices in A until you get to the rightmost

5) If the rightmost vertex of the sorted set V (the vertex with the biggest x coordinate) is not in A connect that last vertex (rightmost of A) with it.

6) Work backwards and starting from the rightmost vertex of the sorted set V (the vertex with the biggest x coordinate) connect all the vertices that are in B

7)Connect the first (leftmost vertex of B) vertex of B with the leftmost vertex of A

I think that the algorithm is correct and can't find a test that it would fail but maybe I'm missing something.

I would appreciate it if you could have a look and give me an example that wouldn't work if there is any(which I'm sure t开发者_JS百科here must be).

Here is a counterexample. When step 5 does not draw a line, it is possible to self intersect.

Validity of algorithm for creation of a non self-intersecting polygon

I'm not sure I understand correctly what you're trying to do. In the other thread, and in the corresponding thread at math.SE (which brought me here), you said you had a polygon and were trying to find its center of gravity. Here you say you have a set of points and you want to construct a non-intersecting polygon from it. Those are two quite different things. As I mentioned at math.SE, if the polygons are not known to be convex, a set of points doesn't uniquely define a polygon -- so the algorithm you propose here may construct some arbitrary non-self-intersecting polygon (I haven't checked whether it successfully does that) but that may or may not bear any relation to the polygon you were originally interested in. Or did I misunderstand your question at math.SE and you actually only have some points and want to construct just any non-self-intersecting polygon from them and don't care that there may be several inequivalent solutions for this?

I think I have a simpler algorithm that creates such a polygon. May be harder to implement in software but is much easier to describe in words.

Pick any point in the set as your start. Create a line at 0 angle starting from it.
start rotating the line around the point. The moment it meets any other point, draw an edge from the starting point to the newly found point.
continue rotating around the starting point, connecting any newly-found point with the last found.
at finish of the rotation, close the shape by meeting the start point.

In case of multiple finds on one direction, connect them picking one direction (say, starting with inner-most ending with outer-most)

The shape will be usually somewhat star-like, but fulfilling the requirements.

Computational execution would be like:

translate all points to coordinate set with origin[0,0] in one of the points.
convert all points to polar coordinate set
sort by: angle ascending, radius ascending.
connect all points in the sort order.
connect last to the first ([0,0]) point.

I would prove it slightly differently by setting the "divider line" as a connection between left-most and right-most points, rather than parallel to x axis. It could happen that there are no points below or above the parallel-to-x line and that could cause trouble to your proof.

Also, connection (5) could lead to some self-intersections with the connections generated in point (6)

There is also a special case when all points are colinear and your polygon is degraded to a line.

We assume that the set V of vertices is finite ;)

Other than that - I believe your claim is true.

I had the same problem in javascript and OpenLayers library. So this is my solution for detecting validity of a polygon in 'vectors' layer as a OpenLayers.Layer.Vector:

var ps = vectors.features[0].geometry.getVertices(), i, j, inx, x1, x2, x3, x4, y1, y2, y3, y4, x43, x21, y21, y43, y31, maxx12, maxx34, minx12, minx34;
ps.push(ps[0]);
for(i = 0; i < ps.length -1 ; i++ ) {
  x1 = ps[i].x; x2 = ps[i+1].x;
  y1 = ps[i].y; y2 = ps[i+1].y;
  for(j = i + 2; j < ps.length -1 ; j++ ) {
    x3 = ps[j].x; x4 = ps[j+1].x;
    y3 = ps[j].y; y4 = ps[j+1].y;
    x43 = x4 - x3; x21 = x2 - x1; y21 = y2 - y1; y43 = y4 - y3; y31 = y3 - y1;
    inx = ( x43*y21*x1 - x21*y43*x3 + y31*x21*x43 )/( x43*y21 - x21*y43 );
    if( x1 < x2 ){
      minx12 = x1; maxx12 = x2;
    } else {
      minx12 = x2; maxx12 = x1;
    }
    if( x3 < x4 ){
      minx34 = x3; maxx34 = x4;
    } else {
      minx34 = x4; maxx34 = x3;
    }
    if (minx12 < inx && inx < maxx12 && minx34 < inx && inx < maxx34 ){
      console.log('intersected!'+' ,x1: '+x1+' ,x2: '+x2+' ,inx: '+inx+' ,i: '+i+' ,j: '+j);

      return;
    }
  }
}

hope you enjoy it!!