c++ - COUNTING 对相交和弦的数量

Question

考虑N一个圆圈中的和弦，每个和弦都由它的端点决定。描述一种O(nlogn)确定在圆内相交的弦对数的解决方案。

假设：没有两个和弦共享一个端点。

Answer 1

存在一个通用的线段相交算法，它在 O(nlogn) 中完成这项工作。
这可以在您的情况下使用，因为两个弦不能在圆的外部相交。
以下链接包含算法：
http ://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf

PS
它需要基本的计算几何知识（线扫描、范围树）。

希望这可以帮助。

Answer 2

在我的头顶上，按极角对和弦端点进行排序（这是 O(n log n) 部分）。然后通读排序列表（即 O(n)）——如果两个相邻的端点属于同一个弦，则它没有交点。如果列表中的两个相邻条目属于不同的和弦，则可能存在交集，具体取决于这两个和弦的其他端点所在的位置 - 例如，如果和弦 A 在其排序顺序中具有端点 A1 和 A2，并且类似地，和弦 B 具有 B1和B2，在列表中找到B2-A1不是交集，因为B1在前，A2在后。但是，B1-A2 将是一个交叉点。

另请参阅 biziclop 的评论以获取另一种更精心构建的解决方案。