East Bay Bike Planner Code checked into subversion

[Matt H]

Hello,

I finally figured out how to upload my code to the Subversion
repository on the Google Code site. That was an adventure. I put it
under branches > eastbay. There are folders for:

www: html page and javascripts
database: information necessary to recreate my MySQL database tables
python:


Anyhow, I don't know if it will be comprehensible to anyone. I was
sort of learning python and javascript and coding the site at the same
time. Still, there are some bits of it that I'm fond of. I plan to
write a brief guide to the important parts.

Amar, from a quick look at your code, I am amazed at how much code you
"rolled on your own". Wow, some seriously inventive stuff in there.
John, I'm sure your code is really good too, but it's Greek to me.

I am convinced that using the pgRouting routines are the best way
forward. The reason: the road and bike network geospatial data can be
stored in the PostGIS database online, and we can connect to the
database with various GIS programs like qGIS to view and edit the data
directly. That means that changes can be made quickly and are
effective right away.

The big downside to my code right now is that it requires a whole
bunch of steps to go from shapefile to the database tables and objects
needed by the planner.

Peter, I'm definitely looking forward to your thoughts once you have a
chance to look over these disparate codebases.

Cheers,
Matt

[John Roark]

Matt,

Glad to hear you were able to get your code checked in.

I do like using pgRouting. You still need to convert the shapefiles to
postgis sql but it's fairly simple.

shp2pgsql -s 4326 -i -I sf_streets.shp sf_streets > sf_streets.sql

You should google shp2mysql if you don't already know about it.

John

> --
>
> You received this message because you are subscribed to the Google Groups "sf-bike-planner" group.
> To post to this group, send email to sf-bike...@googlegroups.com.
> To unsubscribe from this group, send email to sf-bike-plann...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sf-bike-planner?hl=en.
>
>
>

[Matthew Heberger]

Thanks, John. I wasn't able to get cygwin installed on my old(ish) Windows XP machine, so I ended up installing and using TortoiseSVN, which seems to work very well. Three things that got me stuck for an hour or two:

1. You have to download some project code BEFORE you can upload anything.
2. You have to use the address for the Google Code page with https and not http or else it will refuse your login.
3. Your Google Code password is NOT the same as your Google Account password. You have to login and then click "Profile" in the upper right to get your password.

I saw the shp2pgsql tool... Am I correct in assuming that you still need to go in and build a topology before you can use "network analyst" or routing routines with it? Not to start throwing around big words... a topology is what makes it a NETWORK, and not just a bunch of lines.

Amar, to answer your question from another thread, there is decent, not great, documentation for PostGIS. I find that a lot of it is written by and for people who already have GIS experience, and who are coming from working with ESRI software.

http://postgis.refractions.net/documentation/

