使用 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

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

Answer 3

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

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

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