将弱简单多边形拆分为真正的简单多边形或多边形

Question

我想将弱的简单多边形划分为简单的多边形.

背景

用例是使用Javascript Clipper简化简化(联合)的多边形.Javascript Clipper以及原始的Clipper SimplifyPolygon()函数删除了自交叉并组合了常见的边缘,但它无法生成真正的简单多边形.输出用于three.js,其中TriangulateShapes()多边形需要简单.Three.js接受具有一个轮廓和零个或多个孔的多边形结构.

输入,弱简单多边形

弱简单多边形不能具有顺序复制顶点(真实重复点),也不能具有孔(岛)或自交叉(边缘跨越其他边缘),但可能存在非顺序多顶点(顶点具有完全相同)相同的坐标但不是顺序的).输入多边形可以具有CW或CCW绕组顺序,这意味着CW输入是外多边形而CCW是一个孔.输入是CW或CCW多边形.

输入是一个多边形点数组,例如:

// This is a true example of weakly-simple polygon:

var input = [{"X":270,"Y":520},{"X":130,"Y":490},{"X":210,"Y":250},{"X":60,"Y":170},{"X":130,"Y":490},{"X":20,"Y":410},{"X":60,"Y":300},{"X":60,"Y":20},{"X":780,"Y":40}, {"X":680,"Y":180},{"X":460,"Y":130},{"X":210,"Y":250},{"X":320,"Y":100},{"X":220,"Y":80}, {"X":210,"Y":250},{"X":520,"Y":250},{"X":680,"Y":180},{"X":770,"Y":480},{"X":540,"Y":470}, {"X":520,"Y":250},{"X":380,"Y":280},{"X":430,"Y":390},{"X":540,"Y":470},{"X":270,"Y":520},{"X":330,"Y":350},{"X":210,"Y":250}];

这是上面的input多边形作为图像:

以下是编号的点,您可以在其中轻松查看哪些点是重复的:

如您所见,上面的多边形可以分为多种方式,例如:
- 一个外部多边形,五个孔 - 五个外部多边形,其中一个有一个孔

输出,简单多边形作为exPolygon结构

简单多边形是一个没有自相交的多边形,没有重复坐标,无论它们是顺序还是非顺序,没有孔.输出的简单多边形可以具有CW或CCW绕组顺序.CW表示外部和CCW孔.

输出可能有(并且很多时候会有)孔,但在某些情况下输出没有孔.输出始终至少有一个外部多边形,但也可能有多个外部多边形具有零个或多个孔.

输出应该是具有"外部"和"孔"属性的exPolygon对象数组."outer"是点对象的数组,"holes"是点对象数组的数组.如果填充"孔",则其中的孔必须是exPolygon对象中的"外"多边形孔.

输出的例子:

// This is an example of output, but the points are random:

[ { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}],
    "holes": [ [{"X":0,"Y":8},{"X":60,"Y":13},{"X":21,"Y":2},{"X":3,"Y":1}],
               [{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}] ] },
  { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}],
    "holes": [ [{"X":0,"Y":8},{"X":60,"Y":13},{"X":21,"Y":2},{"X":3,"Y":1}],
               [{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}] ] },
  { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}],
    "holes": [] }
];

输出的"外"多边形是CW,"孔"是CCW.

多边形中的点数,exPolygons对象的数量和孔的数量没有限制.

以下是弱简单多边形的其他示例:

分裂的例子

以下是输入多边形的示例:

以下是它的划分方式:

其他一些多边形可以有多种可能的输出替代方案,具体取决于伪重复点的位置.

---

我的问题

如何以这种方式划分多边形并实现所需的输出结构？我不是要问完整的代码(但是如果你有空闲时间并希望证明它是可行的).对可能的算法的想法也是受欢迎的.

---

我搜索了几个小时的解决方案,并试图找到一个算法.

如果你想尝试一个解决方案,我在这里有一个代码,我用它来找到重复项:http://jsbin.com/unuyev/7/edit.它在SVG中显示多边形,并将点显示为红色圆圈和每个点的数组索引(按下"Run with JS"按钮后).

这是相同的,但有12个示例多边形(pindex在Javascript窗口中更改以更改多边形):http: //jsbin.com/unuyev/4/edit

---

编辑:Javascript Clipper 6现已上市,并且有支持StrictlySimple.但根据文档"目前无法保证多边形将严格简单,因为'简化'仍然是一项正在进行中的工作".我测试了StrictlySimple,在某些情况下它失败了:方向问题和缺乏旋转不变性.我们希望这些很快得到解决,StrictlySimple并按预期工作.

---

Answer 1

我可能遗漏了一些东西，但这看起来像是寻找图形的铰接顶点的经典问题。本质上，您试图找到图表中最薄弱的点，这样当您在该点切割图表时，您最终会得到两个单独的图表。因此，在您的示例中，如果您在该顶点切割多边形，最终会得到多个多边形。您可以很容易地将多边形表示为图形，每个顶点表示图形顶点，多边形边表示图形边。

如果我必须解决这个问题，这就是我会采取的方法。您可以查看以下资源：

• 算法设计手册中的关节顶点- 这是您最好的选择。他用简单的术语解释了该算法，并为您提供了可以轻松转换为 JavaScript 的 C 代码。如果我必须开始编写算法，我就会从这里开始。
• 双连通分量
• 关节点检测（搜索“articulation”）

更新

我将尝试向您简要概述问题和解决方案，为您指明正确的方向。使用图实现该算法必然会涉及图算法术语，因此如果您不熟悉图，您可能需要阅读它们。

在您的情况下，强力方法是遍历图形，暂时删除每个顶点，然后在修改后的图形上进行 DFS/BFS 遍历时查看图形是否已连接。这不是很有效并且会以二次方的时间运行O(n(m + n))。但是有一种线性时间算法，它基于对 DFS 遍历形成的结果 DFS 树的边进行分类。

在不包含任何后边的 DFS 树中（将树中“较低”节点连接到“较高”节点的边[假设“较高”节点是靠近根的节点]）叶节点不是铰接节点，因为删除其中任何一个仍会使图保持连接。但是，删除任何内部节点都会断开其后面的所有节点与根的连接。

删除树的根取决于它是否有一个或多个子节点。如果它只有一个子节点，那么它或多或少是一片叶子，因此删除它不会产生任何效果。但是，删除具有多个子节点的根节点将断开图的连接。

但在一般图中，您可以有后边，因此删除中间的任何节点都不会断开图。因此，找出关节顶点归结为找出树的哪些部分通过后边链接到祖先节点（即，找出顶点的“可到达祖先”）。

在我从算法设计手册链接到的页面中，Skiena 描述了顶点可以是关节顶点（根、桥和父切割节点）的三种情况。使用他描述的算法，您可以确定正在处理的顶点是否满足这些条件中的任何一个。如果是，则它是一个铰接节点。

希望这可以帮助您入门！