New vector isochrones generation (version 2)

[Laurent GRÉGOIRE]

Hi again,

To try to solve the various small issues I had with the previous version
of the isochrone generation (namely the slow sampling using a spatial
index and the problem of interpolating with infinite values), here is
the result of a new method, which I may call "accumulative grid sampling".

Basically it works as the following:

1) compute the SPT, as before, clamping the search to the max z cutoff.
2) for each edge geometry in the resulting SPT, take a sample at the two
ends and eventually at evenly-spaced intermediate points if the geometry
is longer than a certain threshold (currently d0/2, d0 being the grid
size). For each sample, find the 4 enclosing grid sample points and
accumulate for each of them a triplet (w, tw, d). See below the details
of this.
3) close our samples grid by adding new samples on the border.
4) compute the set of rings (exactly as in the previous method but
without iterative sampling) to build the polygons. z0 plane intersection
detection and interpolation is detailed below. See isochrone_3.jpg for
an example or results.

For each sample on the grid, we keep w, tw and d value (a multi-valued z
function for the generic isoline-builder class):

- d is the minimum distance between any sample point "real" location and
the sample "grid" location: d=min({di}).
- w is the accumulated weight factor for each sample: w=sum({wi}). In a
first trial I used a gaussian bell function of d, with d0 as a standard
deviation and 0 as mean. To make it faster to compute I now use a
simpler inverse square wi=1/(di+d0)^2, without significant changes in
the results.
- tw is the weighted sum of ti: tw=sum({ti.wi})

See sampling_points.jpg and sampling_grid.jpg showing the sampled points
and the resulting grid.

For intersection detection:
- if d > dmax, then z=+inf
- otherwise z=tw/w
- We have an intersection if zA<t0<=zB or zB<t0<=zA.

For the linear interpolation on an edge [AB], in case of intersection:
- if dA >= dmax OR dB >= dmax (dmax is the max off-road distance), we
linearly interpolate based on d only;
- otherwise we interpolate based on tw/w.

The advantages of this method compared to the previous one are:
- Faster. Since we do not have to find the vertex of any point we do not
use a spatial index anymore. Finding the grid point knowing the sample
coordinates is direct and really fast. Also the sampling grid uses
simple data access (int indexing, custom-made sparse matrix
implementation, direct link to neighbors) to speed up the computation.
We do not use any Maps or Sets anymore, and minimize temporary object
creation.
- Better off-road edge shapes (see attached borders.jpg) thanks to the
distance interpolation. You can see for example on the river the isoline
edges follow more or less the shape of the nearest roads.
- Should handle large and sparse SPT. If the SPT path have many small
island around a set of stations in a large area, the computation time is
only dependent on the SPT size itself and the isochrone rings
perimeters. Having a SPT with many large non-covered area (should) not
be an issue.
- The isoline generation class is simpler (no iterative process).
- Faster to compute many isochrones. Since we sample the grid only once,
and the isochrone building is really fast (3 isochrone building takes
approx 3 times less than sampling), computing many isochrones in one
request is way faster than before.

The drawbacks:
- The max off-road distance (dmax) can't be much smaller or larger than
the grid size (d0). Theorically it could be larger, but we need to add
more sample to close the set in step 3). The ratio between the two has
an impact on the resulting shape.
- The resulting shape is somehow dependent on the grid size. This make
sense of course, since the smaller the grid the more precise it gets,
but due to the limited grid sampling we have small edges appearing or
diseappearing depending on d0 and location of sampling. This is also due
to the averaging (tw is the weighted average from all samples in the
average). I tried to keep only the nearest value (t=ti if d=dmin) but
this does not seems to have a big impact. In urban area, best results
are for grid size 100m to 200m.
- A point that fall initially in the isochrone area in the SPT sample
could be outside the computed area, again due to this sampling. I did
not investigated this a lot, but this could be interesting to compare
various results to check for coherency.

For speed, the attached output takes ~ 400 ms to compute (~300ms for
sampling and ~100 ms for the 3 isolines), on top of ~ 250 ms for the
SPT, with a grid size of 100m x 100m and a SPT consisting of 160k
samples. For the same grid size, number of isochrone and area, I think
this is approx. 3 to 5 times faster than the previous method.

As usual, if you have any comments...

HTH,

--Laurent

[Laurent GRÉGOIRE]

