c# - 使用 C# 查找多边形的中轴

Question

我的任务是弄清楚如何找到多边形的中心线。我的谷歌搜索让我相信我需要的是所谓的“中间轴”。像这样：

_{（来源：kiev.ua）}

根据我所阅读的内容，可以通过使用 2D Voronoi 图构造算法来生成我需要的内容。

我在 codeplex (FortuneVoronoi) 上找到了 Voronoi 算法的 C# 版本，在将我的多边形应用到它之后，我得到了这个：

替代文字 http://www.carbonatlas.com/geonotes/gaia_voronoi.png

绿色是原始多边形。橙色是 Voronoi 顶点，黑色线条是 voronoi 边缘。

我可以在这些顶点中看到我需要的东西，但我不确定下一步需要过滤掉所有我不需要的东西。

我很感激你能提供的任何帮助。

Answer 1

一个简单的解决方案将如评论中所建议的那样：

1. 构建多边形顶点的 Delaunay 三角剖分。
2. 识别多边形内的 Voronoi 顶点（参见 http://en.wikipedia.org/wiki/Point_in_polygon）
3. 输出连接两个内部 Voronoi 顶点的 Voronoi 边。

如果您有大量数据，则交叉点可能会非常昂贵。

然后你可以像问题中那样做类似的方法，这个解决方案也可以为你工作。我会这样做的方式：

1. 构建多边形顶点的 Delaunay 三角剖分。
2. 插入未被 delaunay 边覆盖的每个多边形边的中点。递归执行此操作，直到所有多边形边缘都被 Delaunay 边缘覆盖。
3. 标记与多边形边相对应的所有 Delaunay 边。
4. 使用步骤 3.-5 提取中轴。在这个解决方案中

PS。请注意，这两种解决方案都给出了中轴的近似值，精确计算它的成本要高得多，但作为一个预告片......对于黑色输入样本点，您可以获得这样的结果：

Answer 2

一个类似的构造是Straight 骨架，它可以通过将多边形缩小到自身并在顶点接近中心时跟踪顶点来构造。这可能更容易构建，尽管它与中轴的曲线并不完全相同。

Answer 3

哇。我将在这里冒险并建议该算法可能对多边形的内部与外部感到困惑。当您定义原始多边形的边和顶点时，您必须确保它们的定义方式始终使用“右手定则”之类的方法找到“内部”。只看右下角的多边形，看起来多边形的边缘实际上与自身相交。也许算法将该部分和其他部分视为“由内而外”。左下角也一样。

这是我的直觉，算法似乎无法确定内部方向和外部方向。

我认为一种天真的方法是过滤掉多边形外部的所有 Voroni “节点”，但是，我认为这不会。仔细查看您的图表，看起来每个节点都有 3 条边将其连接到其他节点。也许您可以过滤掉 3 条边中的任何一条连接到多边形外部节点的节点。那行得通吗？