Validity of algorithm for creation of a non self-i

问题:

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 there must be).

回答1:

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?

回答2:

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

回答3:

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.

回答4:

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.

回答5:

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!!