nearby transits for a place/location by lat/lon

[Basit]

how can i know what transits are nearby for a location. like google
maps detail page has it for every location, i want to create similar
thing for my service.

[Joa]

Not sure where your challenge in particular lies; but generally, it
sounds like there are two pieces of "plumbing" that you need to bring
together: One would be to obtain the relevant stop data, the other the
calculation of distances between a given location, and the stops of a
stop set.
1. You can pull stop data from published GTFS feeds. There are a few
sites dedicated to linking to the various feeds, such as GTDF:
http://code.google.com/p/googletransitdatafeed/wiki/PublicFeeds
This is a list of published GTFS feeds that contain stop data from a
variety of transit agencies.
2. The following is a good writeup for the calculation of distances
over the (theoretical) spherical profile of the Earth:
http://www.movable-type.co.uk/scripts/latlong.html
There's also lots of other useful formulas. For some reason the
examples are in JavaScript, but the sample code should easily
translate into whatever language you need or want to code in.
BTW, I am using the Spherical Law of Cosines for distance calculations
where I need them.

[Kieran Huggins]

An interesting idea I saw a friend implement just yesterday is using geohashes to both store & find nearby points.

http://en.wikipedia.org/wiki/Geohash

Geohashes are numerically close when they're near one another, so finding all points within a certain range is as easy as either setting a min & max in a database, or matching a common string prefix.

There are edge cases near the equator where this approach fails, and it also typically requires some post-select shaving to get rid of fringe results, but in general I really like it. If our app didn't necessitate a kdtree c implementation, we'd probably be using geohashes.

Finding proximity in MySQL is possible, though the queries are a pain the ass to write & it can get quite slow for larger datasets. If you're interested in this approach anyway take a look at http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html Postgres has a more convenient API for queries... but it's postgres :-/ http://postgis.refractions.net/

Cheers,
Kieran

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

[Michal Migurski]

Geohashes are a bit tricky, like any space-filling curve. When geohashes are numerically close, then points are definitely near each other. The inverse is not always true: when points are nearby, the geohashes are not necessarily numerically close. You mention the equator, which is the most obvious edge case, but there are many such "little equators" in the geohash space.

There's a picture here which shows where the discontinuities might appear, as well as a strategy for finding points in a box:
http://en.wikipedia.org/wiki/Z-order_(curve)

I've had the best experiences with PostGIS for this sort of thing. Their underlying index is, I think, the R-Tree, which does not suck:
http://en.wikipedia.org/wiki/R-Tree

-mike.

On Mar 10, 2010, at 9:26 AM, Kieran Huggins wrote:

> An interesting idea I saw a friend implement just yesterday is using geohashes to both store & find nearby points.
>
> http://en.wikipedia.org/wiki/Geohash
>
> Geohashes are numerically close when they're near one another, so finding all points within a certain range is as easy as either setting a min & max in a database, or matching a common string prefix.
>
> There are edge cases near the equator where this approach fails, and it also typically requires some post-select shaving to get rid of fringe results, but in general I really like it. If our app didn't necessitate a kdtree c implementation, we'd probably be using geohashes.
>
> Finding proximity in MySQL is possible, though the queries are a pain the ass to write & it can get quite slow for larger datasets. If you're interested in this approach anyway take a look at http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html Postgres has a more convenient API for queries... but it's postgres :-/ http://postgis.refractions.net/
>
> Cheers,
> Kieran
>
> On Wed, Mar 10, 2010 at 2:03 AM, Joa <joachim....@gmail.com> wrote:

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

----------------------------------------------------------------
michal migurski- mi...@stamen.com
415.558.1610

[Kieran Huggins]

@Michael: You're exactly right, which is why you need to trim the excess results after (if needed).

The geohashing steps (for reference) would be:

# determine your radius

# find the bounding box of your circle

# find the common geohash prefix for the bounding box & select on that

# reject all values whose distance form the origin is greater than the original radius

Geohashing is certainly not a complete solution for finding nearest points, but it can seriously short-list results to an iteration-friendly size.

If you have the chops, I'd definitely suggest using a more efficient library (trees are nice) or a complete solution provided by your data-store.

Cheers,
K

[Paul Trenkler]

SQLite can support R-trees too (if compiled with the appropriate
option):
http://www.sqlite.org/rtree.html
Personally I'm using it as an in-memory database table from a C++
routing engine

Paul

[NLambert]

I like this thread because it shines some light on how trip planning is coded. Your guys are great for sharing.

--

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

--
Regards,

[Nicholas Bergson-Shilcock]

Excerpts from NLambert's message of Wed Mar 10 15:47:43 -0500 2010:

> I like this thread because it shines some light on how trip planning is
> coded. Your guys are great for sharing.

If you're interested in learning more about how trip planning is coded, you
should check out the OpenTripPlanner project: http://opentripplanner.org/

All of the code is released under the LGPL, so you can read it and see exactly
how it works :) (Our mailing list also has a decent amount of discussion of
trip planning algorithms/problems.)

/end semi-shameless plug

-Nick

>
> On Wed, Mar 10, 2010 at 3:20 PM, Paul Trenkler <pal...@gmail.com> wrote:
>
> > SQLite can support R-trees too (if compiled with the appropriate
> > option):
> > http://www.sqlite.org/rtree.html
> > Personally I'm using it as an in-memory database table from a C++
> > routing engine
> >
> > Paul
> >
> > On Mar 10, 8:33 pm, Michal Migurski <m...@stamen.com> wrote:
> > > I've had the best experiences with PostGIS for this sort of thing. Their
> > underlying index is, I think, the R-Tree, which does not suck:
> > > http://en.wikipedia.org/wiki/R-Tree
> > >
> > > -mike.
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Transit Developers" group.
> > To post to this group, send email to transit-d...@googlegroups.com.
> > To unsubscribe from this group, send email to

> > transit-develop...@googlegroups.com<transit-developers%2Bunsu...@googlegroups.com>