将弱简单多边形分割成真正的简单多边形或多个多边形

Question

将弱简单多边形分割成真正的简单多边形或多个多边形

9

我希望将弱简单多边形分割成简单多边形。

背景

使用情况是通过Javascript Clipper简化（联合）多边形。 Javascript Clipper以及原始Clipper的 SimplifyPolygon()函数会删除自交并组合公共边，但无法生成真正的简单多边形。输出用于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多边形的图像：

enter image description here

这里是编号的点，您可以轻松地看到哪些点是重复的：

enter image description here

正如您所看到的，上面的多边形可以以多种方式分割，例如：
- 一个外部多边形带有五个孔 - 五个外部多边形中的一个具有一个孔

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

简单多边形是没有自交、无重复坐标（无论它们是顺序还是非顺序）、没有洞的多边形。输出的简单多边形可以有顺时针或逆时针的绕向顺序。顺时针表示外部，逆时针表示内部。

输出可以有（并且很多情况下会有）洞，但在某些情况下输出没有洞。输出始终至少有一个外部多边形，但也可能有多个外部多边形，这些多边形可以有零个或多个孔。

输出应该是一个 exPolygon 对象数组，具有 "outer" 和 "holes" 属性。"outer" 是一个点对象数组，"holes" 是一个点对象数组的数组。如果 "holes" 中有填充内容，则其中的孔必须是 exPolygon 对象中 "outer" 多边形的孔。

输出的示例：

// 这是一种输出示例，但点是随机的： [ { "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": [] } ];

输出的 "outer" 多边形是顺时针的，而 "holes" 是逆时针的。

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

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

这是一个输入多边形的示例：

这是它如何被分割的示例：

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

如何将多边形分割成这样，并实现所需的输出结构？我不是要求完整的代码（但如果你有空闲时间并想证明它是可能的，那就更好了）。欢迎提出可能的算法思路。

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

如果您想尝试解决方案，我在此提供了一段代码，用于查找重复项：http://jsbin.com/unuyev/7/edit。它显示多边形的SVG，并显示点为红色圆圈和每个点的数组索引（按“Run with JS”按钮后）。

这里是相同的内容，但包含12个示例多边形（在Javascript窗口中更改pindex以更改多边形）：http://jsbin.com/unuyev/4/edit

编辑：Javascript Clipper 6 现已推出，并支持 StrictlySimple。但根据文档，“目前不能保证多边形严格简单，因为‘简化’仍然是一个正在进行的工作”。我已经测试了 StrictlySimple 并在某些情况下失败：方向问题和缺乏旋转不变性。我们希望这些问题能尽快得到解决，StrictlySimple 能够正常工作。

- Timo Kähkönen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vivin Paliath · Accepted Answer

我可能遗漏了一些东西，但这看起来像是一个典型的图形寻找关节顶点的问题。本质上，您正在尝试找到图形中最薄弱的点，使得当您在该点处切断图形时，您最终得到两个单独的图形。因此，在您的示例中，如果您在那个顶点处切割多边形，则会得到多个多边形。您可以将多边形表示为图形，每个顶点表示一个图形顶点，而多边形边缘则表示图形边缘。

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

《算法设计手册》中的关节顶点 - 这是你最好的选择。他用简单的语言解释了算法，并提供了C代码，你可以很容易地将其翻译成JavaScript。如果我要开始写一个算法，这就是我会开始的地方。
双连通分量
关节点检测（搜索“articulation”）

更新

我将尝试简要介绍问题和解决方案，指引你朝正确的方向前进。使用图形实现此算法必然涉及到图算法术语，因此如果您不熟悉图形，请先了解一下。

在您的情况下，暴力方法是遍历图形，临时删除每个顶点，然后查看修改后的图形在进行DFS / BFS遍历时是否连接。这不是很高效，运行时间为二次方 O（n（m + n））。但是有一种基于对结果DFS树的边进行分类的线性时间算法。

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

删除树的根节点取决于它是否有一个或多个子节点。如果它只有一个子节点，那么它就是一个叶子节点，因此删除它将没有任何影响。但是，删除具有多个子节点的根节点将断开图形。

但在一般的图中，您可以拥有反向边，因此删除之间的任何节点不会断开图形。因此，找出关节顶点归结为确定哪些部分与祖先节点通过反向边连接（即确定顶点的“可达祖先”）。

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

希望这能帮助您入门！