Mapping public transport stops in OSM is a complex and hotly debated topic. Requirements from different data consumers like individuals, transport agencies, routing apps and renderers meet a range of still evolving mapping standards and conventions. In the talk, on the one hand, we give an introduction to the public transport stop analysis (PTSA) project [1] for visualizing public transport mapping habits around the world and for pointing mappers to inconsistent and possibly erronous data. The data aggregated and visualized by PTSA may inspire further evolution of OSM's public transport mapping schemes. At least it enables local mappers to adapt to their local community's preferred mapping scheme and to improve data quality. On the other hand, we take a look at some algorithmic problems behind the scenes, which motivated the development of a new algorithm for efficient distance measurements with guaranteed and adjustable minimum accuracy. Published source code and documentation may help similar projects to scale ideas and code from a local level to the whole OSM planet.

Mapping of public transport stops in OSM evolved from simple nodes to complex combinations of nodes, ways and areas. Conventions like the classical (aka PTv1) and the PTv2 scheme for public transport mapping do not allow for a clear and simple grouping of all relevant objects. The smallest group available is a stop area, which usually comprises all OSM objects of several nearby or otherwise related stops. Renderers and similar data consumers somehow have to figure out whether multiple objects, say a node and a nearby way (platform), represent one and the same stop or whether there are two or maybe even more stops to render. PTSA provides such stop-level grouping by analyzing geometry and tags of all OSM objects related to public transport. PTSA thus not only allows to visualize different mapping styles around the world, but also yields lots of hints on inconsistent data. Analyzing data aggregated by PTSA would be worth a study on its own from the social point of view. Where did mappers find a (local) consensus on how to map public transport and where not? Which regions tend to complex mapping schemes, which to simple ones? Where the classical PTv1 scheme is preferred? Where did mappers switch to the more recent PTv2 scheme?

But the talk's focus is on the technique behind the scenes. Analyzing geometry of public transport stops requires lots of distance measurements in the range for 1 to 500 meters. How to do this efficiently, but sufficiently accurate with guaranteed minimum accuracy? Accurate distance measurements on the WSG84 ellipsoid or even an a sphere are based on computationally expensive trigonometric functions. We present a new method to solve this problem without trigonometric functions, while maintaining a prescribed minimum accuracy: divide the world's landmass into regions of prescribed maximum diameter, then for each region find an optimal map projection and use Euclidean distances on the projected map.

Dividing the OSM planet into regions small enough to allow for low distortion map projections is a problem of interest on its own. But it's not as simple as one might think. We have to take care of not cutting through an area of interest (public transport stops). Cutting along admistrative boundaries solves this problem. Corresponding data sets for different maximum diameters have been published by the author along with the code to produce subdivisions of the planet for arbitrary maximum diameters, see [2] and [3].

For each region finding the optimal (that is, lowest distortion) map projection is another problem of general interest. If we restrict attention to azimuthal equidistant projections, then optimal mapping parameters are given by center and radius of the region's smallest enclosing circle. To compute the smallest enclosing circle of a region we have to answer two questions: How can we do this? And: how fast can we do this? Computations have to be done on the sphere, not in the plane, to get optimal mapping parameters. On the sphere there only exist algorithms with quadratic time complexity or other shortcommings. An administrative boundary in OSM may consist of more than 100000 nodes (e.g. France and Germany). So the algorithm's time complexity really matters. In the plane there's Welzl's linear time algorithm for smallest enclosing circles [4]. We present a new (hemi-)spherical version of Welzl's algorithm, which maintains linear time complexity and resolves some of the shortcommings of other algorithms, see [5]. A ready to use implementation is available on PyPI [6].

The combination of small regions and the optimal projection parameters obtained from our new Welzl-type algorithm allows for Euclidean distance measurements on the map, while still maintaining a prescribed accuracy. Accuracy can by expressed by the deviation between Euclidean distances on the projected map and geodetic distances on the WSG84 ellipsoid. Given a desired accuracy we show how to compute the corresponding maximum diameter for regions in the subdivision of the OSM planet.