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

问题:

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!

回答1:

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.

回答2:

N circles with the same centre and radius will have N(N-1)/2 pairs of intersecting circles, while by using large enough circles so that their boundaries are almost straight lines you can draw a grid with N/2 lines intersecting each of N/2 lines, which is again N^2. I would look and see how many entries are typically present in your map when you add a new circle.

You might try using bounding squares for your circles and keeping an index on the pending squares so that you can find only squares which have y co-ordinates that intersect your query square (assuming that the sweep line is parallel to the y axis). This would mean that - if your data was friendly, you could hold a lot of pending squares and only check a few of them for possible intersections of the circles within the squares. Data unfriendly enough to cause real N^2 intersections is always going to be a problem.

回答3:

How large are the circles compared to the entire area? If the ratio is small enough I would consider putting them into buckets of some sort. It'll make the complexity a little more complicated than O(n log n) but should be faster.