(cc'd OTP-dev mailing list as this can help others too)

On 10/10/2013 19:01, Adrien Pavillet wrote:
> is the api you use the same that the old one ?
> ex : /opentripplanner-api-webapp/ws/iso?batch=true&...

No there is a new URL: /otp-rest-servlet/ws/isochrone

Only mandatory parameters are:
- origin
- cutoffSec (can be specified multiple times)

Optional parameters:
- routerId (for multiple graph)
- date, time, maxWalkDistance, etc... (same as all SPT queries)
- precisionMeters: grid size
- debug (warning: this will send back a huge amount of data)

There is no need to add the "batch" parameter (it will be set by default).

Returned data is an array of GeoJSON data.

Example:
/otp-rest-servlet/ws/isochrone?routerId=bordeaux&fromPlace=47.059,-0.880&date=2013/10/01&time=12:00:00&maxWalkDistance=1000&mode=WALK,TRANSIT&cutoffSec=1800&cutoffSec=3600&precisionMeters=100

/!\ Disclaimer: this is experimental code and the API is subject to
changes :)

There is a small test client at /otp-analyst-client/isochrone.html. It's
temporary and crappy debug code so you have to modify the parameters in
the isochrone.js file. Only feature is to drag or click on the map to
locate the origin marker.

HTH,

--Laurent

[Adrien Pavillet]

Thanks i've figured it out it's because you use the new OTP directory system while i was still using the old one ;)

Adrien

2013/10/10 Laurent GRÉGOIRE <laurent....@gmail.com>

--
Adrien Pavillet

Twitter : @Pavillet

Linked In : http://fr.linkedin.com/in/pavillet

[Adrien Pavillet]

Hello Laurent,

Just wondering was this branch merged into OTP ?

Also do you know  a way to ignore date and time in isochrone : ie act as if transportation were always avalaible ?

Thanks 

Adrien

2013/10/10 Adrien Pavillet <adr...@pavillet.fr>

[Andrew Byrd]

Laurent provided pull requests for his isochrone code changes. I will try to get them into master today.

_Andrew


Adrien Pavillet <adr...@pavillet.fr> a écrit :

>--
>You received this message because you are subscribed to the Google
>Groups "OpenTripPlanner Developers" group.
>To unsubscribe from this group and stop receiving emails from it, send
>an email to opentripplanner...@googlegroups.com.
>For more options, visit https://groups.google.com/groups/opt_out.

Andrew

--
Sent from a device without a keyboard. Please excuse my brevity and any absurd auto-correct errors.
Andrew

--
Sent from a device without a keyboard. Please excuse my brevity and any absurd auto-correct errors.

[Andrew Byrd]

Laurent provided pull requests for his isochrone code changes. I will try to get them into master today.

_Andrew

Adrien Pavillet <adr...@pavillet.fr> a écrit :

Hello Laurent,

[Laurent GRÉGOIRE]

Hello Adrien,

On 10/12/2013 16:14, Adrien Pavillet wrote:
> Just wondering was this branch merged into OTP ?

See Andrew answer, a pull request is pending.

> Also do you know a way to ignore date and time in isochrone : ie act as
> if transportation were always avalaible ?

That is not possible at the moment, isochrone generation rely on the OTP
path finding code (shortest path tree builder) to generate the data,
which need precise date/time information.

Adding this kind of functionality could be nice for isochrone generation
indeed, but that would be (and need to be from an architecture point of
view) quite independent from the isochrone generation itself.

A tricky point would be to define what this means exactly (weighted
average, no waiting time/best trip, etc...), if that represents reality
and how complex it would be to implement it. However for most
transportation networks an "average" can be approximated using a certain
representative date/time (for example the following Monday at 14:00).

HTH,

--Laurent

[Andrew Byrd]

On 12/10/2013 05:39 PM, Laurent GR�GOIRE wrote:
>> Also do you know a way to ignore date and time in isochrone : ie act as
>> if transportation were always avalaible ?
>
> That is not possible at the moment, isochrone generation rely on the OTP
> path finding code (shortest path tree builder) to generate the data,
> which need precise date/time information.

I just wanted to point out the
org.opentripplanner.api.ws.analyst.SimpleIsochrone class, which serves
the particular purpose of making isochrones with little regard to time
of day in places with poor OSM data.

It produces many shortest path trees at various times throughout the day
and for each point, it uses the shortest travel time from that set of
searches.

This might be a viable approach for your problem.

-Andrew