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

Question

我的任务是弄清楚如何找到多边形的中心线.我的谷歌搜索让我相信我所需要的是'Medial Axis'.像这样:

替代文字http://www.ndl.kiev.ua/downloads/center_line.png

根据我所读到的,我可以通过使用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.请注意,这两个解决方案都给出了一些近似的中轴,计算它的成本要高得多,但作为预告片...你可以得到这样的结果用于黑色输入采样点: