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

Question

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

_{（来源： 基辅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 提取中轴。在 这个解决方案

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

Answer 2

一个类似的结构是直骨架时，其可以通过缩小多边形分割成构成本身和跟踪顶点，他们的做法中心。这可能是更容易一些构造，虽然它并不像中轴同一曲线。

Answer 3

哇。我要在这里走出去的肢体，并建议也许算法是困惑的内部与多边形的外侧。当你定义的边缘，你原来的多边形顶点，你必须确保他们以这样的方式“内部”始终使用类似的“右手法则”发现定义。只要看看在右下角的多边形，它看起来像你的多边形的边缘实际上与自身交叉。也许算法是看到这一节，和其他人，如“内而外”。在左下角的相同。

这是我的直觉，该算法似乎并不能够确定什么方向是内部的，哪些是外部的。

我觉得一个幼稚的方法将过滤掉所有Voroni“节点”是多边形之外，但是，我不认为会看。在您的图表左看右看，它看起来像每个节点有3个边，它连接到其他节点。也许可以过滤掉，其中任何3个的边缘被连接到多边形之外的节点的节点。将这项工作？