Location-Based Human Computation

In what ways can human computation be useful in developing relevant mapping applications? To answer this question we have to think about how you, the User, interacts with an embedded map. For example, the user of a map application on a Police Department's website usually wants to know about safety in their neighborhood. The traditional map usually has a number of fields for the user to enter an address, and dropdown menus for filtering the crime data, etc.

Figure 1. Map Interface with several search form fields.

 

 This method works well in retrieving information, but their are a few flaws with this method. Firstly, the end user has complete control to filter crime information for a given address, but often may receive empty results for their query. This happens, for example, when a user searches for crimes that have not, and may never occur at their location. I propose a more intelligent system that returns information to the user that is more relevant to their query.

 

The first challenge when developing the Mapplication for the Police Department, was to take a user's address query and return the locations "Police Service Area." The PSA is a sub-division of each Police District of the city, and has a Lieutenant assigned to each.  Once the PSA is determined, all information about the PSA and District are returned back to the user. The technical challenge here is determining which polygon region the address is in.

 

Figure 2. Mapplication Interface with District Polygon Overlays www.phillypolice.com/districts

 

 

The Point in Polygon Challenge

When approaching a problem, often a simple solution exists, but arriving at this solution may require a thorough understanding of the fundamentals of the problem. As was the case with the following Geometric Proof I encountered while developing the Mapplication.

 

Given: the following image drawn as the following:

Prove:

1. The red point is inside the Polygon.

2. The Blue Point is Outside the Polygon.

3. The Teal Point is neither outside or inside the Polygon. (It is a vertex of the Polygon)

 

The above Proof was the fundamental challenge I needed to solve in order to get the Philly Police District Maps to function as a Location-Based Information Retrieval System. When the user enters their address, The map interface zooms to the location, and returns the police district, service area, and recent nearby crimes (coming soon!)

 

It turns out that this is a popular Computer Science Problem, and there have been a number of solutions developed. As such, I had to consider the cost (i.e. efficiency of the solution code), and the accuracy of the results. Accuracy is actually not a major issue because the resolution of our map interface within the browser negates the error factor encountered by most "Point in Polygon" Algorithms.

 

 

The Code

There are different variations of code depending the language you are coding in. (todo: Link to Google Code Repository) Visit http://www.visibone.com/inpoly/ for a deeper discussion on the Point in Polygon problem. Below is a (very) basic flow chart of the system.

Figure 3 Mapplication Very Basic Flow Chart.

 

Some things I noted when debugging my point in polygon script were:

 

• Remember to optimize and keep the code simple and clean.
• Keep the number of server requests (i.e. AJAX calls) to one (no more than 3)
• Utilize onLoad method when retrieving polygon data from kml files.

Remember tools like Google Chrome's Inspector Tool, or Firebug, or Microsoft Debugger are your friend. Uitilize their services wisely. ;)

 

 

Part 2 - Data Relevance

In the next article I will discuss the importance of generating data relevant to a user's query. The Mapplication's goals are to make location information more accessible and relevant. The only way to achieve these goals are to optimize the time it takes query data, and return the most relevant results.

 

 

Resources

Mapplication Live in the Wild - www.phillypolice.com/districts

http://citymaps10.phila.gov/Map/default.aspx

 

Detrmining If a Point Lies on the Interior Of a Polygon - http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/

A Point About Polygons - http://www.visibone.com/inpoly/

Google Maps Api v2 - http://code.google.com/apis/maps/documentation/

Human Computation - http://video.google.com/videoplay?docid=-8246463980976635143#

MoodSwings - http://ismir2008.ismir.net/papers/ISMIR2008_257.pdf

 

 

If you have any question contact me at questions@emelle.me, or leave a comment.