查找一组直线段中的所有交点？
查找一组直线段中的所有交点？
提问于 2020-04-09 20:21:57
我有一个对象数组(行)和一个返回true/false的二元运算(交集)。蛮力是复制数组并在嵌套的for循环上运行。
for (Line line : linesArray) {
for (int j = 0; j < linesArray.length; j++) {
if (line.isIntersecting(linesArray[j])) {
Point intersection = line.intersectionWith(linesArray[j]);
d.drawCircle(intersection.getXInt(), intersection.getYInt(), 3);
d.fillCircle(intersection.getXInt(), intersection.getYInt(), 3);
}
}
}但是，顺序并不重要，所以我考虑生成一个大小为2的子集，并对每个子集进行检查，但从复杂的角度来看，这似乎也不会更好
是否有一个有效的(运行时)来做到这一点？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-04-09 20:54:08
您是正确的，枚举大小为2的所有子集并检查每个子集都不会比现有算法有所改进。事实上，这本质上只是重述你的算法所做的事情。
有更快的算法可以解决在线段集合中查找所有交点的问题。其中最著名的是Bentley-Ottmann algorithm，它的工作原理是根据线段的x坐标对线段进行排序，并从左到右在点上扫过一条线。它的工作时间是O((n + k)log )，其中n是线段的数量，k是交叉点的数量。
其他更现代的算法可以更快地解决这个问题，但这可能是一个很好的起点。
希望这能有所帮助！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61129606
复制相关文章
相似问题
腾讯云开发者
