Next / Previous / Contents / NM Tech homepage

6.30. CBCData.overlappers(): Find overlapping circles
# - - -   C B C D a t a . o v e r l a p p e r s

    def overlappers(self, fromCircle):
        '''Find circles that overlap fromCircle.

          [ fromCircle is a Circle instance ->
              return a list of tuples (pct,c) representing all the
              circles in self that overlap fromCircle, such that c is
              the overlapping Circle instance and pct is the
              percentage of their areas that overlap in the interval
              (0.0, 100.0) ]

For performance reasons, we would like to avoid comparing the fromCircle with every circle in the database. To reduce the number of candidates, we will start by considering how big a difference in latitude or longitude is necessary to guarantee no overlap, that is, how many minutes of latitude or longitude are guaranteed to be greater than 15 miles at any location on the globe.

A given difference in degrees of latitude is always the same distance in miles. However, for a given difference in degrees of longitude, the distance in miles is largest at the equator. The author has written a package to perform mapping calculations; see A Python mapping package for particulars. Here is a conversational session using this package. Point zero is the intersection of the 0°meridian and the equator. Point e15 is fifteen miles east along the equator, and point n15 is fifteen miles north along the meridian. The .offsetFeet() method produces the new location along a given bearing (the first argument, in radians), and the second argument is the distance along that bearing in feet.

>>> from math import pi
>>> from terrapos import *
>>> zero=LatLon(0.0, 0.0)
>>> fifteen=5280.0 * 15    # Fifteen miles in feet
>>> e15=zero.offsetFeet(pi/2, fifteen)  # Fifteen miles east
>>> print e15.lonDeg*60    # Longitude in minutes
>>> n15=zero.offsetFeet(0, fifteen)     # Fifteen miles north
>>> print n15.latDeg*60    # Latitude in minutes

Hence, we can guarantee that any circle whose latitude or longitude is 14 or more minutes away cannot overlap fromCircle. This value is defined in Section 6.3.26, “OVERLAP_MINUTES.

To convert this condition into a range test of latitude and longitude in our database query, we must find the circles whose latitude and longitude are within range. See Section 6.31, “CBCData.degMinAdd(): Lat/long arithmetic” for the method that does arithmetic on latitudes and longitudes in character form, which always returns the new quantity as “dddmm”.
        #-- 1 --
        # [ loLat  := minus OVERLAP_MINUTES, as "ddmm"
        #   loLon  :=  fromCircle.lon minus OVERLAP_MINUTES, as "dddmm"
        #   hiLat  := plus OVERLAP_MINUTES, as "ddmm"
        #   hiLon  :=  fromCircle.lon plus OVERLAP_MINUTES, as "dddmm" ]
        loLat = self.degMinAdd(, -OVERLAP_MINUTES)[1:]
        loLon = self.degMinAdd(fromCircle.lon, -OVERLAP_MINUTES)
        hiLat = self.degMinAdd(, OVERLAP_MINUTES)[1:]
        hiLon = self.degMinAdd(fromCircle.lon, OVERLAP_MINUTES)

Now we can do a query on the circle table and constrain it as a range of latitudes and longitudes.
        #-- 2 --
        # [ candidates  :=  Circle instances in self whose lat and lon
        #       are in the range [loLatLon, hiLatLon]
        #   result  :=  a new, empty list ]
        candidates = ( self.s.query(self.Circle)
            .filter( >= loLat)
            .filter(self.Circle.lon >= loLon)
            .filter( <= hiLat)
            .filter(self.Circle.lon <= hiLon)
            .all() )
        result = []

Next we add to result tuples (pct, c) for circles that actually overlap. This check is performed in Section 6.32, “CBCData.overlapCheck(): Do these circles overlap?”.
        #-- 3 --
        # [ result  +:=  tuples (pct, c) for circles in candidates
        #       that overlap fromCircle to any nonzero degree ]
        for toCircle in candidates:
            #-- 3 body --
            # [ if toCircle and fromCircle are distinct circles that
            #   overlap to any nonzero degree ->
            #     result  +:=  a tuple (pct, toCircle) where pct is the
            #         percentage area overlap
            #   else -> I ]
            if fromCircle is not toCircle:
                pct = self.overlapCheck(fromCircle, toCircle)
                if pct > 0.0:
                    result.append ( (pct, toCircle) )

Finally, sort the list in descending order by percent overlap, and return it.
        #-- 4 --
        return result