标签: medial-axis

我想对带有孔的复杂(但不是自相交)多边形进行三角测量,以便生成的三角形全部位于多边形内部,完全覆盖该多边形,并遵守Delaunay三角形规则.

显然,我可以为所有点构建Delaunay三角剖分,但是我担心多边形的某些边缘不会被包含在生成的三角剖分中.

那么,这样的三角测量可能吗？如果是,我该怎么办？

以防万一 - 我需要它来构造多边形中轴的近似(我希望它可以通过连接所得三角形的所有圆周点来完成).

我正在编写一个程序,需要实现Medial Axis提取,其中Delaunay三角测量是一个步骤.外部中轴是不需要的,因此要删除相应的外部三角形.幸运的是,我遇到了一个包含大量图表的页面,还有一个确定内部和外部Delaunay三角形的方法("基于虚线周长"),但它只是一个提示,没有详细的解释.谁知道算法？

编辑:我忘了提到从闭合多边形的边界采样的初始点,我的目的是确定每个Delaunay三角形是否在多边形内.

我的任务是弄清楚如何找到多边形的中心线.我的谷歌搜索让我相信我所需要的是'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边缘.

我可以在这些顶点看到我需要的材料,但我不确定下一步需要过滤掉我不需要的所有东西.

我很感激您提供的任何帮助.

我将2D形状存储为SVG中的路径元素。形状由贝塞尔曲线和线段组成。

我在使用弧长参数化生成的形状上也有一组等距的点。

如何使用SVG或这些点确定形状的中轴？

我正在使用Python，但是任何形式的伪代码或算法建议都将不胜感激。

以下是我正在处理的形状类型的示例，红色点是沿曲线的采样点。