|< Day Day Up >
Hack 52. Google Cartography: Street Art in Your Neighborhood
cartography n. The art or technique of making maps or charts.
Google Cartography (found here: http://richard.jones.name/google-hacks/google-cartography/google-cartography.html) uses Google via the Google Search API [Chapter 9] to build a visual representation of the interconnectivity of streets in an area.
This application takes a starting street and finds streets that intersect with it. Traversing the streets in a breadth-first manner, the application discovers more and more intersections, eventually producing a graph that shows the interconnectivity of streets flowing from the starting street.
Figure 3-5. New York, U.S., as determined by Google cartography
Figure 3-6. Melbourne, Australia, mapped by a little Google cartography
3.6.1. The Gory Details
Google Cartography uses the Google API to find web pages that refers to street names. Initial street and region criteria are combined to form a search query, which is then executed by the Google API. Each URL from the Google results is fetched and the content of the pages converted into text. The text is then processed using pattern matching (programmers, read: regular expressions) designed to capture information relating to the relationship between streets (for example, streets that cross each other or turn into other streets).
For each page a list of vertices is produced, where each vertex represents an intersection between two streets. After the results for the initial street have been processed, the list of vertices will hopefully contain some vertices that intersect with the initial street.
At this point, the mapper performs a breadth-first search through the streets that can be reached from the initial street. Each street traversed during this process is subjected to the same process as the initial street, expanding the list of known street intersections. This process continues until no more streets can be reached from the initial street or until the halting criteria is satisfied (for instance, reaching the maximum amount of Google API key usage).
Once the data collection phase has completed, the application converts the intersection vertices into a graph. Each street becomes a vertex of its own, with outgoing edges connecting to the vertices of intersecting streets. The connectivity of this graph is analyzed (using the Jung graph package at http://jung.sourceforge.net) to determine the largest maximal subgraph where all pairs of vertices are reachable from each other. This subgraph almost always contains the starting street; the probability of this not occurring should decrease proportionally to the number of streets traversed (which naturally selects for streets that are in the same subgraph as the starting street).
The largest connected subgraph is then visualized using a Radial Layout algorithm provided by the Prefuse graph visualization framework (http://prefuse.sourceforge.net). The graph is initially centered on the start street but will automatically adjust its focus to center around the most recently selected street.
Ignoring its general lack of usefulness (at the time of this writing), there are several problems with the application worth noting:
3.6.2. Running the Hack
Point your web browser at http://richard.jones.name/google-hacks/google-cartography/applet/mapping.html.
When the "Enter parameters" applet window appears (shown in Figure 3-7), enter your Google API key and adjust the maximums per instructions on the Google Cartography page. Now, type in your starting street and any additional search criteria by which to narrow the search.
Figure 3-7. Enter a starting point of interest and anything that might narrow down the possibilities
After a little churning, the applet will display a map for your street and region of interest similar to those in Figures Figure 3-6.
|< Day Day Up >