我有分段曲线定义生成器(想象一下画笔)和分段曲线表示画笔遵循的路径。我希望生成生成器曲线在扫过路径时创建的边界。
这是一个类似工程CAD的应用程序。我正在寻找一个通用的算法或代码样本在任何语言。
我建议以下论文:
- "二维弯曲物体的近似一般扫描边界"，作者:Ahn Jae-Woo, Kim Myung-Soo和Soon-Bum Lim
- "Real Time Fitting of Pressure brushes " by Thierry Pudet "图形规范的刷-轨迹方法:一些代数解"
我们使用的实际答案太复杂了，不能全文发布，只能做个总结。
- 沿着变换后的路径每隔一段时间采样曲线
- 通过连接每个样本的顶点来构建三角形网格下一个和上一个示例
- 确定候选轮廓边缘，其相邻三角形法线指向相反方向
- 使用宽线算法分割十字路口的所有边缘。这是一个棘手的部分，因为我们发现我们必须使用BigRational算法或微妙的数值错误来实现这一点，这会破坏拓扑结构。
- 将分割边转换为平面图
- 找到离某个外部测试点最近的分割边
-
绕图的外侧走一圈。(同样，所有的测试都使用大的rational)
由于BigRational的计算，该算法的性能并不出色。然而，我们尝试了很多方法在浮点中做到这一点，我们总是得到数值边，结果图不是平面的。如果图形不是平面的，那么你就不能绕着它的外面走。
如果你有一个任意复杂的形状沿着任意路径平移和旋转，使用精确的方法计算出扫描的面积(及其边界)将是一个非常棘手的问题。
你可以考虑使用基于呈现的方法:
- 以黑色画布开始
- 对移动形状的路径进行密集采样
- 对于每个样本位置和旋转，将形状渲染为白色
- ，你现在有一个相当好的估计扫过的形状的画布
您可以按照以下步骤执行:
- (可选)做一些图像处理，试图修复由于过于稀疏地采样形状路径而引入的任何伪影
- (可选)将画布通过边缘查找过滤器以获得扫描形状的边界