计算O（（n + s）log n中的圆交点） [英] Computing circle intersections in O( (n+s) log n)

问题描述

我试图找出如何设计一个算法，可以用O（（n + s）log n）复杂度来完成这个任务。是交叉点的数量。我试过在互联网上搜索，但无法找到真正的东西。

无论如何，我认识到有一个好的数据结构是关键。我在java：TreeMap中使用红黑树实现。我还使用着名的（？）扫描线算法来帮助我处理我的问题。

让我首先解释我的设置。

我有一个调度程序。这是一个PriorityQueue，根据他们最左侧的坐标，我的圈子被排序（升序）。 scheduler.next（）基本上轮询PriorityQueue，返回下一个最左边的圆。

  public Circle next（）
 {return this.pq.poll（）; } 
  

我在这里也有一个4n事件点的数组。授予每个圈子有2个事件点：最左边x和最右边x。调度程序有一个方法sweepline（）来获取下一个事件点。

  public double sweepline（）
 {return this.schedule [指针++]; } 
  

我也有一个Status。扫线状态更精确。根据理论，该状态包含可以相互比较的圈子。在整个故事中拥有扫描线的一点是，你可以排除很多候选人，因为他们根本不在当前圈子的半径范围内。

我使用 TreeMap< Double，Circle> 实现了状态。 Double是 circle.getMostLeftCoord（）。

这个TreeMap保证O（log n）找到。

算法本身是这样实现的：

  Double sweepLine = scheduler.sweepline（）; 
 Circle c = null; （（！））（$ scheduler.next（））和（（））。getMostLeftCoord（）> = sweepLine）
 while（notDone）{
 。新增（C）; 
 
 $ b / * 
 *删除扫描线留下的最旧的圆圈
 * / 
 while（status.oldestCircle（）。getMostRightCoord（） < sweepLine）
 status.deleteOldest（）; 
 
圈出其他圆; （Map.Entry< Double，Circle>条目：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（）; 
 
 
 
 $ b 
编辑： 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）; } 
 $ b $ 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（）; } 
 $ b $ public CircleCircle（）
 {return this.status.get（this.status.firstKey（））; } 
  
我测试了我的程序，我清楚地知道O（n ^ 2）的复杂性。 
我在这里错过了什么？任何输入您可能能够提供的是超过欢迎。
 
 
 
预先感谢！
解决方案 
您无法在 O（n log n）平面中找到 n  c $ c>时间，因为每对圆圈最多可以有两个不同的交点，因此 n 圆可以达到n² -  n 不同的交叉点，因此它们不能在 O（n log n）时间中枚举。
 
 
 
获取n² -  n 交叉点的最大数量的一种方法是将 n 的圆心放置在一条长度线的相互不同的点处，相等半径 r   l< 2r 。
 
 
 
  
 
I'm trying to figure out how to design an algorithm that can complete this task with a O((n+s) log n) complexity. s being the amount of intersections. I've tried searching on the internet, yet couldn't really find something.

Anyway, I realise having a good data structure is key here. I am using a Red Black Tree implementation in java: TreeMap. I also use the famous(?) sweep-line algorithm to help me deal with my problem. 

Let me explain my setup first. 

I have a Scheduler. This is a PriorityQueue with my circles ordered(ascending) based on their most left coordinate. scheduler.next() basically polls the PriorityQueue, returning the next most left circle. 
public Circle next()
{ return this.pq.poll();    }
I also have an array with 4n event points in here. Granting every circle has 2 event points: most left x and most right x. The scheduler has a method sweepline() to get the next event point.
public Double sweepline()
{ return this.schedule[pointer++];    }
I also have a Status. The sweep-line status to be more precise. According to the theory, the status contains the circles that are eligible to be compared to each other. The point of having the sweep line in this whole story is that you're able to rule out a lot of candidates because they simply are not within the radius of current circles. 

I implemented the Status with a TreeMap<Double, Circle>. Double being the circle.getMostLeftCoord().

This TreeMap guarantees O(log n) for inserting/removing/finding.

The algorithm itself is implemented like so:
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); returns max 2 intersection points. Overlapping circles are not considered to have any intersections.

The code of the 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());   }
I tested my program, and I clearly had O(n^2) complexity. 
What am I missing here? Any input you guys might be able to provide is more than welcome.

Thanks in advance!
解决方案
You can not find all intersection points of n circles in the plane in O(n log n) time because every pair of circles can have up to two distinct intersection points and therefore n circles can have up to n² - n distinct intersection points and hence they can not be enumerated in O(n log n) time.

One way to obtain the maximum number of n² - n intersection points is to place the centers of n circles of equal radius r at mutually different points of a line of length l < 2r.



                        
这篇关于计算O（（n + s）log n中的圆交点）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！