search

tedsteiner / OpenStreetMap.jl

Julia OpenStreetMap Package
Other
52 stars 18 forks source link

Intersection clustering #59

Closed tedsteiner closed 9 years ago

tedsteiner commented 9 years ago

This code addition (no changes to existing functions were needed) allows clustering of intersection nodes into a single node. This is helpful in the case of boulevards and divided highways crossing one another and inducing 3+ intersections, rather than a single highway intersection. This allows you to get a better estimate of how many highway intersections are present in a region, because the divided highways will not inflate the count.

There is also a function included to replace all clustered intersections' node IDs in the highway list, so that the highways all pass through a single point. This might speed up routing a little bit in some cases, and also enables findIntersections() to be run again on the new set of highways to get the more accurate count.

I also added tests and documentation for the features.

Closes Issue #31.

coveralls commented 9 years ago

Coverage Status

Coverage increased (+1.96%) when pulling 64472170d953ade1cfcb8b5ce6262208e3e44fc4 on IntersectionConsolidation into 37a4e40fab1abe06eb1d03600b06fb73b796cd81 on master.

garborg commented 9 years ago

Very cool. It will be interesting to see how this plays with @yeesian's work on turn restrictions / relations -- exciting to see a lot in motion!

tedsteiner commented 9 years ago

Yeah, I'm not sure how it will go with turn restrictions. Probably we will need to make the function that replaces nodes in the highway list smarter, to make sure it preserves the turn restrictions, shifting them as necessary.

In general use, it's probably not necessary to have them both working together. If you want accurate routing, you'll probably use the full graph. This is more about counting the intersections. And it would also be useful for "human readable" driving directions, so we could give a list of intersections. Even in that case, though, all that would be needed is the mapping between true intersections and their associated clusters (the output of the clustering function).

tedsteiner commented 9 years ago

It looks like Travis failed only on the julianightlies branch, involving reading the xml files with libexpat:

signal (11): Segmentation fault
XML_SetUserData at /home/travis/.julia/v0.4/LibExpat/src/lX_common_h.jl:4

Has anyone tried running `Pkg.test("OpenStreetMap") with version 0.4 yet?

garborg commented 9 years ago

Yep, I generally work on 0.4, and then test at the end that I'm also 0.3 compatible. Merging #55 passed Travis on 0.4, and I also tested it locally on 0.4. I've tagged a new version of LibExpat.jl since then, though -- it was tested alone and under OpenStreetMap.jl on 0.4 before tagging, but who knows. I can't look more now, but I will try to look later.

garborg commented 9 years ago

I tested this branch on 0.4 locally, all passing. Opening another issue for the recent Travis-only 0.4 failures, to handle separately if it doesn't go away in a day or so.

tedsteiner commented 9 years ago

Ok, I'll go ahead and merge it then, despite Travis being cranky. It looks like the master branch is having the same issue right now, anyways.