一个用于创建非自交多边形的算法的有效性

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顶点）顶点与A的最左侧顶点连接起来。

---

我认为该算法是正确的，找不到它会失败的测试，但也许我漏掉了什么。

如果可以的话，我希望你能看一下并给我一个例子，证明它无法工作（我相信一定有）。

- mixkat

Answer 1

这里有一个反例。当第5步没有画线时，可能会出现自相交的情况。

- Null Set

---

是的！我自己画了一个类似的！布局很好！谢谢！好事是我最终不需要算法了！ - mixkat

Answer 2

我不确定我是否正确理解了您的意图。在另一个帖子和数学交流网站上对应的帖子中（这也是我来到这里的原因），您说您有一个多边形，并试图找到它的重心。而在这里，您说您有一组点，并且想从中构建一个非自交的多边形。这是两件完全不同的事情。正如我在数学交流网站上所提到的，如果这些多边形不被认为是凸的，一组点并不能唯一地定义一个多边形——因此您在这里提出的算法可能会构造出一些任意的非自交多边形（我还没有检查它是否成功完成了这个任务），但这些多边形可能与您最初感兴趣的多边形毫无关系。或者我在数学交流网站上误解了您的问题，您实际上只有一些点，并且想从中构建出任何非自交多边形，而不关心可能存在几个不等价的解决方案？

- joriki

---

@joriki 对不起，我没有解释清楚！我最初是想找到一种算法，可以计算任何给定多边形（自相交或非自相交）的重心。然而，由于我没有实际的多边形，只有一组点，所以我认为我可以“绘制”多边形，使其永远不会自相交。这基本上就是我正在尝试使用此算法做的事情。这样我就可以应用重心公式了。 - mixkat

@mixkat：听起来像是一个定义不清的问题。你是怎么得到这些点的？你怎么知道从它们中形成的任何多边形的重心是相关的？从相同的点构造出的不同多边形的重心可能会有很大的差异。例如，想象一下一个点几乎位于另外两个点之间，但略微“向内”——你可以将它连接在那两个点之间，或者你可以将它连接在相反侧的两个点之间，结果会截然不同。也许你真正感兴趣的是凸包吧！ - joriki

@joriki 你说得对，质心可能会有很大的变化。我的最终算法需要考虑到每个点的坐标，这就是为什么我不考虑凸包的原因。正如我所说，主要思想是计算一群人的最近集合点。我想多边形的质心并不总是最准确的结果，但应该足够好了。 - mixkat

@mixkat：抱歉，我可能错过了“一群人最近的会面点”这部分；我不知道你在哪里写了那个。既然如此，我不明白为什么你还要费心去计算多边形。为什么不直接计算这些人的重心呢？即 $\sum_{i=1}^n \vec{x}_i/n$。这是最小化人们与会面点距离平方和的解决方案。我看不出为什么要引入多边形。 - joriki

@joriki 不不不，没关系！这不是你的错，是我数学技能的问题！真的那么简单吗？简直不敢相信我花了两天时间来解决这个问题！有时候你只是过于复杂化了事情！我一直把它想象成一个多边形，但它是该死的坐标系吧？当然你可以得到它们的平均值！太棒了！非常感谢你！你确实帮了我很多！ - mixkat

Answer 3

我认为我有一个更简单的算法可以创建这样的多边形。在软件中可能更难实现，但用语言描述起来更容易。

• 从集合中选择任意一点作为起点。从该点开始创建一个0度角的直线。
• 开始绕着这个点旋转这条直线。当它遇到任何其他点时，从起始点到新发现的点画出一条边。
• 继续围绕起点旋转，连接任何新发现的点与上一个发现的点。
• 在旋转结束时，通过与起点相遇来关闭形状。

如果在一个方向上有多个发现，则连接它们时选择一个方向（例如，从最内部开始，以最外部结束）

该形状通常类似于星形，但符合要求。

计算执行步骤如下：

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

- SF.

---

感谢您的输入，不过在代码中实现会更困难一些。看起来应该可以（还没有实际检查）。 - mixkat

@joriki：我认为你误解了算法。它不会在进行操作时切换旋转点，并且它肯定适用于所有点。例如：http://i54.tinypic.com/24zzt4m.png - SF.

你是对的，我误解了算法。对此感到抱歉。 - joriki

Answer 4

我会通过将“分隔线”设置为连接最左和最右点而不是与x轴平行来稍微证明一下。可能会出现没有点在平行于x线下方或上方的情况，这可能会对您的证明造成麻烦。

此外，连接（5）可能会导致与点（6）生成的连接发生自交。

还有一种特殊情况，即所有点都共线，您的多边形退化为一条直线。

我们假设顶点集V是有限的;)

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

- CygnusX1

---

谢谢回复!!! [1]“还有一种特殊情况，当所有点共线时，你的多边形会退化成一条线。”这实际上是一个有效的观点!!! [2]你能举个例子吗：“此外，连接（5）可能会导致与在点（6）生成的连接发生自相交。” [3]“可能出现没有点在平行于x轴的线下或上，这可能会对你的证明造成麻烦。” 这和[1]一样吗？ - mixkat

Answer 5

我在JavaScript和OpenLayers库中遇到了同样的问题。这是我检测“向量”图层中多边形有效性的解决方案：

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

希望你喜欢它！

- hadilq