创建非自相交多边形算法的有效性

Question

作为我的线程的扩展和部分答案，我编写了一个简单的算法，给出了一组点（具有xy坐标）可以形成一个非自相交的多边形。

---

主张：给定具有不同坐标的任意点集，始终可以构造规则或不规则、非自相交的多边形。

算法：

假设有一个包含所有顶点的集合 V

1) 按 x 坐标对 V 中的所有顶点进行排序

2) 想象一条平行于的直线（我们称之为“分隔线”）从第一个节点开始的 x 轴扩展到无穷大并将顶点分成两组。

3) 现在考虑这两个集合：

A = 分割线上或分割线上的所有顶点的集合

B = 所有剩余顶点的集合

4) 从 A 的最左边的顶点开始，连接 A 中的所有顶点，直到到达最右边

5 ) 如果排序集 V 的最右边的顶点（具有最大 x 坐标的顶点）不在 A 中，则将最后一个顶点（A 的最右边）与其连接。

6) 向后工作，从排序集 V 的最右边的顶点（具有最大 x 坐标的顶点）开始，连接 B 中的所有顶点

7) 将 B 的第一个（B 的最左边的顶点）顶点与最左边的顶点连接起来 我认为该算法

---

是正确的，并且找不到它会失败的测试，但也许我遗漏了一些东西。

如果您能看一下并给我一个如果有的话就不起作用的例子（我确信一定有），我将不胜感激。

Answer 1

这是一个反例。当第5步没有画线时，就有可能自相交。

Answer 2

我不确定我是否正确理解你想要做什么。在另一个线程中，以及 相应的线程中在 math.SE（它把我带到这里），你说你有一个多边形并试图找到它的重心。在这里，您说您有一组点，并且您想从中构造一个不相交的多边形。这是两件完全不同的事情。正如我在 math.SE 中提到的，如果不知道多边形是凸的，则一组点不会唯一定义一个多边形 - 因此您在这里提出的算法可能会构造一些任意的非自相交多边形（我还没有没有检查它是否成功做到了这一点）但这可能与您最初感兴趣的多边形有任何关系，也可能没有任何关系。或者我是否误解了您在 math.SE 上的问题，而您实际上只有一些点并且只想构造任何点来自它们的非自相交多边形并且不关心可能有几个不等价的解决方案？

Answer 3

我想我有一个更简单的算法来创建这样的多边形。用软件实现可能比较困难，但用文字描述要容易得多。

• 选择集合中的任意一点作为起点。从它开始以 0 角度创建一条线。
• 开始围绕该点旋转线。当它遇到任何其他点时，从起点到新找到的点绘制一条边。
• 继续围绕起点旋转，将任何新找到的点与最后找到的点连接起来。
• 旋转结束时，通过满足起点来闭合形状。

如果在一个方向上有多个发现，请选择一个方向将它们连接起来（例如，从最内层开始到最外层结束）

形状通常有点像星形，但满足要求。

计算执行类似于：

• 将所有点平移到以其中一个点为原点[0,0]的坐标集。
• 将所有点转换为极坐标集
• 排序方式：角度升序、半径升序。
• 按排序顺序连接所有点。
• 最后连接到第一个 ([0,0]) 点。

Answer 4

我将通过将“分隔线”设置为最左边和最右边的点之间的连接，而不是平行于 x 轴来证明这一点略有不同。可能会发生平行于 x 线下方或上方没有点的情况，这可能会给您的证明带来麻烦。

此外，连接 (5) 可能会导致与点 (6) 中生成的连接发生一些自相交。

还有一种特殊情况，即所有点共线并且多边形退化为一条线。

我们假设顶点集 V 是有限的；）

除此之外 - 我相信你的说法是正确的。

Answer 5

我在 javascript 和 OpenLayers 库中遇到了同样的问题。所以这是我的解决方案，用于检测“矢量”层中多边形作为 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;
    }
  }
}

希望您喜欢它！