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

Question

我被委托找到如何找到多边形的中心线。我的谷歌搜索让我相信我需要的是所谓的“中轴线”。就像这样：

_{(来源：kiev.ua)} 据我所读，我需要的可以通过使用二维Voronoi图构造算法来生成线段。

我在codeplex上找到了一个C#版本的Voronoi算法（FortuneVoronoi），在将我的多边形应用于它之后，我得到了这个结果：
alt text http://www.carbonatlas.com/geonotes/gaia_voronoi.png 绿色是原始多边形，橙色是Voronoi顶点，黑线是Voronoi边缘。

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

如果您能提供任何帮助，我将不胜感激。

- mdm20

---

你的一张图片丢失了。 - Caio Iglesias

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.提取中轴线

注意，这两种解决方案都给出了一些关于中轴线的近似值，精确计算成本更高，但是可以通过以下样本点的黑色输入获得结果：

- balint.miklos

Answer 2

类似的结构是直骨架，可以通过将多边形收缩到自身并跟踪顶点接近中心来构造。这可能更容易构建，但它不完全是介于两侧的曲线。

- SingleNegationElimination

Answer 3

哇，我要冒险猜测一下，也许算法对多边形内部和外部的定义有些混淆。当您定义原始多边形的边缘和顶点时，必须确保它们以“右手定则”等方式定义，以便始终可以找到“内部”。仅看右下角的多边形，它似乎实际上穿过了多边形的边缘。也许算法将该部分和其他部分视为“内部外部颠倒”。左下角也是如此。

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

我认为一个天真的方法是过滤掉所有在多边形外部的 Voroni“节点”，但我认为那样做不会奏效。仔细观察您的图表，每个节点似乎都有连接到其他节点的3条边缘。也许您可以过滤掉任何一条边缘连接到多边形外部节点的节点。这样行得通吗？

- Scott Whitlock

---

确实。生成的 Voronoi 集在多边形内部和外部都有定义。（事实上，Voronoi 集算法并不要求生成集是多边形，甚至不需要是连续连接的集合。）原帖作者只对 Voronoi 集区域的边界感兴趣，这些边界在 poly 内部。因此，构建一个算法来过滤掉不在 poly 内部的 Voronoi 集边界。确定给定点是否在 poly 内部并不难。 - Eric Lippert