Computing circle intersections in O ((n + s) log n)

Question

I am trying to figure out how to develop an algorithm that can accomplish this task using the complex O ((n + s) log n) task. s is the number of intersections. I tried searching the Internet but could not find something.

In any case, I understand that a good data structure is important here. I am using a Red Black Tree implementation in java: TreeMap. I also use the famous (?) Sweep Algorithm to help me deal with my problem.

Let me explain my setup first.

I have a scheduler. This is a PriorityQueue with ordered circles (ascending) based on their leftmost coordinate. scheduler.next() basically poll PriorityQueue, returning the next leftmost circle.

 public Circle next() { return this.pq.poll(); } 

I also have an array with 4n events here. Giving each circle has 2 event points: most left x and rightmost x. The scheduler has a sweepline () method to get the next event point.

 public Double sweepline() { return this.schedule[pointer++]; } 

I also have a status. More accurate scan line status. According to theory, the status contains circles that can be matched to each other. The point of having a scan line in this whole story is that you can exclude many candidates because they simply are not in the radius of the current circles.

I executed the status using TreeMap<Double, Circle> . The double is circle.getMostLeftCoord().

This TreeMap guarantees O (log n) for insert / delete / search.

The algorithm itself is implemented as follows:

 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 intersecting.

SweepLineStatus Code

 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 obviously had O (n ^ 2) complexity. What am I missing here? Any input that you guys can provide is more than welcome.

Thanks in advance!

Answer 1

You cannot find all intersection points of circles n in the plane in O(n log n) , because each pair of circles can have up to two different intersection points, and therefore circles n can have up to n² - n intersection points and therefore they do not can be listed in O(n log n) time.

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

Answer 2

N circles with the same center and radius will have N (N-1) / 2 pairs of intersecting circles, and when using large enough circles so that their borders are almost straight, you can draw a grid with N / 2 lines intersecting each of N / 2 lines, which is again N ^ 2. I would see how many records are usually present on your map when adding a new circle.

You can try to use the bounding squares for your circles and keep the index on the pending squares so that you can only find the squares that have y coordinates that intersect your query square (assuming the scan line is parallel to the y axis). This would mean that if your data was friendly, you could keep a lot of pending squares and only check a few of them for possible intersections of circles inside the squares. Adverse data to create real N ^ 2 intersections will always be a problem.

Answer 3

How big are the circles compared to the whole area? If the ratio was small enough, I would think about putting them in some kind of bucket. This will make complexity a bit more complicated than O(n log n) , but should be faster.