How to find all contact points of all the circles in a image by using opencv

Question

Here is the image,I want to find all contact points in this image,I know the center and radius of each circle.In my mind, the euclidean distance maybe is not a efficient method to calculate the center-to-center distance.So,My question is how to find all the contact point of this image in a efficient way.Thanks.

you can reduce the number of comparisons by using either binary space partitioning techniques or spatial hashing — Micka, Nov 04 '15 at 13:17
btw, circle collision test is maybe the easiest collision test and afaik euclidean distance is used there. Drawing a circle is probably more expensive than some good amount of collision tests. — Micka, Nov 04 '15 at 15:21
maybe there are some more hints in http://stackoverflow.com/questions/2544431/collision-detection-of-huge-number-of-circles like using delauny triangulation. — Micka, Nov 04 '15 at 15:23

Micka · Accepted Answer · 2015-11-04T15:00:34.510

Circles' contact points will be placed on the line from center1 to center2. So for example if both circles have the samze size you would choose intersection = center1 + 1/2*(center2-center1) But since your circles aren't of same size you could choose something like:

compute dirVector = center2-center1
compute d = |dirVector|
if d < radius1 + radius2 + threshold: consider circles to intersect so now compute contact point
    gap = d - radius1 - radius2 // remark: here gap might become < 0 which is ok
    contactPoint = center1 + (radius1+gap/2)*(dirVector/d)

I've tested this approach with primitive C++ code and I'm getting this result:

green circles are your original image, red circles are my extracted circles (not perfect but simple), pink dots are contact points for some contact-distance-threshold (20 pixel)

and this is the result for a much lower contact-distance-threshold (5) (but keep in mind that my extracted circle radius is a bit lower than yours):

To make this more efficient (because you would have to compare each pair of circles, no matter how far away they are => O(n²) ) you should use some kind of binary space partitioning like:

KD-Tree

Quad-Tree

or similar

or try Spatial Hashing, but those are better suited for sparse areas.

In general you might want to search for collision detection optimizations to speed things up (there you'll find more information about binary space partitioning and spatial hashing).

Since your space is very filled you might consider a simple grid, too (which is similar to spatial hashing in this case):

//choose size of each grid cell to be the maximum found radius of all your circles.
gridCellSize = max diameter + contact-threshold-distance // radius was wrong I think
for each circle
    indexX = round(center.x/gridCellSize)
    indexY = round(center.y/gridCellSize)
    grid[x,y].push_back(current circle)

for each circle in a grid-cell:
    compare this circle to each other circle in the cell
    compare this circle to each circle in all surrounding cells
    ignore all circles in all other cells

for my previous example I've extracted a maxium radius of 44 pixel (yours might be something like 47 pixel, depending on the line size you used for drawing the circles.

So a grid like this is computed:

For example in grid-cell position (1,1) if grid is 0-indexed, there are 2 circles located. Each of them should be compared to all circles in the same cell and each circle in surrounding cells. So those 2 circles will be compared to only 12 circles instead of against n-1 circles.

Or graphically marked examples: All circles in a red cell have to be compared against each circle in the surrounding blue cells in addition to the other circles in the red cell (none in this example):

This is really helpful for my question,thank you for your time. — Elivis, Nov 05 '15 at 03:19

score 1 · Answer 2 · answered Nov 04 '15 at 04:45

There are several ways to attempt this problem:

As you have told you have radius and center of the circles, that means you have boundaries (Circumference coordinates) of the circle. that means you can know which coordinates belongs to which circle, so you can find out intersection using this information.
you can segment the image get blobs and further distinguish them on the basis of circularity, the blobs which are circular, remove them. now you will have all those blobs which are not follow circularity(because circles have joined together) so you can again apply step 1 which will now have very less point to check the intersection.
Watershed algorithm its little complex than above methods but you can give it a try, for this you can create an image where you can plot all these circles using their center and radius(this image will be the binary image) fill all the circles and apply watershed algorithm using centers as seed of the watershed, it will give you the coordinates where the two objects are joining.

In my point of view you can approach the problem using method 1 or 2.

Thank You

The first method is good,but there is a question,if the two circles are close enough,but they don't have the contact point, i also look them as two contacted circles, it seems that the first method is useless in this situation — Elivis, Nov 04 '15 at 07:23
as you have told that you have idividual centroids and radius then method number 1 will not have any problem....mthod 2 is just for reducing overhead on non touching circles....in both the case i assume you know the center and radius for each circle. — Ankit Dixit, Nov 04 '15 at 17:15

How to find all contact points of all the circles in a image by using opencv

2 Answers2