计算O（（n + s）log n）中的圆交点
我试图弄清楚如何设计一个能够用O（（n + s）log n）复杂度完成这项任务的算法。 是交叉点的数量。 我试过在网上搜索，却找不到东西。
无论如何，我意识到拥有一个好的数据结构是关键。 我在java：TreeMap中使用Red Black Tree实现。 我还使用着名的（？）扫描线算法来帮助我处理我的问题。
让我先解释一下我的设置。
我有一个调度程序。 这是一个PriorityQueue，我的圈子根据最左边的坐标排序（升序）。 scheduler.next()基本上轮询PriorityQueue，返回下一个最左边的圆圈。
public Circle next() { return this.pq.poll(); }
我这里也有一个包含4n个事件点的数组。 授予每个圆圈有2个事件点：大多数左x和最右x。 调度程序有一个方法sweepline（）来获取下一个事件点。
public Double sweepline() { return this.schedule[pointer++]; }
我也有状态。 扫描线状态更加精确。 根据该理论，状态包含有资格相互比较的圆圈。 在整个故事中拥有扫描线的关键在于你能够排除很多候选人，因为他们根本不在当前圈子的半径范围内。
我使用TreeMap实现了Status。 Double是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 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(); }
编辑： Solver.findIntersection(c, otherCircle); 返回最多2个交叉点。 重叠的圆圈不被认为有任何交叉点。
SweepLineStatus的代码
public class BetterSweepLineStatus { TreeMap status = new TreeMap(); public void add(Circle c) { this.status.put(c.getMostLeftCoord(), c); } public void deleteOldest() { this.status.remove(status.firstKey()); } public TreeMap circles() { return this.status; } public Set<Entry> keys() { return this.status.entrySet(); } public Circle oldestCircle() { return this.status.get(this.status.firstKey()); }
我测试了我的程序，我显然有O（n ^ 2）的复杂性。 我在这里想念的是什么？ 您可能提供的任何输入都非常受欢迎。
提前致谢！
在O(n log n)时间内，您无法在平面中找到n圆的所有交点，因为每对圆最多可以有两个不同的交点，因此n圆可以有多达n² - n不同的交点，因此它们不能在O(n log n)时间内枚举。
获得最大数量的n² - n交点的一种方法是将n个相等半径r圆心设置在长度l < 2r的线的相互不同的点上。
具有相同中心和半径的N个圆将具有N（N-1）/ 2对相交的圆，而通过使用足够大的圆使得它们的边界几乎是直线，您可以绘制具有与每个相交的N / 2条线的网格。 N / 2行，也是N ^ 2。 我会看一下，当你添加一个新的圆圈时，你的地图中通常会有多少条目。
您可以尝试为圆圈使用边界正方形并在待处理的正方形上保留索引，以便只能找到与坐标相交的y坐标的正方形（假设扫描线与y轴平行）。 这意味着 – 如果您的数据是友好的，您可以保留许多待处理的正方形，并且只检查其中的一些正方形中圆圈的可能交叉点。 足够不友好的数据导致真正的N ^ 2交叉点总是一个问题。
圆圈与整个区域相比有多大？ 如果比例足够小，我会考虑将它们放入某种水桶中。 它会使复杂性比O(n log n)复杂一点，但应该更快。