我的任务是弄清楚如何找到多边形的中心线 . 我的谷歌搜索让我相信我所需要的是'Medial Axis' . 像这样：
（来源：kiev.ua）
根据我所读到的，我可以通过使用2D Voronoi图构造算法来生成我需要的东西 .
我在codeplex（FortuneVoronoi）上找到了Voronoi算法的C＃版本，在将多边形应用到它之后，我最终得到了这个：
alt text http://www.carbonatlas.com/geonotes/gaia_voronoi.png
绿色是原始多边形 . 橙色是Voronoi顶点，黑色线是voronoi边缘 .
我可以在这些顶点看到我需要的材料，但我不确定下一步需要过滤掉我不需要的所有东西 .
我很感激您提供的任何帮助 .
3 回答
一个简单的解决方案将如评论中所建议：
构建多边形顶点的Delaunay三角剖分 .
识别多边形内的Voronoi顶点（参见http://en.wikipedia.org/wiki/Point_in_polygon）
输出连接两个内部Voronoi顶点的Voronoi边 .
如果您有大量数据，交叉路口可能会非常昂贵 .
那么你可以像question那样做类似的方法，this solution也适合你 . 我会这样做的方式：
构建多边形顶点的Delaunay三角剖分 .
插入未被delaunay边缘覆盖的每个多边形边的中点 . 递归执行此操作，直到所有多边形边都被Delaunay边覆盖 .
标记对应于多边形边的所有Delaunay边 .
使用步骤3.-5提取中轴 . 在this solution
PS . 请注意，这两个解决方案都给出了一些近似的中轴，计算它的成本要高得多，但作为预告片...你可以得到这样的结果用于黑色输入采样点：
类似的构造是Straight skeleton，它可以通过将多边形收缩到自身并在顶点接近中心时跟踪顶点来构造 . 这可能更容易构建，尽管它与中轴的曲线不完全相同 .
哇 . 我打算在这里走出去，并建议可能算法混淆了多边形的内部与外部 . 定义原始多边形的边和顶点时，必须确保它们的定义方式是始终使用“右手规则”之类的内容找到“内部” . 只看右下角的多边形，看起来多边形的边缘实际上就是自身交叉 . 也许算法会将该部分和其他部分视为“由内而外” . 左下角也是如此 .
这是我的直觉，该算法似乎无法确定内部和外部的方向 .
我认为一种天真的方法是过滤掉多边形之外的所有Voroni“节点”，但是，我认为不会这样 . 仔细查看您的图表，看起来每个节点有3条边连接到其他节点 . 也许您可以过滤掉3个边中的任何边连接到多边形外部节点的节点 . 那会有用吗？