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

Question

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

背景

用例是使用 Javascript Clipper 来简化已简化(联合)的多边形。 . Javascript Clipper 以及 original Clipper's SimplifyPolygon()函数去除自相交并合并公共(public)边，但它不能产生真正的简单多边形。输出用于three.js，其中有TriangulateShapes()这需要多边形很简单。 Three.js 接受具有一个轮廓和零个或多个孔的多边形结构。

输入，弱简单多边形

弱简单多边形不能有连续重复顶点(真正的重复点)，也不能有孔(岛)或自相交(边与其他边交叉)，但可以有非连续多顶点(顶点恰好具有相同的坐标但不是连续的)。输入多边形可以有 CW 或 CCW 缠绕顺序，这意味着 CW 输入是外部多边形，CCW 是一个孔。输入是 CW 或 CCW 多边形。

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

//这是弱简单多边形的真实示例:

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 孔。

输出可能有(并且在很多时候会有)孔，但在某些情况下，输出没有孔。输出总是至少有一个外部多边形，但也可以有多个具有零个或多个孔的外部多边形。

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

输出示例:

//这是一个输出示例，但点是随机的:

[ { "外": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{ "X":10,"Y":50}],
“洞”:[[{“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}]]},
{“外”:[{“X”:54，“Y”:4}，{“X”:2，“Y”:50}，{“X”:30，“Y”:5}，{“X":10,"Y":50}],
“洞”:[[{“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}]]},
{“外”:[{“X”:54，“Y”:4}，{“X”:2，“Y”:50}，{“X”:30，“Y”:5}，{“X":10,"Y":50}],
“洞”:[] }
];

输出的“外部”多边形是 CW，而“孔”是 CCW。

多边形中的点数、exPolygons 对象数和孔数没有限制。

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



除法示例

这是输入多边形的示例:



以下是它的划分方式:



其他一些多边形可以有多种可能的输出选择，具体取决于伪重复点的位置。

我的问题

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

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

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

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

编辑:Javascript Clipper 6现已推出，并支持 StrictlySimple .但是根据文档“目前不能保证多边形会严格简单，因为'简化'仍在进行中”。我已经测试过 StrictlySimple，但在某些情况下它会失败:Orientation problems和 lack of rotation invariance .我们希望这些问题很快得到解决和 StrictlySimple按预期工作。

Answer 1

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

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

Articulation vertices from the Algorithm Design Manual - 这是你最好的选择。他用简单的术语解释了算法，还为您提供了可以轻松转换为 JavaScript 的 C 代码。如果我必须开始编写算法，这就是我要开始的地方。

Biconnected component

Detection of Articulation Points (搜索“清晰度”)

更新

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

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

在不包含任何后缘的 DFS 树中(将“较低”节点连接到树中“较高”节点的边[假设“较高”节点是那些更靠近根的节点])叶节点不是关节节点，因为删除它们中的任何一个仍然会使图形保持连接。但是，删除任何内部节点都会断开其后的所有节点与根节点的连接。

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

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

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

希望这可以帮助您入门!