I would like to be able to represent circles in x-y coordinates.

Each circle contains an x and y coordinates and radius in double data type.

My goal is to compare circles with each other whether they are partially or completely overlapping.

I am looking for efficient ideas. Honestly the only idea that comes to my mind is draw a line(let's say l1) from x1,y1 to x2,y2 and the length of this line is larger than addition of r1 and r2 then it does not overlap, if r1+r2 =< l1 then it overlaps, but I don't know how to find whether it is completely overlapping or partially. Also this wouldn't work for cases where I am combining more than one circle.

  • 1
    $\begingroup$ That's the most sensible solution. Circle 1 is contained in circle 2, iff r2 > l+r1. What do you mean by "combining"? $\endgroup$ – Karolis Juodelė Jan 6 '14 at 3:55
  • $\begingroup$ Thanks for figuring that out. I completely couldn't see that. When I say combining, assume that I have L which is an array of circles(cx). I have another circle that is not in L let's say c1, so I want to be able to figure out whether c1 is contained all cx'es combined together. $\endgroup$ – Sarp Kaya Jan 6 '14 at 4:09
  • 1
    $\begingroup$ That's a much bigger problem. $\endgroup$ – Karolis Juodelė Jan 6 '14 at 4:38
  • 1
    $\begingroup$ What do you mean by "completely" overlapping. Given circles $c_1$ and $c_2$, do they overlap "completely" only if $c_1 = c_2$ ($\equiv (c_1\subset c_2\wedge c_2\subset c_1)$) or also if $c_1\subset c_2\vee c_2\subset c_1$? $\endgroup$ – Jan Hudec Jul 29 '14 at 13:33
  • 1
    $\begingroup$ Your additional precisions given to @KarolisJuodelė should be properly included in your question (by editing it). As it stands, your question is unprecise. (comments are not considered stable information). $\endgroup$ – babou Jul 29 '14 at 15:31

This answer considers two cases:

  • the overlapping relation between two disks, which is a very simple problem.

  • the ovelapping or covering of a disk by a set of other disks, which is somewhat harder in general.

Case of two disks

It is indeed a good idea to use center and radius to represent your circles. However I think you are not thinking of circles, which are closed planar lines formed of all points at a given distance $r$, called radius, of a point $c$ called the center. The planar surface enclosed by a circle, which also includes all points at a lesser distance fron $c$ is called a disk (also spelled disc).

Regarding the various overlap situations for two disks, you have the following test, assuming the two circles have radius $r_1$ and $r_2$ (assuming witout loss of generality that $r_1\geq r_2$), with their centers at distance $d$ (computable from the centers coordinates, thanks to Pythagoras):

  • $r_1+r_2<d$ : disks are disjoint, no overlap.

  • $r_1+r_2=d$ : disks are tangent externally, a single point of overlap.

  • $r1-r2<d<r_1+r_2$ : disks are partially overlapping.

  • $r_1-r_2=d$ : disks are tangent internally, total overlap of disk 2 by disk 1.

  • $d<r_1-r_2$ : disk 1 overlap totally disk 2.

There can be exact overlap of each disk by the other only when $r_1=r_2 \wedge d=0$

Regarding the case of several disk, it is not clear whether you want to see whether one distinguished disk is overlapped totally, partially or not at all by the others, or whether you want to check that for each disk with everyone of the others, or possibly something else. You should make that more precise.

Case of several disks

This is only a rough sketch, hopefully correct. Working out all details is a lot more work than can be included in an answer.

As suggested in the question, we can represent a disk $D$ by a triple $(x,y,r)$ which gives the coordinates of the center, and the radius.

Now if you have a disk $D_0=(x_0,y_0,r_0)$ and a set of disks $L=\{D_i\mid D_i=(x_i,y_i,r_i),\; i\in[1,n]\}$, your question, as made more precise in a comment, is how to check whether the disks of set $L$ together overlap partially, totally or not at all the disk $D_0$.

First you want to make a list of the disks in $L$ that actually overlap $D_0$. For that you can simply apply the above test to $D_0$ and $D_i$ for every $D_i$ in $L$. You get a set $I\subseteq[1,n]$ of indices such that D overlaps every $D_i$ for $i\in I$.

If this set $I$ is not empty, you know that $D_0$ is overlapped by $L$.

The question remains of a total overlap of $D_0$ by $L$.

For this, you create a new set $J\subseteq I$ by removing indices of disks $D_i$ that are only externally tangent to $D_0$, overlapping it on only one point.

If $J$ is empty, you had only tangential overlapping in a finite number of point, but the set $L$ does not cover (fully overlap) the disk $D_0$.

If $J$ is not empty, then $L$ completely overlap $D_0$ iff it does it with the disks $D_i$ such that $i\in J$. Tangential overlapping on a single point cannot contribute usefully to overlapping a surface.

Now, all disks in $M=\{D_i\mid i\in J\}$ overlap $D_0$ on a fragment of its surface.

If one disk in $M$ completely overlaps $D_0$, then we have an answer of complete overlap. We can now assume it is not the case.

Then the problem is to find an orderly strategy to check whether the disks in $M$ completely cover $D_0$. We will now use disks from $M$ one by one, removing them from M, to cover $D_0$. The strategy is in choosing them.

We chose first a disk in M (which we remove from M), such that it is not internally tangent to $D_0$, but intersect the edge circle of $D_0$. There must be at least two such disks, else $D_0$ cannot be covered, as its perimeter circle will nor be covered except for a finite number of points.

We compute the two points where the two circles intersect. They define two arcs, one on each circle, that delimit a surface yet to be covered by the other circles. With respect to this surface, the arc belonging to $D_0$ is convex, while the other is concave.

For simplicity and intuition, we call these intersections the angles of the remaining surface. We call sides or edges the arcs between 2 angles that delimit the remaining surface to be covered.

We then chose one of the two angles, and look in M for another circle covering this intersection. This new circle removes at least this angle, and adds usually two new angles. We discuss this further below.

One remark is that the arcs coming from $D_0$ are always convex, while the others are always concave. This is useful to visualize what can occur.

Then we repeat the same step, until there are no angles left, in which case we have a covering of $D_0$, which is tested first, or until there are no disk left in M that can cover a chosen angle, in which case the overlap is incomplete.

To understand this we have to look at intermediate steps in more details. During execution of the algorithm, we may have actually created an uncovered curvy polygon with many angles. When we chose a new disk $D_i$ to cover a chosen angle $A$, we may actually cover several angles of the polygon, and the edges in between, so that we actually reduce the number of edges.

So after choosing the disk $D_i$, we have to find the first edge on both sides of the angle $A$ (not necessarily adjacent to $A$) that are intersected by the circle bounding $D_i$. These two intersections, one on each side, define two new angles and a new edge provided $D_i$, and may replace several edges and angles. Hence the number of sides of the polygon may be reduced rather than increased. It may be also that all sides are covered, in wich case we have covered the whole disk.

There may be cases when the new disk will cut the curvy polygon into two polygons, that will both have to be covered. To check for that, the circle bounding the disk has to be checked for intersection with all edges of the curvy polygon(s).

All this implies of course to keep an up-to-date description of the curvy polygon and the relations between angles, edges and disks. To keep correspondence between the relative positions of angles, if they are listed counter-clockwise on the curvy polygon(s), then they should be counter-clockwise on the circle of the disk $D_0$ and clockwise on the disks from $M$.

There are quite a few details to be worked out, which I would not try without at least checking an implementation. But I believe this basic idea can be implemented.

From this analysis, I think the time complexity is $O(n^2)$, since every steps considers a new disk, and has to look at intersections potentially with all disks that have already been considered.

The extension to spheres is left as an exercise.


Not the answer you're looking for? Browse other questions tagged or ask your own question.