To render maps using data in a MySQL database, you have to set up a special file called a "virtual datasource" to tell the map generator how to access the data. Create a file named countries.vrt in the same directory as your main script, and enter the following into this file:

<OGRVRTDataSource>
  <OGRVRTLayer name="countries">
    <SrcDataSource>MYSQL:distal,user=USER,passwd=PASS
        tables=countries</SrcDataSource>
    <SrcSQL>SELECT id,outline FROM countries</SrcSQL>
  </OGRVRTLayer>
</OGRVRTDataSource>

Don't forget to replace USER with the username and PASS with the password used to access your MySQL database. Also, make sure all the text from<SrcDataSource> to</SrcDataSource> is on a single line.

Now that we have the virtual datasource file, we can go ahead and set up the MySQL datasource dictionary using the following code:

vrtFile = os.path.join(os.path.dirname(__file__),
                       "countries.vrt")

datasource = {'type'  : "OGR",
              'file'  : vrtFile,
              'layer' : "countries"}

Setting up the datasource dictionary for a PostGIS database is straightforward:

datasource = {'type'     : "PostGIS",
              'dbname'   : "distal",
              'table'    : "countries",
              'user'     : "USER",
              'password' : "PASS"}

Obviously, you should replace USER and PASS with the username and password used to access your PostGIS database.

Obtaining map data from a SpatiaLite database is also straightforward. The only trick is that we have to include the full path to the SpatiaLite database file, so we use __file__ to avoid hardcoding path names into our script:

dbFile = os.path.join(os.path.dirname(__file__),
                      "distal.db")

datasource = {'type'           : "SQLite",
              'file'           : dbFile,
              'table'          : "countries",
              'geometry_field' : "outline",
              'key_field'      : "id"}

As we saw in Chapter 5, Working with Geo-Spatial Data in Python pyproj allows us to do accurate great circle distance calculations based on two lat/long coordinates, like this:

geod = pyproj.Geod(ellps='WGS84')
angle1,angle2,distance = geod.inv(long1, lat1, 
                                  long2, lat2)

The resulting distance is in meters, and we could easily convert this to miles as follows:

miles = distance / 1609.344

Based on this, we could write a simple program to find the features within the desired search radius:

geod = pyproj.Geod(ellps="WGS84")

cursor.execute("select id,X(position),Y(position) " +
               "from places")
for id,long,lat in cursor:
    angle1,angle2,distance = geod.inv(startLong, startLat,
                                      long, lat)
    if distance / 1609.344 <= searchRadius:
        ...

A program like this would certainly work, and would return an accurate list of all features within the given search radius. The problem is one of speed: because there are more than four million features in our places table, this program would take several minutes to identify all the matching placenames. Obviously, this isn't a very practical solution.

We saw an alternative way of identifying features by distance in Chapter 5, Working with Geo-Spatial Data in Python where we looked for all parks in or near an urban area. In that chapter, we used an angular distance to estimate how far apart two points were. An angular distance is a distance measured in degrees—technically, it is the angle between two rays going out from the center of the Earth through the two desired points on the Earth's surface. Because latitude and longitude values are angular measurements, we can easily calculate an angular distance based on two lat/long values, like this:

distance = math.sqrt((long2-long1)**2) + (lat2-lat1)**2)

This is a simple Cartesian distance calculation. We are naïvely treating lat/long values as if they were Cartesian coordinates. This isn't right, but it does give us a distance measurement of sorts.

So, what does this angular distance measurement give us? We know that the bigger the angular distance, the bigger the real (great circle) distance will be. In Chapter 5, Working with Geo-Spatial Data in Python we used this to identify all parks in California that where approximately within 10 kilometers of an urban area. However, we could get away with this in Chapter 5 because we were only dealing with data for California. In reality, the angular distance varies greatly depending on which latitude you are dealing with; looking for points within ±1 degree of longitude of your current location will include all points within 111 km if you are at the equator, 100 km if you are at ±30° latitude, 55 km at ±60°, and zero km at the poles:

Because DISTAL includes data for the entire world, angular measurements would be all but useless—we can't assume that a given difference in latitude and longitude values would equal a given distance across the Earth's surface in any way that would help us do distance-based searching.

Another way of finding all points within a given distance is to use a projected coordinate system that accurately represents distance as differences between coordinate values. For example, the Universal Transverse Mercator projection defines Y coordinates as a number of meters north or south of the equator, and X coordinates as a number of meters east or west of a given reference point. Using the UTM projection, it would be easy to identify all points within a given distance by using the Cartesian distance formula:

distance = math.sqrt((long2-long1)**2) + (lat2-lat1)**2)
if distance < searchRadius:
    ...

Unfortunately, projected coordinate systems such as UTM are only accurate for data that covers a small portion of the Earth's surface. The UTM coordinate system is actually a large number of different projections, dividing the world up into 60 separate "zones", each six degrees of longitude wide. You need to use the correct UTM zone for your particular data: California's coordinates belong in UTM zone 10, and attempting to project them into UTM zone 20 would cause your distance measurements to be very inaccurate.

If you had data that covered only a small area of the Earth's surface, using a projected coordinate system would have great advantages. Not only could you calculate distances using Cartesian coordinates, you could also make use of database functions such as PostGIS' ST_DWithin() function to quickly find all points within a given physical distance of a central point.

Unfortunately, the DISTAL application makes use of data covering the entire Earth. For this reason, we can't use projected coordinates for this application, and have to find some other way of solving this problem.

