4

作为对我的线程的扩展和部分回答，我编写了一个简单的算法，给定一组点（带有 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的最左边的顶点）顶点和A的最左边的顶点

我认为该算法是正确的，找不到会失败的测试，但也许我遗漏了一些东西。

如果您能看一下并给我一个示例，如果有的话，我将不胜感激（我确信必须有）。

4

5 回答 5

3

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

反例

于 2011-03-12T00:57:54.963 回答
2

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

于 2011-03-11T22:42:17.207 回答
2

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

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

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

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

计算执行如下：

  • 将所有点转换为在其中一个点中使用 origin[0,0] 的坐标集。
  • 将所有点转换为极坐标集
  • 排序方式：角度升序，半径升序。
  • 按排序顺序连接所有点。
  • 最后连接到第一个 ([0,0]) 点。
于 2011-03-11T22:45:47.327 回答
1

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

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

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

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

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

于 2011-03-11T22:33:05.903 回答
0

我在 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;
    }
  }
}

希望你喜欢它！！

于 2013-06-13T15:54:47.903 回答