Find the intersection points of all circles

Admin 1
Viewed 633

Given a set of 2D coordinates and radius for each coordinate how to efficiently find all the points where at least 2 circles of the set of circles intersect?

I understand two circles intersect at a maximum of 2 points so it can be done by pairwise comparisons between two circles and looping over the entire data set but when the real data set has 10000 circles, doing all the pairwise comparisons will be computationally expensive.

Below is the sample code for generating Test Data. 

    library("plotrix")
    set.seed(1995)
    XCoordinate = sample(x = 1:100,size = 20)
    set.seed(2000)
    YCoordinate = sample(x = 1:100,size = 20)
    set.seed(1997)
    Radius = sample(x = 1:50,size = 20)
    ## Create DataFrame
    TestData = data.frame(XCoordinate = XCoordinate,YCoordinate = YCoordinate, 
    Radius = Radius )

    ## Plot Circle
    plot(TestData$XCoordinate, TestData$YCoordinate, 
         type="n", xlab="", ylab="" , main="Test draw.circle")

    for(Row in 1:nrow(TestData)){
      PlotCircle(TestData$XCoordinate[Row], 
                 TestData$YCoordinate[Row], 
                 TestData$Radius[Row])
    }

I am trying find all the points that are marked in black in the attached.

Small example

r algorithm
3 Answers

You may get quite a few false positive candidates but unless the circles are pretty much laid out on top of each other, we could significantly reduce the number of pair checks by calculating the bounding boxes for the circles and running a line sweep. Intersecting circles imply bounding box intersection, although not vice versa.

user_20347870

Probably more complicated to implement but maybe more selective than the solution of גלעד ברקן:

  1. Build an R-Tree, organizing the circle centers and add an additional attribute maxRadius to each node that holds the maximum radius of any circle who's center is contained in that node

  2. For each circle c, find candidate circles performing range search on the R-Tree. Discard nodes p when minDist(c, p) > c.radius + p.maxRadius

  3. Compute intersections for each candidate

Building the R-Tree in 2D is generally O(n log n), range search is considered O(log n) for moderate ranges (radii). Which makes a total of O(n log n) in the average case.

user_85926470

I've implemented the sweep-line algorithm for circle intersection in C++ here: github.com/malyasova/intersect_circles

It works like the segment intersection algorithm only the upper and lower arc of each circle are inserted into status instead of segments. It works in O((n+k)log n) time, where n is the number of circles and k is the number of intersections.

user_83429100
Related