8

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

背景

用例是使用Javascript Clipper简化已简化（联合）的多边形。Javascript Clipper 和原始 Clipper 的 SimplifyPolygon()功能一样，去除了自相交并组合了公共边，但它不能生成真正的简单多边形。输出用于three.js，TriangulateShapes()它需要多边形简单。Three.js 接受具有一个轮廓和零个或多个孔的多边形结构。

输入，弱简单多边形

弱简单多边形不能有顺序重复顶点（真正的重复点），也不能有孔（岛），也不能有自相交（边与另一条边交叉），但可以有非顺序多顶点（具有完全相同的坐标但不是顺序的）。输入多边形可以有 CW 或 CCW 缠绕顺序，这意味着 CW 输入是外部多边形，CCW 是一个孔。输入是 CW 或 CCW 多边形。

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

// 这是一个弱简单多边形的真实例子：

var 输入 = [{"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 对象中“外部”多边形的孔。

输出示例：

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

[ { "外": [{"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 个示例多边形（pindex在 Javascript 窗口中更改以更改多边形）：http: //jsbin.com/unuyev/4/edit

编辑：Javascript Clipper 6现在可用，并且支持StrictlySimple. 但是根据文档“目前不能保证多边形会严格简单，因为'简化'仍在进行中”。我已经测试了 StrictlySimple，但在某些情况下它会失败：方向问题和缺乏旋转不变性。我们希望这些问题尽快得到修复StrictlySimple并按预期工作。

4

1 回答 1

2

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

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

更新

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

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

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

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

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

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

希望这可以帮助您入门！

于 2013-04-24T17:15:42.647 回答