# - - - 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
zero is the intersection of the
0°meridian and the equator. Point
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
>>> 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 13.025057227 >>> n15=zero.offsetFeet(0, fifteen) # Fifteen miles north >>> print n15.latDeg*60 # Latitude in minutes 13.025057227
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, “
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, “
arithmetic” for the method that does
arithmetic on latitudes and longitudes in character form,
which always returns the new quantity as “
#-- 1 -- # [ loLat := fromCircle.lat minus OVERLAP_MINUTES, as "ddmm" # loLon := fromCircle.lon minus OVERLAP_MINUTES, as "dddmm" # hiLat := fromCircle.lat plus OVERLAP_MINUTES, as "ddmm" # hiLon := fromCircle.lon plus OVERLAP_MINUTES, as "dddmm" ] loLat = self.degMinAdd(fromCircle.lat, -OVERLAP_MINUTES)[1:] loLon = self.degMinAdd(fromCircle.lon, -OVERLAP_MINUTES) hiLat = self.degMinAdd(fromCircle.lat, 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(self.Circle.lat >= loLat) .filter(self.Circle.lon >= loLon) .filter(self.Circle.lat <= hiLat) .filter(self.Circle.lon <= hiLon) .all() ) result = 
Next we add to
( for circles that actually overlap.
This check is performed in Section 6.32, “
CBCData.overlapCheck(): Do these circles
#-- 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 -- result.sort() result.reverse() return result