Isochrones with Tinfour and openstreetmap

[danrosher]

Hi,

I'd like to create performant Isochrones from an openstreetmap PBF.

I've looked com.graphhopper.isochrone.algorithm.JTSTriangulator
[https://github.com/graphhopper/graphhopper core/src/main/java/com/graphhopper/isochrone/algorithm/JTSTriangulator.java]
which internally uses ConformingDelaunayTriangulator from org.locationtech.jts.triangulate.ConformingDelaunayTriangulator but the performance for isochrones for 1hr take around 2mins

Being completely new to this topic, I was wondering how easily this can be achieved with Tinfour, it seems it might be a more performant algorithm.

Kind regards,
Dan

[gwlucastrig]

I will try to give you as useful an answer as possible. So I will describe Tinfour "warts and all".

By isochrones, I assume you are talking about producing some kind of contour map representation. There is some discussion on how Tinfour does contouring from a Delaunay Triangulation at Using the Tinfour Contouring API.

One thing about Tinfour is that it deals strictly with Euclidean distances. So in terms of an isochrone, it would have only a limited ability to deal with differences in travel times on a road network (where path-of-travel is restricted to roads and speed is non-uniform).

The thing that Tinfour is good at is dealing with point data and constraints. A data set containing a few million points should be processed in less than 5 seconds. Above about 10 million sample points, processing slows down a bit. The largest data set I've tested (Lake Victoria soundings) had 17 million sample points and required about 30 seconds to process.

Are you thinking of doing a Voronoi diagram? Tinfour has a Voronoi module. But it's not the focus of the project and I would think that other libraries might do a more efficient job with the Voronoi.

Finally, I have never written code to access a PBF file. So that might be a sticking point. To access PBF files, some level of additional integration using other API's would be necessary. I might be able to help you with that, but this is a "nights and weekends" project for me, and my availability is limited.

Your project sounds quite interesting. Whether you decide to use Tinfour or some other solution, I would be interested in hearing more about what you're working on.

[danrosher]

Hi Gary,

The project is to produce isochrones in distance (or time) for various profiles available from the PBF e.g. car, bike,walk and then use the isochrone polygon to filter results in a search engine, namely Solr. Solr provides spatial filtering by polygons. The final result would need to be a WKT POLYGON without holes. The locationtech jts solution ( https://github.com/locationtech ) would be too slow, I'm looking to create (and cache) isochrones for e.g. car,bike,walk for say 20min,30min,45min,1hr and also 10mi 20mi 30mi etc for potentially all 1.6M UK postcodes (and the 50K towns/villages), or at least 'snap' the query location to point on a 100m square grid of the UK, something like that.

With the 1hr 'car' isochrone for example, the library I'm using, graphhopper, produces 2.6M datapoints from the PBF within range from an arbitrary query point. I could convert the lat/lon into x,y using a mercator projection before using Tinfour to determine the contour polygon? then proceed something like:

List vertices = // convert PBF datapoints to x,y -> Vertex(x,y,null) ?
IncrementalTin tin = new IncrementalTin(1.0f);
tin.add(vertices, null);

// ... and probably use smoothing to reduce final dataset

and on the way out convert the x,y back to lat/lon again?

Thanks for your assistance on this.

Kind regards,
Dan

[gwlucastrig]

2.6 million data points is easy.

Problems with a geometry basis always work better with an isotropic (Cartesian) coordinate system than with lat/lon. Since you're in the UK, a fairly high latitude, you might want to consider some projected coordinate system other than Mercator (which is conformant in terms of angle, but not so hot in terms of distance). But you can always treat that as a downstream refinement and focus on what you've got for right now.

Tinfour has some support utilities to read text files in the form of comma-separated or tab-separated value files. So if you could output your points as a text file (comma or tab separated values), they can be dragged-and-dropped into the Tinfour Viewer demonstration program for visual inspection.

Also, if you put text files somewhere I can download and view them, I could take a look at the data and perhaps make better suggestions.

In terms of polygons without holes, that's pretty easy. The contouring API has the idea of "nesting" polygons that keeps track of which are inside which. Alternately, you could just produce contours for each interval with separate runs of the contouring logic.

You mentioned the specification of constraints. What kind of constraints would you have?

Finally, I'm surprised that the Locationtech stuff is running so slow because, in general, those guys do a pretty good job of things. On the other hand, the Delaunay is the sole focus of my project, so it makes sense that Tinfour would have an unusually fast TIN constructor.

[gwlucastrig]

Also, if you want to give me a text file with lat,lon rather than x,y, I can handle that.