问题标签 [medial-axis]

我正在编写一个需要实现中轴提取的程序，其中 Delaunay 三角剖分是其中的一个步骤。外部中轴是不需要的，因此打算移除相应的外部三角形。幸运的是，我找到了一个有很多图表的页面，也提示了确定内部和外部德劳内三角形的方法（“基于折线周长”），但这只是一个提示，没有详细解释。有人知道算法吗？

编辑：我忘了提到初始点是从封闭多边形的边界采样的，我的目的是确定每个德劳内三角形是否在多边形内。

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

_{（来源：kiev.ua）}

根据我所阅读的内容，可以通过使用 2D Voronoi 图构造算法来生成我需要的内容。

我在 codeplex (FortuneVoronoi) 上找到了 Voronoi 算法的 C# 版本，在将我的多边形应用到它之后，我得到了这个：

替代文字 http://www.carbonatlas.com/geonotes/gaia_voronoi.png

绿色是原始多边形。橙色是 Voronoi 顶点，黑色线条是 voronoi 边缘。

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

我很感激你能提供的任何帮助。

有谁知道如何计算两条给定曲线的中轴？

中轴：http ://en.wikipedia.org/wiki/Medial_axis

这是我需要计算的形状：

我自己画了中轴，深黑线，但我需要能够动态计算它。

这是我到目前为止所做的小程序和代码：http: //www.prism.gatech.edu/~jstrauss6/3451/sample/

已知变量是： -pt A、B、C、D - 红色、绿色和黑色圆圈的半径 -pt Q 和 R（就在图片之外），黑色圆圈。

我有兴趣寻找软件来计算 3D 多面体的精确中轴（或您选择的术语！）。我想输出将是一个三角形面列表，可能是边和顶点，代表内侧表面的连接点、薄片和接缝。理想情况下，我想要可以处理所有多面体的东西，包括凹形（此时三角形面还不够），但我很高兴找到可以处理凸多面体的东西。

先说一下我知道的软件：

有多种“近似”方法可用，它们假设我正在变换的形状是一个复杂的表面，并且通过在表面上散布密集点来实现。
其中一种方法是http://www.cs.ucdavis.edu/~amenta/powercrust.html提供的powercrust软件 （虽然应该如何为这个软件定义点文件以便正确处理凹面情况，但我不是当然）

另一种近似方法集成到 Tight Cocone (http://www.cse.ohio-state.edu/~tamaldey/cocone.html)。这再次将点密集分布在表面上，并使用 voronoi 图收敛到中轴。有一个“改进的 CAD 模型中轴”版本，它利用了表面完全已知的事实。然而，这种改进的模型并未并入分布式代码中。

有一个 Matlab 代码，例如 Gianni Schena (http://www.mathworks.com/matlabcentral/fileexchange/4917-skeleton-in-3d) 的“3D 骨架”，它使用了几个基于距离的简单方法转换。还是近似的。

显然，近似方法可能会受到某些类型的数值不稳定性的影响，从而使表面出现“尖峰”。此外，它们会生成非常大的面和顶点数据结构。我想要的是一个多面体（如立方体）的中轴/表面的精确表示，它应该有一个非常简单和小的数据结构。

在 [2004, Culver, Keyser, and Manocha, Exact Computation of the Medial Axis of a Polyhedron] 中，发表了一种计算多面体精确中轴的方法。但是，我找不到任何有人实际实现了这种方法的软件。

有人知道什么，或者有什么可以添加到我对 3D 内表面软件的小尝试中吗？

我想用孔对复杂的（但不是自相交的）多边形进行三角剖分，以便生成的三角形都位于多边形内，完全覆盖该多边形，并遵守德劳内三角形规则。

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

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

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

是否可以为一个复杂的非凸多边形构造一个中轴，该多边形在次二次时间中有孔？你能指出我的算法解释吗？

或者也许在Java中有一个库？

我需要获得这些图片上显示的内容：

我认为它与中轴变换有关，但我只需要垂直或水平线。有什么建议么？

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

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

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

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

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

有没有人知道一种简单的方法，给定一个二进制图像，构造一个变换，对于边界上的每个点（轮廓集像素）返回它最接近的中轴上的点？

我想近似一个封闭的多边形，但 PostGIS 给我的不是一个干净的线串，而是带有 3 个线串的多线串。都是因为直骨架上留下的那条小尾巴。 有没有合适或好的方法来处理这个问题？