Verifying addresses within a set geographic region served by a library

Our library client wanted to allow patrons to apply for library cards via their website. The client had existing restrictions on access to cards. Local residents receive free cards while visitors and non-residents pay a fee. Individual patrons should not have access to more than one library card.  Therefore the system had to automatically validate and standardize addresses to support duplicate detection, determine a geographical position for each address, and finally classify addresses as local or non-local. We supported this using GeoJSON and integrating with the library's ILS. We tested this functionality a number of ways, including an exploration into the mathematic principles behind the solution.

Address collection

The first step in the registration process is collecting the patron’s address, which is done by use of an online form. This form includes the usual fields: street, building number, city, province, and postal code. There is an optional line for additional details.

The library wanted to ensure each patron could hold only one card, which meant matching submitted addresses against existing database records.  Specificity is important for this, so addresses needed a standardized format to avoid mismatches such as on abbreviations like St. for Street.

To meet this goal, Mugo applied the Canada Post Address Complete JavaScript service. This service allows matching against the Canada Post address database on partial input and presenting options in a drop down.

The patron then selects a drop down option which automatically fills in the address fields with the canonical Canada Post values.

Determining a geographic position for an address

The next step is to obtain a latitude and longitude for an address as supplied by Canada Post.  This is essential for verifying whether a patron lives within the library service area.  We integrated with Google's Geocoding API for this. The Geocode service accepts an address in standard format (building number, street, city, province, postal code) and returns a latitude and longitude.

Defining library service area

Mugo was given an HTML file with embedded JavaScript. That script had a data structure that stored the positions defining the boundaries of York Region, and a function to check whether a point lies within the interior. This data structure follows a standard GeoJSON format, and you can use the GeoJSON web interface to display it directly.

GeoJSON turns the data into sets of polygons, with areas that encompass the region and smaller sets of polygons to exclude areas within the region (such as bodies of water).

Here is an example of the data viewed via that web page, showing an island and excluding the water features.

We tested the data thoroughly to make sure that it was accurate, and then integrated it with Google Maps. 

By using GeoJSON with its capability to accurately represent arbitrary regions of the Earth’s surface, we avoid having to guess whether an applicant is within the library service area based on their postal code.

Verifying addresses within the region

With the area is defined, we tested to check if the address is within the boundaries. GeoJSON has a built-in script to do this, but let's explore the principle behind the script.

You can determine whether a point (x, y) lies inside a polygon by counting the number of times a line drawn starting at that point intersects the polygon’s boundaries. First, draw a horizontal line segment or ray starting at the specified point running to the right. Count the number of times the ray intersects one of the edges of the polygon. An odd number of intersections means the ray crossed to the outside; an even number of intersections means the ray started from the outside.
 

Bonus mathematical proof of concept

Given two points on the polygon i and j, the line segment running between them, from j to i,  satisfies the following, for values of 0 <= t <=1

X axis value : t xj + (1-t) xi 

Y axis value : t yj + (1-t) yi

Given the point (x,y), a ray running horizontally to the right, for s >= 0 satisfies

X axis value : x + s

Y axis value : y

We have 2 linear equations in the 2 variables s, t.  If there is a solution with 

0 <= s

0 <= t <= 1

Then the ray extending from the point intersects that line segment.

Setting them equal we see

t xj + (1 - t) xi = x + s

t yj + (1 - t) yi = y

Rearranging shows us the value of t immediately, from the 2nd equation

t (xj -xi) = x - xi + s

t (yj - yi) = y - yi

Or t = (y - yi) / (yj - yi)

Substituting that into the first equation and solving for s

(y - yi) (xj - xi) / (yj - yi) = x - xi + s

So 

s = (y - yi) (xj - xi) / (yj - yi) - x + xi

For an intersection, s has to be 0 (line on the point) or positive (ray hits the point after some distance to the right)

For 0 <= s

0 <=  (y - yi) (xj - xi) / (yj - yi) - x + xi

x <=  (y - yi) (xj - xi) / (yj - yi) + xi

Practical math in application

The function in the GeoJSON provided can be seen to be using the above intersection condition:

  function inside(point, vs) {
       var x = point[0], y = point[1];
       var inside = false;
       for ( var i = 0, j = vs.length - 1; i < vs.length; j = i++ ) {
           var xi        = vs[i][0], yi = vs[i][1];
           var xj        = vs[j][0], yj = vs[j][1];
           var intersect = ( ( yi > y ) != ( yj > y ) ) && ( x < ( xj - xi ) * ( y - yi ) / ( yj - yi ) + xi );
           If (intersect) inside = !inside;
       }
        return inside;
   }

The first condition involving yi > y != yj > y checks that the point (x, y) is neither above both points i, j nor below both points. This avoids double-counting a ray that hits a boundary point, and doesn’t count polygon edges parallel to the ray (which would have an infinite number of intersection points).

Conclusion

Using this script, along with the data provided, patrons can enter their address in the online library card application, and the system will automatically verify that they are eligible for a card. If the address supplied is outside the region, they are prompted to pay a yearly non-resident card fee. There is an additional layer of verification that goes through a library staff approval workflow. Staff get an automated email whenever a form is submitted, with a link to review the data and click approve or reject. If approved, the patron gets an immediate email with their library card details.