Algorithm to check if a Circle is totally contained in the area of other circles

Question

What would be the algorithm to check if a circle like the blue one below is TOTALLY contained in the area of other circles (the while circles). I want a TRUE for the blue circle and a FALSE for the red circle

The input for all circles is their coordinates and their radius.

Answer 1

I don't think there's an easy solution.

I would address that by taking every circle in turn, and performing a boolean subtraction of all other circles. (The circles that are far enough - R0 + R1 < D12 - will not interfere.)

After pieces have been eaten, a circle becomes a curvilinear polygon made of circular arcs, or a set of such polygons, as connexity can be broken. A polygon can be represented by the list of circles that contribute an arc of its outline, and the arcs endpoints are defined by the common intersection of two consecutive neighbors, or of the target circle and a neighbor. Note that the same neighbor can appear several times.

To make things a little more gory, the polygons can have holes, which you need to represent as well.

Then a crucial operation is the subtraction of a circle from a curvilinear polygon. You need to detect the arcs that are wholly inside the new circle and those that cross it. After getting the remaining portions of the arcs, you need to rearrange the remaining arcs and the new one(s).

I guess that all these operations can be built from a single primitive that finds the portion of an arc (defined by three circles) that is inside a disk.

Answer 2

Here's a crude solution:

• Take all the circles and find all intersection points which are either on or inside the test circle T. Split the corresponding edges and build an edge graph:

For each edge keep track of the circle that created it.

• Find all the non-overlapping regions inside the circle, using the minimum-cycle algorithm (Find all non-overlapping polygons in a list of edges/vertices).

• For each bounding edge E of each region R you find, take the circle C that E belongs to. If C is not T (red) - i.e. E is blue, check if the points on the other edges of R are inside the C:

  • If they are then C covers R. Continue onto the next region.
  • If they are not, then R is not covered by C. Loop over the other blue edges bounding R.
  • If at the end R is still not covered, then T is not completely covered - return false.

in the above diagram, C contains B, so R is covered; but C does not contain A, so does not cover S

• If you haven't returned yet at this stage then return true.

---

Side cases:

• If a certain circle contains T, then ignore it.
• If T contains it, then defer the intersection test by storing it in a list. At the end redo the test and split its edges.

This algorithm is highly inefficient, and I'm not 100% sure if there are any more degenerate cases; if anyone has any suggestions please let me know.

Answer 3

This seems simple (EDIT: but is not): if every point of every arc of a given circle is contained in at least one of the other circles, then the whole circle is contained. You would then have to find all intersections (algorithm to detect if a Circles intersect with any other circle in the same plane), and do a check for all arcs which are specified by these intersections. If any "inside" point of an arc A1-A2 of circle A for given two intersections with Circle B (arc B1-B2, where points A1=B1 and A2=B2) is contained in the circle B, then the whole arc is contained in circle B and vice-versa. Please correct me if I am wrong.

EDIT: Ok I already know, that I was wrong, as has maxim1000 shown. This is more complicated than I thought. I think of adding something to my answer, but I am not sure, whether this is a solution. I hope it helps, though. Namely: I think of determining the total area of intersections between our circle in mind and all others. We find all separated intersections within our circle - all parts that include the same points, that are separated by all intersecting arcs - and find their areas. Wu sum them up. If it is equal to the area of our circle, then our circle is contained in other circles. Determining this area may be a problem on its own, but as I said, it may lead into the right direction. Let me think too..

EDIT: After a while of thinking. Determining all the areas in (multiple) intersecting circles is just a matter of adding or subtracting triangles or ...hmmm... how to call them? ...yellow parts like here on the image :)