是否有一种有效的方法来计算给定的一组线段之间的交点数量？

本文介绍了是否有一种有效的方法来计算给定的一组线段之间的交点数量？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 假设我有n个一般位置的线段。我如何快速计算n个分段中每个分段有多少个n-1相交？

我可以在O（n ^{2 ）时间。我可以在O（（n + k）log n）时间内使用相当直接的扫描线算法（Bentley-Ottmann）找到所有交点，其中k是这样的交点的数量，然后将我发现的交点聚集成一堆计数。}

不过，我不需要找到交叉点，我只想知道有多少。我不明白如何修改扫描线算法以使其更快，因为它需要为每个交集重新排列树中的两个东西，而且我也想不到其他任何不会遇到同样问题的其他技术。 / p>

我也有兴趣知道如何计算有多少个交叉点。

解决方案

我很难相信在一般情况下你可以比Bentley Ottman做得更好。如果你不关心线段在哪里相交，你可以简化一些计算，但是我没有看到你如何在没有找到它们的情况下计算交叉点。

在本质上，Bentley Ottman是一种简化交叉路口搜索空间的方法。还有其他一些方法可能适用于线段的特定布置，但除非您的线段之间存在某种可预测的几何关系，否则您将无法比第一种方法更好地使用某种巧妙的方法找到候选交点并将其与除非你的问题域有一些可能会提供可开发子结构的特定功能，否则我认为你最好的速度选择是适应宾利Ottman（或一些类似的扫描算法）用于并行执行。 （将线段剪成乐队是很简单的，找出一组最佳乐队也会很有趣。）当然，这是一个实用的而不是学术的练习;并行算法可能最终会完成更多的工作;它只是利用硬件在（一个固定的因素）时间内完成工作。

Suppose I have n line segments in general position. How can I quickly count, for each of my n segments, how many of the other n-1 it intersects?

I can do this naively in O(n2) time. I can find all intersections using a fairly straightforward sweep line algorithm (Bentley-Ottmann) in O((n + k) log n) time, where k is the number of such intersections, and then aggregate the intersections I found into a bunch of counts.

I don't need to find the intersections, though; I just want to know how many there are. I don't see how to modify the sweep line algorithm to be faster since it needs to reorder two things in a tree for every intersection, and I can't think of any other techniques that don't suffer from the same problem.

I'm also interested in hearing how to count how many total intersections there are.

解决方案

I have a hard time believing that you can do better than Bentley Ottman in the general case. You can simplify the computation a bit if you don't care where the line segments intersect, but I don't see how you could count crossings without finding them.

In essence, Bentley Ottman is a way to simplify the search space for intersections. There are other ways, which might work for particular arrangements of line segments, but unless there is some predictable geometric relationship between your segments, you're not going to be able to better than first using some clever way of finding candidate intersections combined with an individual verification of each candidate.

Unless your problem domain has some specific features which might make provide exploitable substructure, I'd think your best bet for speed would be to adapt Bentley Ottman (or some similar sweeping algorithm) for parallel execution. (Clipping the line segments into bands is a simple one. Figuring out an optimal set of bands would be interesting, too.) Of course, that's a practical rather than an academic exercise; the parallel algorithm might well end up doing more work in total; it just exploits hardware to do the work in (a constant factor) less time.