Perhaps more important is the documentation for pgRouting. They have a wiki (I suspect that the developers would rather spend time writing code than writing documentation, so hope that the users do it for them!  The details are sketchy, but it is MUCH more fleshed out than it was a year ago:

http://pgrouting.postlbs.org/wiki/pgRoutingDocs

Hope this helps.

Matt

[amario]

I love how the pgRouting wiki has *no* introduction whatsoever. If
you don't know, you don't need to know!

I'd like to try out whatever visualization software you guys use to
inspect and modify the PostGIS data. Matthew you mentioned qGIS.
Could I use this to check out your DB John? Would it be easier than
me building the DB myself? Either way I'd like to give it a spin, but
would definitely prefer the path of least resistance.

-a-

> On Wed, Dec 9, 2009 at 5:02 PM, John Roark <john.ro...@gmail.com> wrote:
> > Matt,
>
> > Glad to hear you were able to get your code checked in.
>
> > I do like using pgRouting. You still need to convert the shapefiles to
> > postgis sql but it's fairly simple.
>
> > shp2pgsql -s 4326 -i -I sf_streets.shp sf_streets > sf_streets.sql
>
> > You should google shp2mysql if you don't already know about it.
>
> > John
>

> > sf-bike-plann...@googlegroups.com<sf-bike-planner%2Bunsu...@googlegroups.com>
> > .

> > > For more options, visit this group at
> >http://groups.google.com/group/sf-bike-planner?hl=en.
>
> > --
>
> > You received this message because you are subscribed to the Google Groups
> > "sf-bike-planner" group.
> > To post to this group, send email to sf-bike...@googlegroups.com.
> > To unsubscribe from this group, send email to

> > sf-bike-plann...@googlegroups.com<sf-bike-planner%2Bunsu...@googlegroups.com>
> > .

[amario]

So I got gGIS installed -- pretty cool. Interesting to overlay John's
st_streets shapefile with the one I used (from SFGov). There are
slight diffs-- I think SFGov version was more recent.

I ran shp2pgsql -s 4326 -i -I sf_streets.shp sf_streets >
sf_streets.sql

but am embarrassed to say, I have no idea how to run the DB locally! I
installed psql, but don't know the command(s) needed to start up a DB
instance.

-Amar

[Matthew Heberger]

Hi,

I wrote a Readme file for my Python route-finding routine, if anyone is curious... Here's what's in it.  -Matt

Readme for the East Bay Bike Mapper Prototype
Server-side Python scripts

Matthew Heberger, December 2009
mheb...@gmail.com

Here is a list of the different modules used:


MODULE LIST

a_route
    getclosestnode
        dbQuery

    findpath
        dijk
            priodict

    definePathObj
        dbQuery
            conf

    glineenc

    demjson


FUNCTIONS VS. OBJECTS AND METHODS
When I started writing this, I was learning python and javascript. I had heard of object-oriented programming, but didn't really know what it was, or why it's important. Apparently, what I had been doing for years (in VB, mostly) was called "functional programming." I tried to create a few objects, but mostly ended up writing a lot of functions and passing around built-in data types, like you would in Fortran or something... The nice thing about Python is that it lets you do both, so I may have created what looks like an odd mix of styles.


MOD_PYTHON -- PUBLISHER HANDLER

I have set up mod_python to use the Publisher handler. This makes a difference in how information is passed to python, and how it is returned by the server. This means that URL http://domain/abcd.py/efgh will call the function "efgh" of file "abcd.py" Lots more details here:

  http://webpython.codepoint.net/mod_python_publisher_handler


AJAX

The first module, a_route.py, handles the request from the browser. I named it starting with the letter a for convenience, so it will appear first in file lists.

This module handles the request (sent via AJAX) from the browser to map a new route between two points. I decided early on to pass a single parameter, called "jstr" (short for JSON string), because it could store arbitrarily complex information, e.g. javascript nested associative arrays, which are very similar to python dictionaries. Also, if I add new parameters to the web page, I don't have to re-write a lot of code to read in more parameters.

I am using the equivalent of a GET Request, I believe, where the parameters are explicitly appended to the end of the URL, because (1) at the time, I didn't know about GET and POST and the difference between the two, and (2) It was easier to debug that way.

Here is an example AJAX Request:

http://ebmgh.com/python/a_route.py?jstr={"point1":{"Ts":37.812948,"Ub":-122.244951,"x":-122.244951,"y":37.812948},"point2":{"Ts":37.805715207044685,"Ub":-122.26736068725586,"x":-122.26736068725586,"y":37.805715207044685}}

Note: I directly encoded the GMaps Point objects using JSON.stringify, and they contain some redundant information: the coordinates are in (x,y) but also in (Ts, Ub)? Don't know what the reason for that is, but it is something that should eventually be fixed, to make the request string a little more streamlined, and make the transmission slightly faster.


GET CLOSEST START AND END NODES

The points on the map may be from a user double-click or a marker drag-and-drop. That means the point could be anywhere, not necessarily snapped to a road. They could be in the middle of a city block, in a forest with no roads, in the middle of a lake, or in the ocean... So the first step is to figure out the closest node in the network. This is handled by the module "getclosestnode". Essentially, we pass two points (a long/lat pair) and are returned two nodes, the start and the end.

TO DO: When the user drags and drops the marker, we return the coordinates. It would be nicer to return the name of the street or intersection.


GET THE LEAST-COST ROUTE

Once we know the start and end node, we calculate the least-cost path between the two nodes. This is fairly straightforward: we read in the graph, G, stored as a Python dictionary in a .pkl file on disk, and then call the function shortestPath in the module dijk. The cost for the "edges" or paths, between each "node" or intersection is calculated beforehand, and stored in the graph data object. Here we use the findpath module. The Graph object (a python dictionary) is stored in a Python pickle file.


PICKLE FILES?

A .pkl file is a binary file that efficiently stores python data objects and variables. I doubt that the use of pickle files is viable once the bike mapper is expanded to a much bigger geographic area. I suspect that the file would get very large once it has to contain tens of thousands of road segments and intersections, it would be unacceptably slow to read it in, and it may consume a lot of memory, causing me to go over the limit of my $10/month web host.


DIJKSTRA ALGORITHM

I use code that implements the Djikstra algorithm for finding the shortest path. This version is from the python cookbook:

  http://code.activestate.com/recipes/119466/

I made a couple of very small changes to the module, putting two blocks of code into TRY blocks to trap errors that would cause the program to exit. The original code would exit if it encountered any "sink" nodes. These are nodes that have incoming links but no exit. In practice, our bike mapper will probably always have some of these near the edges of our map area, if there are one-way streets heading out to the boundary of our service area.

The dijk module requires the module priodict, which has something to do with queuing. It's all a black box to me, but it works.

  http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228

The shortestPath function returns is an ordered list of edges. Once we have this, we can look up the vertices for the edges, and create the encoded polyline for the Google Map.

ROUTE POLYLINE

I use the module glineenc, a really nice piece of code that I got from a guy named Wyatt Baldwin, who is one of the people behind the bycycle project in Portland, Oregon. I downloaded it from their SVN repository, and later corresponded with Wyatt via email.

  http://project.bycycle.org/

The module takes the polyline coordinates and creates an "encoded polyline string". See:

  http://code.google.com/apis/maps/documentation/polylinealgorithm.html

An encoded polylines have a few advantages over a set of (lng, lat) pairs:

1. It is smaller, so saves on download time
2. It can store the appropriate number of vertices at different zoom levels (when you're zoomed out, you can generally display fewer vertices without affecting the appearance of the line on the map)

DIRECTIONS

The module directions has code for turning the ordered set of edges into text directions like Left on 34th Street, 580 feet, etc.

It makes use of a custom object I created, a dictionary of turn angles, T. Dictionary items are:

  (from_edge, to_edge): angle,

The key is a tuple with two elements, the IDs of the from_edge and to_edge
(The IDs are Long Integers)

The value is an integer representing the turn angle in degrees from 0 - 360

T = { (-254, -260): 0,
      (-1011, -508): 59,
      (645, 615): 271,
        ...
    }

The function getDirections reads T from a pickle file, and uses it to figure out the turn direction from among several possibilities.

In directions.py, getDirections also reads the street names from the MySQL database and uses those to help create the text. There is one disadvantage to the way I have this written. Suppose you are on River Street, and you come to a T intersection. River Street actually continues to the left. We probably want to tell the user "Turn Left to continue on River Street". But my method only gives an indication when the street name changes. So it's not perfect by any means.

I do like the fact that I am displaying distances in feet for short distances, and miles for anything over 0.1 miles, and that everything is getting nicely rounded. (I hate it when a program says go 3.1415926 miles!)

I also threw in a snippet of code to calculate calories burned, greenhouse gas emissions avoided (compared to driving a car), and money saved on gas. These calculations were based on a small study we did at the Pacific Institute:

http://www.pacinst.org/topics/integrity_of_science/case_studies/driving_vs_walking.html

For now, this is just fun, but I can see how some people would be really interested in finding out this information! Of course, the calculations could easily be customized to the individual user and made more accurate...

RETURNING INFO TO THE BROWSER

Since I am using asynchronous calls, the web page does not actually get reloaded. I'm sending everything back as a JSON string. I used the module called demjson. (There were a lot of different choices for converting Python variables to a JSON string, but this one looked like a good choice.)

Finally, in a_route.py, the function index loads the polyline and the html snippet with the directions table and some extra info into a dictionary, for convenience, and returns these.

When the browser receives this info, the javascript code unpacks the JSON string, and sends the polyline to the google map, and the html gets printed on the map.