数对相交和弦数

Question

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

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

Answer 1

在O(nlogn)中存在一种通用的线段求交算法.

这可以用在你的情况下，因为两个和弦不能相交在一个圆的外部。

以下链接包含算法：

http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf

附注：

它需要基本的计算几何知识(行扫描，范围树)。

希望这能有所帮助。

Answer 2

在我的头顶上，按极角对弦端点进行排序(这是O(n log n)部分)。然后读取排序列表(即O(n)) --如果两个相邻的端点属于同一个chord，则它没有交叉点。如果列表中的两个相邻条目属于不同的和弦，则可能会有一个交集，这取决于这两个和弦的其他端点所在的位置--例如，如果和弦A的端点A1和A2按排序顺序排列，而和弦B有B1和B2，则在列表中查找B2-A1不是交集，因为B1更早，A2更晚。然而，B1-A2将是一个交集。

另见biziclop对另一种更仔细构造的解决方案的评论。