寻找一种有效的算法来找到扫掠的二维形状的边界 [英] Looking for an efficient algorithm to find the boundary of a swept 2d shape
问题描述
我有一个分段曲线，定义了一个生成器（想想画笔），还有一个分段曲线，代表了画笔遵循的路径。我希望生成生成器曲线在扫过路径时创建的边界。
I have piecewise curve defining a generator (think brush) and a piecewise curve representing the path the brush follows. I wish to generate the boundary that the generator curve creates as it is swept across the path.
这是用于类似工程CAD的应用程序。我正在寻找任何语言的通用算法或代码示例。
This is for an engineering CAD like application. I am looking for a general algorithm or code samples in any language.
推荐答案
我们使用的实际答案过于复杂，无法发布
The actual answer we used is too complex to post in full but in summary.
- 沿转换路径以规则间隔对曲线采样
- 构建一个通过将每个样本的顶点连接到下一个和上一个样本的
三角形网格 - 通过其相邻三角形法线指向相反方向的候选轮廓边来识别
- 使用扫掠线算法在相交处分割所有边。这是棘手的部分，因为我们发现我们必须使用BigRational算法或微妙的数值错误来做到这一点，从而破坏了拓扑结构。
- 将拆分边转换为平面图
- 找到最靠近某个外部测试点的分割边
-
在图形外部走动。 （同样，所有测试都是使用大有理数完成的）。
- Sample the curve at regular intervals along the transformed path
- Build a triangular mesh by joining the vertices from each sample to the next and previous sample
- Identify candidate silhouette edge by whose neighboring triangles normals point in opposite directions
- Split all edges at intersections using a sweepline algorithm. This is the tricky part as we found we had to do this with a BigRational algorithm or subtle numerical errors crept in which broke the topology.
- Convert the split edges into a planar graph
- Find the closest of the split edges to some external test point
Walk around the outside of the graph. ( again all tests are done using big rational )
由于BigRational的计算，算法的性能并不出色。但是，我们尝试了很多方法在浮点中执行此操作，并且总是得到数值边缘情况，其中所得图形不是平面。如果图形不是平面的，那么您将无法在图形的外部走动。
The performance of the algorithm is not brilliant due to the BigRational calculations. However we tried many ways to do this in floating point and we always got numerical edges cases where the resulting graph was not planar. If the graph is not planar then you can't walk around the outside of it.
这篇关于寻找一种有效的算法来找到扫掠的二维形状的边界的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
