[OSM-dev] [Geowanking] shortestpathtree.org - a tool for quickly checking OSM data integrity

Sean Gorman sean at geoiq.com
Mon Mar 12 17:09:50 GMT 2012


Cool you might get a bit better performance here:

https://github.com/bgrins/javascript-astar

Purely supposition on my part have not tested it

cheers,
sean

On Mon, Mar 12, 2012 at 1:05 PM, Brandon Martin-Anderson
<badhill at gmail.com>wrote:

> About thirty lines of javascript implementing a pretty brain-dead
> breadth-first search:
>
> https://github.com/bmander/vtp/blob/master/templates/game.html#L118
>
> -B
>
> On Mon, Mar 12, 2012 at 1:01 PM, Sean Gorman <sean at geoiq.com> wrote:
> > Awesome work - for the shortest path calculation are you using an A*,
> > Bellman-Ford type approach, or something else?  We tried a bunch of
> > optimizations to a Floyd style all-to-all SP problem back in the day.
> >  Tricky computations and always cool to see new approaches.  Not
> > to mention a brilliant visualization of it all.
> >
> > thanks,
> > sean
> >
> > On Mon, Mar 12, 2012 at 12:49 PM, Brandon Martin-Anderson
> > <badhill at gmail.com> wrote:
> >>
> >> Not directly. Stochastic optimizing processes, or optimizing processes
> >> over stochastic data sets, tend to end up looking biological, because
> >> biological systems are stochastic optimizing processes.
> >>
> >> -B
> >>
> >> On Mon, Mar 12, 2012 at 12:42 PM, Laurence Penney <lorp at lorp.org>
> wrote:
> >> > Utterly beautiful.
> >> >
> >> > Is it inspired by Günther von Hagens’s work with blood vessels?
> >> >
> >> > http://weheartit.com/entry/19937599
> >> > http://plastynarium.pl/images/2011/10/krwiobieg.jpg
> >> >
> >> >
> http://3.bp.blogspot.com/_DaOtlZ8Ux7s/TFmhpAJziMI/AAAAAAAAADE/PFP15vpUZlU/s1600/bodies-revealed-blood-vessels.jpg
> >> > http://www.bodyworlds.com/en/media/picture_database/preview.html?id=4
> >> > http://thedispersalofdarwin.files.wordpress.com/2011/11/img_0690.jpg
> >> >
> >> > - Laurence
> >> >
> >> > On 12 Mar 2012, at 16:11, Brandon Martin-Anderson wrote:
> >> >
> >> >> Behold! I made a thing.
> >> >>
> >> >> http://shortestpathtree.org
> >> >>
> >> >> It creates shortest path trees, which are pretty, and have a variety
> >> >> of uses. My favorite use is quickly and phenomenologically checking
> >> >> OSM referential integrity across entire cities. Also, potentially, it
> >> >> can tell you how to get places. Tell me how you like it.
> >> >>
> >> >> Colophon, for the interested:
> >> >> Server and client-side code is at https://github.com/bmander/vtp. I
> >> >> took Migurski's city extracts in PBF format and popped them into a
> >> >> Mongodb instance using a homebrew script in node.js. Then I applied a
> >> >> series of map-reduce runs to slice the ways at shared intersections,
> >> >> and to collect them into tiles. This is slow, but there's some home
> of
> >> >> parallelization. A simple node.js script serves the vector tiles to
> >> >> the client, where all routing is done; printed to a homebrew
> >> >> canvas-based client. The disadvantage is that routing is slow for
> you.
> >> >> The advantage is the server doesn't have to do anything except hand
> >> >> out tiles, which, ideally, should be pretty small.
> >> >>
> >> >> -B
> >> >>
> >> >> _______________________________________________
> >> >> dev mailing list
> >> >> dev at openstreetmap.org
> >> >> http://lists.openstreetmap.org/listinfo/dev
> >> >
> >>
> >> _______________________________________________
> >> Geowanking mailing list
> >> Geowanking at geowanking.org
> >> http://geowanking.org/mailman/listinfo/geowanking_geowanking.org
> >
> >
> >
> >
> > --
> > Sean Gorman PhD.
> > GeoIQ
> > 2200 Wilson Blvd. Suite 307
> > Arlington VA, 22201
> > mobile: 202-321-3914
> > office: 703-647-2151
> >
> > --
> > This email and the information it contains are confidential and may be
> > privileged. If you have received this email in error please notify me
> > immediately. You should not copy it for any purpose, or disclose its
> > contents to any other person. Internet communications are not secure and,
> > therefore, FortiusOne does not accept legal responsibility for the
> contents
> > of this message as it has been transmitted over a public network. If you
> > suspect the message may have been intercepted or amended please contact
> the
> > sender.
> >
>



-- 
Sean Gorman PhD.
GeoIQ
2200 Wilson Blvd. Suite 307
Arlington VA, 22201
mobile: 202-321-3914
office: 703-647-2151

--
This email and the information it contains are confidential and may be privileged. If you have received this email in error please notify me immediately. You should not copy it for any purpose, or disclose its contents to any other person. Internet communications are not secure and, therefore, FortiusOne does not accept legal responsibility for the contents of this message as it has been transmitted over a public network. If you suspect the message may have been intercepted or amended please contact the sender.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20120312/4c1df916/attachment.html>


More information about the dev mailing list