我试图弄清楚如何设计一种算法，可以以 O((n+s) log n) 复杂度完成此任务。 s 是交叉点的数量。我尝试在互联网上搜索，但找不到真正的东西。
无论如何，我意识到拥有良好的数据结构是关键。我在java中使用红黑树实现：TreeMap。我还使用著名的（？）扫描线算法来帮助我处理我的问题。
让我先解释一下我的设置。
我有一个调度程序。这是一个 PriorityQueue，我的圈子根据最左边的坐标排序（升序）。scheduler.next()基本上轮询 PriorityQueue，返回下一个最左边的圆圈。
public Circle next()
{ return this.pq.poll(); }
我这里还有一个包含 4n 个事件点的数组。假设每个圆有 2 个事件点：最左边的 x 和最右边的 x。调度程序有一个方法sweepline()来获取下一个事件点。
public Double sweepline()
{ return this.schedule[pointer++]; }
我也有一个状态。更精确的扫线状态。根据该理论，状态包含有资格进行相互比较的圈子。在整个故事中使用扫描线的目的是，您可以排除许多候选者，因为它们根本不在当前圆圈的半径内。
我用一个实现了 StatusTreeMap<Double, Circle>。双为circle.getMostLeftCoord().
此 TreeMap 保证插入/删除/查找的 O(log n)。
算法本身的实现如下：
Double sweepLine = scheduler.sweepline();
Circle c = null;
while (notDone){
while((!scheduler.isEmpty()) && (c = scheduler.next()).getMostLeftCoord() >= sweepLine)
status.add(c);
/*
* Delete the oldest circles that the sweepline has left behind
*/
while(status.oldestCircle().getMostRightCoord() < sweepLine)
status.deleteOldest();
Circle otherCircle;
for(Map.Entry<Double, Circle> entry: status.keys()){
otherCircle = entry.getValue();
if(!c.equals(otherCircle)){
Intersection[] is = Solver.findIntersection(c, otherCircle);
if(is != null)
for(Intersection intersection: is)
intersections.add(intersection);
}
}
sweepLine = scheduler.sweepline();
}
EDIT: Solver.findIntersection(c, otherCircle);返回最多 2 个交点。重叠的圆不被视为有任何交点。
SweepLineStatus 的代码
public class BetterSweepLineStatus {
TreeMap<Double, Circle> status = new TreeMap<Double, Circle>();
public void add(Circle c)
{ this.status.put(c.getMostLeftCoord(), c); }
public void deleteOldest()
{ this.status.remove(status.firstKey()); }
public TreeMap<Double, Circle> circles()
{ return this.status; }
public Set<Entry<Double, Circle>> keys()
{ return this.status.entrySet(); }
public Circle oldestCircle()
{ return this.status.get(this.status.firstKey()); }
我测试了我的程序，显然有 O(n^2) 复杂度。
我在这里缺少什么？我们非常欢迎你们提供任何意见。
提前致谢！
