Next / Previous / Contents / NM Tech homepage

6.32. CBCData.overlapCheck(): Do these circles overlap?
# - - -   C B C D a t a . o v e r l a p C h e c k

    def overlapCheck ( self, fromCircle, toCircle):
        '''Do these circles overlap?

          [ fromCircle and toCircle are Circle instances ->
              if the circles overlap ->
                return the percentage of area that they overlap
                in (0.0, 100.0)
              else -> return 0.0 ]

This will require a bit of applied geometry. We don't care about the diameter of the circles, just the degree to which they overlap, so we'll use unit circles of radius 1. Here is a picture of two overlapping circles.

In this figure, C and D are the centers of the two circles of radius 1. If the length of CD is 2 or greater, there is no overlap. If there is overlap, the area of overlap is twice the area of the shaded portion of the figure. This area is called a segment of a circle, meaning the area bounded by a chord and the circle's perimeter. The CRC Standard Mathematical Tables gives this formula for the area of the segment subtended by a given angle θ.

Here R is 1 by definition, so this formula simplifies to:

The angle θ is angle FCG in the figure, which is twice angle FCE. We know that length CF is 1 because it is the radius of a unit circle. We also know that length CE is exactly half of length CD. By simple trig, the cosine of angle FCE is the adjacent side (CE) divided by the hypotenuse, which is 1. So, if S is the separation between the circles in diameters, θ is given by:

Now, on to the code. First, find the separation between the two circles in terms of the standard circle diameter. This is handled in Section 6.33, “CBCData.__circleSep(): Compute the separation of two circles”. The result is expressed in diameters, so a result of 1.0 or greater means no overlap.
        #-- 1 --
        # [ sep  :=  separation between fromCircle and toCircle
        #            as a fraction of CIRCLE_DIAMETER ]
        sep = self.__circleSep ( fromCircle, toCircle )

        #-- 2 --
        if sep >= 1.0:
            return 0.0

The value of sep is the S in the formula above, so now we can compute θ, then the area of the segment. The area of the overlap is twice the area of the segment, which we then convert to a percentage by multiplying by 100.
        #-- 3 --
        # [ theta  :=  angle subtending the segment where two
        #       unit circles overlap if their separation is
        #       (sep) diameters ]
        theta = 2.0 * math.acos(sep)

        #-- 4 --
        # [ overlapArea  :=  twice the area of the segment of a
        #       unit circle subtended by angle theta ]
        overlapArea = theta - math.sin(theta)

Finally, the percentage of overlap is computed as the area of the overlap, divided by the area of a unit circle, which is exactly π, and convert to a percentage by multiplying by 100.
        #-- 5 --
        return 100.0 * overlapArea / math.pi