我正在做一些工作(过于复杂无法解释),其中一个任务是将平滑多边形的光栅图像转换为骨架。因此,我需要做类似于这样的事情:
我有光栅图像(左侧),我想要一个由点和边组成的图形(右侧),该图形表示图像。
我已经阅读了一些算法,特别是Steven Skiena的一本书,他告诉我们要使用“刷火算法”,他解释道:“每个周期,经过每个在边缘上的点,对于相互碰撞的边,添加一个到骨架上的点并删除剩余的点,继续进行下一次周期,直到只剩下骨架为止”,但我在网上找到的所有关于这个算法的信息都是关于一些机器人路径规划算法的,我不知道如何在这里应用它(如果我只有填充/空闲像素的坐标,我怎么知道“边”)。
我查看了CGAL库及其骨架演示,但当多边形具有许多顶点时,它的表现并不好,因此仅将边界上的每个顶点转换为多边形的顶点,然后将其输入算法不会产生良好的结果。
我希望这必须是一个常见的算法,因为该任务似乎非常基本,但我不想重新发明轮子,我在这个主题上找不到任何信息(也许是因为我不知道正确的关键词)。
![Pic 01](https://istack.dev59.com/hUBsf.webp)
我已经阅读了一些算法,特别是Steven Skiena的一本书,他告诉我们要使用“刷火算法”,他解释道:“每个周期,经过每个在边缘上的点,对于相互碰撞的边,添加一个到骨架上的点并删除剩余的点,继续进行下一次周期,直到只剩下骨架为止”,但我在网上找到的所有关于这个算法的信息都是关于一些机器人路径规划算法的,我不知道如何在这里应用它(如果我只有填充/空闲像素的坐标,我怎么知道“边”)。
我查看了CGAL库及其骨架演示,但当多边形具有许多顶点时,它的表现并不好,因此仅将边界上的每个顶点转换为多边形的顶点,然后将其输入算法不会产生良好的结果。
我希望这必须是一个常见的算法,因为该任务似乎非常基本,但我不想重新发明轮子,我在这个主题上找不到任何信息(也许是因为我不知道正确的关键词)。