两组线段的Bentley-奥特曼算法
采用Bentley-奥特曼算法计算线段的相交.
但是，我不想在它们之间找到所有直线的相交点，而是在两组直线之间找到相交点。这就是说，对于直线组A中的每一行，我想知道这些线与组B中的直线之间的交点。
无论如何，我可以为此扩展宾利-奥特曼算法吗？我已经实现了现有的本特利-奥特曼算法( 在CGAL图书馆)，我不想修改它。然而，我渴望找到重用和扩展它的方法。
编辑:任何其他算法(不一定基于宾利-奥特曼)都是受欢迎的。如果这些算法已经在现有的库中实现了，则会更好。
回答 4
Stack Overflow用户
发布于 2010-12-30 01:31:29
您可以在A+B中找到所有行之间的所有交叉点，然后删除同一集合中的行之间的交叉点。您并没有增加太大的复杂性，这允许您使用CGAL的库函数而只使用一个简单的包装函数。
Stack Overflow用户
发布于 2011-02-02 22:20:50
本特利-奥特曼保留了一棵由直线段组成的树，这些线段按它们当前的垂直位置排列，难道你不能保留两棵树，A组和B组各一棵吗？然后，在原始算法检查当前点之上和下面的邻居的地方，您将检查上面的A-邻域和下面的B-邻居，反之亦然。
这是基于对维基百科文章的快速浏览，在过去的十年里，我没有写过太多的几何代码。
Stack Overflow用户
发布于 2015-08-02 03:38:04
添加这个答案是为了完整，尽管它可能不是二维最有效的方法。
在3D图形中，它的共同点是2 KD-树，可用于检测所有重叠的节点(可用于几何上的布尔运算)。
工作示例(C代码)。kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b1089美元
如果有许多小段(例如手绘线的路径)，这将是合理有效的。然而，如果有许多长的边缘(比如小木棍).这将执行不好的操作，您可能希望在BVH树中分割叶节点以获得更好的性能。然而，如果是这样的话，最好采用其他答案中所建议的不同方法。
https://stackoverflow.com/questions/4553739
复制相似问题
腾讯云开发者