Actually, there is a way in which DISTAL could use projected UTM coordinates, but it's rather complicated. Because every feature in a given database table has to have the same spatial reference, it isn't possible to have different features in a table belonging to different UTM zones—the only way we could store worldwide data in UTM projections would be to have a separate database table for each UTM zone. This would require 60 separate database tables! To identify the points within a given distance, you would first have to figure out which UTM zone the starting point was in, and then check the features within that database table. You would also have to deal with searches that extend out beyond the edge of a single UTM zone.

Needless to say, this approach is far too complex for us. It would work (and would scale better than any of the alternatives), but we won't consider it because of its complexity.

In the previous chapter, we looked at the process of identifying all points within a given polygon. Because MySQL only handles bounding box intersection tests, we ended up having to write a program that asked the database to identify all points within the bounding box, and then manually checked each point to see if it was actually inside the polygon:

This suggests a way we can solve the distance-based selection problem for DISTAL: we calculate a bounding box that encloses the desired search radius, ask the database to identify all points within that bounding box, and then calculate the great circle distance for all the returned points, selecting just those points that are actually inside the search radius. Because a relatively small number of points will be inside the bounding box, calculating the great circle distance for just these points will be quick, allowing us to accurately find the matching points without a large performance penalty.

Let's start by calculating the bounding box. We already know the coordinates for the starting point and the desired search radius:

Using pyproj, we can calculate the lat/long coordinates for four points by traveling radius meters directly north, south, east, and west of the starting point:

We then use these four points to define the bounding box that encloses the desired search radius:

Here's a Python function to calculate this bounding box:

import pyproj

def calcSearchBounds(startLat, startLong, searchRadius):
    geod = pyproj.Geod(ellps="WGS84")

    x,y,angle = geod.fwd(startLong, startLat, 0,
                         searchRadius)
    maxLat = y

    x,y,angle = geod.fwd(startLong, startLat, 90,
                         searchRadius)
    maxLong = x

    x,y,angle = geod.fwd(startLong, startLat, 180,
                         searchRadius)
    minLat = y

    x,y,angle = geod.fwd(startLong, startLat, 270,
                         searchRadius)
    minLong = x

    return (minLong, minLat, maxLong, maxLat)

Note that, because we're using pyproj to do a forward geodetic calculation, this will return the correct lat/long coordinates for the bounding box regardless of the latitude of the starting point. The only place this will fail is if startLat is within searchRadius meters of the North or South Pole—which is highly unlikely given that we're searching for cities (and we could always add error-checking code to catch this).

Given this function, we can easily create a Polygon containing the bounding box, and use the database to find all features within that bounding box. First, we create the Polygon and convert it to WKT format:

from shapely.geometry import Polygon
import shapely.wkt

p = Polygon([(minLong, minLat), (maxLong, minLat),
             (maxLong, maxLat), (minLong, maxLat),
             (minLong, minLat)])
wkt = shapely.wkt.dumps(p)

We can then pass this to the database to find all points within the bounding box, using a spatial join. We haven't looked at the concept of spatial joins yet, so let's do that now.

If you have worked with databases in the past, you're probably already familiar with the concept of a join operation, where you combine information from two or more linked database tables. A traditional database join links tables together using field values, for example by storing the primary key of one record in a second table:

You can then join the tables together like this:

SELECT books.title,publisher.name FROM books,publishers
 WHERE books.publisherID = publishers.id;

A spatial join works in the same way, except that you connect the records using spatial predicates like MBRIntersects(), ST_Contains(), or ST_DWithin(). These predicates identify records that are related in some way spatially, for example by having overlapping bounding boxes or being within a given distance of each other.

In this case, we want to use a spatial join to identify all the places within the calculated lat/long bounding box. To do this using MySQL, we would write the following:

connection = MySQLdb.connect(user="...", passwd="...")
cursor = connection.cursor()

cursor.execute("USE distal")

cursor.execute("SELECT id,name,X(position),Y(position) " +
					"FROM places WHERE MBRContains(" +
               "GeomFromText(%s), position)", (wkt,))
for row in cursor:
    ...

Using PostGIS:

connection = psycopg2.connect("dbname=... user=...")
cursor = connection.cursor()
cursor.execute("SET NAMES 'utf8'")

cursor.execute("SELECT id,name,X(position),Y(position) " +
               "FROM places WHERE ST_Contains(" +
               "GeomFromText(%s, 4326), position)", (wkt,))
 for row in cursor:
    ...

Remember that SpatiaLite doesn't automatically use a spatial index for queries. To make this code efficient in SpatiaLite, we have to check the spatial index directly:

db = sqlite.connect("distal.db")
db.enable_load_extension(True)
db.execute('SELECT load_extension("...")')
cursor = db.cursor()

cursor.execute("SELECT id,name,X(position),Y(position) " +
               "FROM places WHERE id in (SELECT pkid " +
               "FROM idx_places_position " +
               "WHERE xmin >= ? AND xmax <= ? " +
               "AND ymin >= ? and ymax <= ?)",
               (minLong, maxLong, minLat, maxLat))
for row in cursor:
    ...

Obviously, spatial joins work best if the database includes spatial indexes that can be used to join together the two tables. One of the challenges of developing spatial queries is to make sure that the database can and does use your spatial indexes; using the techniques described in the previous chapter, you can analyze your queries, and modify them if necessary, to ensure that your spatial indexes are used.

Now that we have identified all the points within the bounding box, we can check the Great Circle distance and discard those points that are inside the bounding box, but outside the search radius:

...

geod = pyproj.Geod(ellps="WGS84")

for row in cursor:
    id,name,long,lat = row
    angle1,angle2,distance = geod.inv(startLong, startLat,
                                      long, lat)
    if distance > searchRadius: continue

    ...

Using this logic, we can achieve a 100 percent accurate distance-based lookup on placenames, with the results taking only a fraction of a second to calculate.