![enter image description here](https://istack.dev59.com/8sGCs.webp)
我正在研究,但同时,如果有人能给出一些指针或想法,那将是有帮助的。谢谢阅读。顺便说一句,我正在使用WPF/C#,所有的折线都是PathGeometry。
图片来源:http://www.sitepen.com/blog/wp-content/uploads/2007/07/gfx-curve-1.png
在Geom的建议基础上(使用R-Tree是正确的方法),可以通过以下方式进一步提高性能:
1. 简化折线 - 可以通过角度阈值处理每个点或使用 Ramer-Douglas-Peucker算法来减少折线中的点数,同时保持折线的总体形状。根据您的需求,您可能需要跟踪原始折线中哪些点用作简化折线的每个线段的起点/终点(原始折线的点的索引需要存储在某个地方)。
在此示例中,您可以看到如何减少折线的点数。红色点表示未使用的原始折线中的点,绿色点表示保留下来用于构建简化折线的点。
2. 将简化的折线存储在R-Tree中,并确定每条折线的每个线段之间的交点(比较线段的边界以减少计算对性能有利)。在执行此操作时,原始折线线段的旧索引将作为与每个检测到的交点相关的信息存储,以及相交的折线(可以使用某种标识符)。这基本上为您提供了每个原始折线中存在与其他折线相交的交点的每个线段的起始和结束边界。
3. 仅当交点位置必须与原始折线的交点位置匹配时才执行此步骤。您需要返回并使用原始的非简化折线,以及从第2步获取的交点信息。每个交点应该与其关联的起始和结束索引,这些索引可用于确定需要处理哪些原始折线的具体线段。这将允许您仅处理必要的线段(由存储在交点信息中的起始和结束索引给出)。另一种方法是使用点本身并向外扩展边界框,然后处理与该边界框相交的原始折线的线段(尽管这可能需要更长时间)。
4. 可能需要采取额外的步骤来检查每个折线的端点与其他折线段的交点,因为简化过程可能会去除一些端点交叉点。(这通常非常快)。
使用Bentley-Ottmann算法(这是Geom提到的扫描线算法)可以进一步改进此算法。还要注意,根据所使用的简化算法和用于此类算法的参数(例如角度容差),性能和准确性之间可能存在权衡(某些交点结果可能会丢失,具体取决于折线的简单程度)。
显然,有一些库可能是可行的,但如果由于您所在公司或正在开发的产品的许可条款而受到限制,则第三方库可能不是选项。此外,其他库可能无法满足所需的性能要求。