<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Frédéric Rodrigo on Medium]]></title>
        <description><![CDATA[Stories by Frédéric Rodrigo on Medium]]></description>
        <link>https://medium.com/@frederic.rodrigo?source=rss-92b83f95ef5c------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*O6-29F6YlWg9YaOAyioI4Q.png</url>
            <title>Stories by Frédéric Rodrigo on Medium</title>
            <link>https://medium.com/@frederic.rodrigo?source=rss-92b83f95ef5c------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 10:27:31 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@frederic.rodrigo/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[OSM Logical History — From technical diffs to reconstructed semantic object history]]></title>
            <link>https://medium.com/@frederic.rodrigo/osm-logical-history-from-technical-diffs-to-reconstructed-semantic-object-history-eea089a6d72e?source=rss-92b83f95ef5c------2</link>
            <guid isPermaLink="false">https://medium.com/p/eea089a6d72e</guid>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[openstreetmap]]></category>
            <category><![CDATA[gis]]></category>
            <category><![CDATA[conflation]]></category>
            <dc:creator><![CDATA[Frédéric Rodrigo]]></dc:creator>
            <pubDate>Tue, 21 Oct 2025 10:10:36 GMT</pubDate>
            <atom:updated>2025-10-21T10:10:36.671Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>OSM Logical History — From technical diffs to reconstructed semantic object history</strong></h3><p>This article is an English translation of my own article in French from <a href="https://tech.teritorio.fr/fr/blog-technique/OSM-Logical-History-Depuis-les-diff-techniques-OpenStreetMap-a-la-reconstruction-de-l-historique-semantique-des-objets-fr.html">Tetiroio Tech blog</a>.</p><h3><strong>Objective</strong></h3><p>The objective is to review the changes between two versions of OSM data in order to evaluate the quality of these changes and, if necessary, correct the data in OSM.</p><p>To do this, it is necessary to use a data differential between the two versions. The OSM differential format (“diff”) is relatively technical and low-level in terms of data structure. It is therefore difficult for humans to interpret and read. Here, we seek to establish a semantic, rather than technical, differential between the data before and after modification. We are only interested in this subject.</p><h4><strong>OSM Changesets and Diffs Problem</strong></h4><p>In OSM, changes are contributed in groups of modifications called “Changesets.” These are “Diffs”: data differentials with a set of metadata (date, contributor nickname, etc.). This differential simply contains the modified objects in their new versions.</p><p>Objects in OSM consist of free key-value attributes carrying semantics, as well as geometry (carried directly by points, or indirectly by segmented lines and relations). Objects also have meta-attributes, such as contributor nickname. These objects are versioned as they are modified, with version and deletion (“soft delete”) meta-attributes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/372/1*9ETWomQXOjkYvLcaartD7A.png" /><figcaption>Illustration of OSM object with versions, multiple versions stacked. <a href="https://www.openstreetmap.org/node/6506410029/history](OSM-Logical-History-From-technical-diffs-to-reconstructed-semantic-object-history/01-osm-history.png)">https://www.openstreetmap.org/node/6506410029/history</a></figcaption></figure><p>There is no requirement for semantic consistency in changesets. They can involve modifications to objects that are not related thematically or geographically. A changeset could add a house in Brazil and modify the shape of a road in Mongolia (although this is not recommended practice). Furthermore, unlike relational databases a changeset is not transactional. A changeset is a working session that can extend over time. It can even contain several versions of the same object.</p><p>This history structure of OSM objects and the nature of changesets present challenges for data analysis¹.</p><p>A changeset is therefore a group of changes spread out geographically, semantically, and temporally.</p><h4><strong>Semantic issues raised by the structure of OSM data</strong></h4><p>The OSM data model is very simple and very open. All objects have attributes in the form of “free” key-value pairs, tied into a consensus of usage. These attributes define the semantics of the objects. There is therefore no equivalence with the thematic layers found in the GIS world. Objects can even have several semantics at once, and the number of semantic aspects can even depend from the viewpoint of the observer. For example, an object can be a building, a business, and an address all at once (which is not recommended practice, but such objects exist in large numbers).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/337/1*zzq_Q_lMyYjgUFbXcG-9Cg.png" /><figcaption>Example of an OSM object with multiple semantics. <a href="https://www.openstreetmap.org/way/156152829](OSM-Logical-History-From-technical-diffs-to-reconstructed-semantic-object-history/02-osm-multi-semantic.png)">https://www.openstreetmap.org/way/156152829</a></figcaption></figure><p>There are also three types of objects that are not defined by attributes: points, segmented lines, and relations. Depending on the level of detail of the mapping and the intrinsic complexity of the object, an object can be modeled according to one of these three types. A segmented line does not have its own geometry, but references points. Note that in OSM, a polygon is one or more segmented lines in a loop, whose surface nature is defined only by the interpretation of attributes.</p><p>This modeling flexibility, while advantageous for contributors, complicates data consistency analysis².</p><p>Although each object has an identifier, a version number, and a history in its meta-attributes, this history is primarily technical. For example, a school may initially be contributed as a point, which may be deleted before being re-mapped as a polygon. This is reflected in the history by the deletion of the point-type school object with a first technical identifier, followed by the creation of a segmented line-type school object with another technical identifier. There is therefore no link in the history between the two objects, although semantically they are the same school.</p><p>To take another, more complex example, a road can be split into several segments to carry different attributes, such as the maximum speed limit. One of the segments retains the identifier and link to the history, while the other segments are new objects with no link, either technical or historical.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/354/1*rjh93X_7VFXwDS1u91S_vw.png" /><figcaption>Splitting a segment, creating two new objects.</figcaption></figure><p>It should be noted that objects may have “business” identifier or reference attributes, such as the reference number of a road shared by several sections or the unique reference of a fire hydrant.</p><p>The technical history of objects therefore does not allow for a semantic link to be made between objects before and after modification. An object can even retain its identifier and history, while changing all of its attributes and therefore its semantics.</p><h4><strong>Require to work at the semantic level</strong></h4><p>As identified by Padilla-Ruiz et al. (2017)³ in their classification of digital map conflation processes. To limit the analysis to actual changes in OSM data, it is necessary to process the data at the semantic level.</p><p>In fact, deleting a fire station to transform it from a node object type to a polygon is equivalent to a deletion and creation at the data model level. But at the semantic level, this should be interpreted as a simple geometry modification.</p><p>In addition, objects can be modified while remaining present in another form. For example, an object with building, business, and address attributes can be split into three separate objects, whose overall semantics remain equivalent to those of the original object. Depending on the quality and change monitoring rules that one wishes to follow, this can be considered a simple modification of geometry, or even not considered a change as long as the location remains the same.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/799/1*OUucIgSEMcyCmGQLEMcSCw.png" /><figcaption>Semantic segmentation of an object.</figcaption></figure><h3><strong>Context of the need</strong></h3><p>The approach detailed here derives from a need of the <a href="https://github.com/teritorio/clearance">Clearance</a> project. Clearance is a tool for synchronizing a copy of an OSM database. As its name suggests, data synchronization is subject to control. This synchronization is not done uniformly, both geographically and temporally. Only changes that locally (geographically) meet quality criteria are synchronized. Changes are not processed chronologically, but by rearranging the modified objects into “local” groups. The aim is to ensure the local consistency of the synchronized data. These groups of local changes are called “LoCha” (Mohapatra, 2019)⁴.</p><p>This is where the need to analyze the difference between data already synchronized in the OSM copy and new data coming in from contributions made to OSM comes in. The data to be synchronized is put into quarantine while its quality is validated and corrected. If this data meets the quality criteria locally (geographically), it is integrated into the synchronized copy. Otherwise, the data in quarantine is updated (still in the quarantined copy) until it meets the quality criteria. This approach to reorganizing changes by LoCha allows problematic areas to be put on hold while continuing to update data elsewhere.</p><p>To evaluate the quality criteria, it is easier to do so on a high-level semantic representation rather than at the technical format level of OSM diffs. It is for this task that we need this semantic differential between two versions of OSM data.</p><p>The concepts and implementations detailed here are intended to be more generic than the scope for which we developed them.</p><p>Due to the issues described above, OSM technical identifiers are neither permanent nor reliable. Furthermore, reconstructing the semantic history of objects could contribute to discussions on the topic of permanent identifiers. (https://giswiki.hsr.ch/Permanent_ID_for_OSM <a href="https://wiki.openstreetmap.org/wiki/Permanent_ID">https://wiki.openstreetmap.org/wiki/Permanent_ID</a> <a href="https://wiki.openstreetmap.org/wiki/Persistent_Place_Identifier">https://wiki.openstreetmap.org/wiki/Persistent_Place_Identifier</a> )</p><h3><strong>Selection and preparation of OSM data</strong></h3><p>The data to be compared is in the OSM data schema. It is a relational structure, not geometric, nor organized by thematic layers, and not particularly suitable for processing. It is necessary to calculate the complete geometries of the objects and, for example, determine whether a segmented line in loop is a polygon or not.</p><p>On the other hand, objects that do not change are excluded from the analysis because they have no history of modification.</p><h3><strong>Conflation</strong></h3><p>Conflation consists of finding objects whose identity appears to correspond between the before and after versions. This also makes it possible to identify objects, in the semantic sense, that have been newly created or deleted. This comparison is made on the basis of both the semantics of OSM tags and geometry.</p><p>This conflation is performed iteratively on a set of criteria.</p><p>The approach described here is the one currently implemented. Improvements are possible.</p><h4><strong>Reconciliation by distance</strong></h4><p>For all objects, a distance matrix is calculated between all OSM objects in the before version and those in the after version. This is not a geometric distance, but a distance measuring semantic and spatial similarity.</p><p>The object before and the object after with the smallest distance, and less than a maximum distance, are considered to be in correspondence.</p><p>These objects are removed from the matrix and the process is repeated until there are no more objects in correspondence.</p><p>The iterative approach is similar to Volz, Steffen. (2006)⁵. This approach is not without drawbacks. In the future, rather than iterating, we could look to minimize the sum of the distances between paired objects.</p><h4><strong>Concept of distance</strong></h4><p>The distance used for matching is not only the Euclidean geometric distance, but is based on the semantics of the tags and geometric shapes.</p><p>As a result, the matrix is not complete; it is only defined for objects that are comparable to each other.</p><h4><strong>Geometric distance</strong></h4><p>For objects without geometry, such as certain OSM relations, or invalid geometries, the distance is undefined. These objects are therefore not matchable.</p><p>Identical geometries have a distance of 0.</p><p>For points, the Euclidean distance is interpolated non-linearly in the interval [0; 1]. The idea is to differentiate small distances more than large ones. The value 1 is obtained for the maximum permitted distance (200 m). Beyond this, the distance is no longer defined, and therefore the approximation is impossible.</p><p>For other types of geometries, if there is no intersection, we use the same distance formula as for points, but in the interval [0.5; 1]. A penalty of 0.5 is introduced for geometries without intersection.</p><p>In the case of an intersection, if one of the two geometries is completely included in the other, the distance is then evaluated as 0 (see below for the reason with partial matches). Otherwise, the ratio between the size of the intersection and the size of the union is calculated (value between 0 and 1), in other words that the Jaccard distance, which is a proven method for performing conflations (Li &amp; Goodchild, 2011). This “size” can be either the length or the area, depending on the case.</p><p>These calculations are performed using buffers to handle cases such as quasi-intersections or quasi-inclusions.</p><p>This geometric distance has a value between 0 and 1.</p><h4>Reconciliation by tags</h4><p>OSM tags are free-text key-value pairs. However, not all tags have the same role or importance and should be weighted as proposed by Samal et al. (2004)⁶.</p><h4>Reconciliation by references</h4><p>The first criterion for finding objects is to use their business references. In OSM, there may be several reference tags.</p><p>If in the before and after versions we find a single OSM object with the same set of references, then we consider that a match and that the distance between geometry on these objects is 0.</p><p>The reference tags used are the “ref” tag and those beginning with “ref:”.</p><p>In the future, we could handle cases where several OSM objects share the same references, as is the case for roads.</p><h4><strong>Semantic distance between tags</strong></h4><ul><li><strong>Concept hierarchy tags</strong>: in OSM, there is a nomenclature of tags defining the nature of objects. The keys and values are codified. For example, “highway=motorway” to indicate that a road is a motorway; or “tourism=information” + “information=board” + “board_type=history” for a tourist information board about the history of a place.</li><li><strong>Additional attribute tags</strong> with free or fixed values, such as “name=*” for the name, or “wheelchair=yes” to indicate that the object is wheelchair accessible.</li></ul><p>To establish a distance between object tags, we will separate the tags into two subgroups: those defining a first-level hierarchical nature and the others.</p><p>Objects that do not share top-level hierarchical keys are considered non-comparable, and the semantic distance between them is not defined.</p><p>An object in OSM can have several top-level tags, for example “amenity=recycling” + “landuse=industrial”.</p><p>Among these top-level tags, there are two types of values:</p><ul><li>Those for which the value changes the nature (“amenity=recycling” or “amenity=driving_school”). Although the key is the same, the objects are not similar. The distance is defined as 1.</li><li>Those for which the value gives a level for a type of object (“highway=motorway,” “highway=unclassified”). The objects are of the same type and comparable to each other. The distance is defined as 0.5.</li></ul><p>If the keys and values are identical, the distance is 0. If the keys or values exist for only one of the two objects, the distance is 1.</p><p>The distance of the tags in this first subgroup is obtained by averaging the individual distances of the tags.</p><p>For the second subgroup of additional tags, for each identical key, the Levenshtein distance between the values (number of different characters between the two values) is calculated, normalized between 0 and 1. Then we average all the tags in this second group.</p><p>Finally, the distances of the two subgroups are added together and divided by two to obtain a semantic distance of the tags between 0 and 1.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d221299af2f3244a80ec35e1e4593127/href">https://medium.com/media/d221299af2f3244a80ec35e1e4593127/href</a></iframe><p>This approach of weighting attributes according to their semantic importance is inspired by the work of McKenzie et al (2014) ⁷ on matching user-generated points of interest. For the second subgroup, the nature of the tags may be used to calculate the distance rather than using a Levenshtein distance that is completely unrelated to the semantics of the content.</p><h4><strong>Partial matching</strong></h4><p>When a before object is a geometric sub-part of the after object, we will cut the geometry to perform only a partial match, as proposed by Adams et al (2015)⁸ for roadways.</p><p>This case occurs frequently with roads that can be segmented to support different attributes, such as speed changes.</p><p>The remaining part of the object will be reintroduced into the distance matrix and will be available for new matches.</p><p>We also perform partial tag matching in cases where there are multiple top-level tags. After partial matching of the top-level tags, we return the object with the remaining top-level tags to the matrix. This occurs when an OSM object concept is moved. For example, we move the `amenity=school` tag from a building to a larger area that includes an outdoor. The building and the school concepts remain, but separately.</p><p>The current implementation handles the case of partial tag matching or geometric matching, but not both at the same time.</p><h4><strong>Simplify</strong></h4><p>After these matches, there may still be complete or partial objects remaining. In order to improve interpretation, the result is simplified. The remaining partial objects are merged back with the original OSM objects that have already been matched. This is particularly the case for objects whose geometry has been enlarged and not split into several objects.</p><p>Objects may have changed semantics, and the objects before and after cannot be matched because they are different in nature. For example, a bank that has become a pizzeria. The semantic matching process will identify the deletion of a bank and the creation of a pizzeria, which is correct. However, these changes occur on the same OSM object and are not matched to anything. As a last resort, we will use the fact that the OSM technical identifier has not changed to match the objects anyway. Ultimately, it is indeed a bank that has become a pizzeria.</p><h4><strong>Implementation</strong></h4><p>This approach is implemented in the project <a href="https://github.com/teritorio/openstreetmap-logical-history">OpenStreetMap Logical History</a>.</p><p>The project also provides an API that allows you to calculate the semantic history of an area between two dates by retrieving OSM data from an Overpass or Ohsome instance. The result can be viewed here <a href="https://teritorio.github.io/openstreetmap-logical-history-component/">OpenStreetMap Logical History</a>.</p><h4><strong>Conclusion</strong></h4><p>This initial implementation of merging between two versions of OSM needs improvement, but it already provides better structuring of information and thus facilitates the review of changes by offering a history based on semantics, where objects do not have only one predecessor or successor in the history.</p><p>In addition to the demonstration project, this implementation is already in place in the Clearance project, where it helps to detect changes that actually require human review.</p><p>This approach brings conflation to the OSM data history by recreating a semantic history rather than a technical history.</p><p>The approach outlined here opens up possibilities for offering an alternative to the need for unique identifiers and provides a basis for better evaluating changes in OSM data over time.</p><p>¹: Girres, Jean-François &amp; Touya, Guillaume. (2010). Quality Assessment of the French OpenStreetMap Dataset. T. GIS. 14. 435–459. 10.1111/j.1467–9671.2010.01203.x.</p><p>²: Fan, Hongchao &amp; Zipf, Alexander &amp; Fu, Qing &amp; Neis, Pascal. (2014). Quality assessment for building footprints data on OpenStreetMap. International Journal of Geographical Information Science. 28. 700–719. 10.1080/13658816.2013.867495.</p><p>³: Padilla-Ruiz, Marta &amp; Lopez-Vazquez, Carlos. (2017). Measuring conflation success. Revista Cartográfica. 41–64. 10.35424/rcarto.v0i94.341.</p><p>⁴: Mohapatra, Saurav (2019). MaRS: How Facebook keeps maps current and accurate. <a href="https://engineering.fb.com/2019/09/30/ml-applications/mars/">https://engineering.fb.com/2019/09/30/ml-applications/mars/</a></p><p>⁵: Volz, Steffen. (2006). An Iterative Approach for Matching Multiple Representations of Street Data. In: Hampe,M. (ed.); Sester,M. (ed.); Harrie, L. (ed.): Proceedings of the JOINT ISPRS Workshop on Multiple Representations and Interoperability of Spatial Data. Vol. XXXVI Part 2/W40, pp. 101–110. 36.</p><p>⁶: Samal, Ashok &amp; Seth, Sharad &amp; Cueto, Kevin. (2004). A feature-based approach to conflation of geospatial sources. International Journal of Geographical Information Science. 18. 459–489. 10.1080/13658810410001658076.</p><p>⁷: McKenzie, Grant &amp; Janowicz, Krzystof &amp; Adams, Benjamin. (2014). A weighted multi-attribute method for matching user-generated Points of Interest. Cartography and Geographic Information Science. 41. 125–137. 10.1080/15230406.2014.880327.</p><p>⁸: Adams, Benjamin &amp; McKenzie, Grant &amp; Gahegan, Mark. (2015). Frankenplace: Interactive Thematic Mapping for Ad Hoc Exploratory Search. 10.1145/2736277.2741137.</p><p>⁹: Li, Linna &amp; Goodchild, Michael. (2011). An optimisation model for linear feature matching in geographical data conflation. International Journal of Image and Data Fusion. 2. 309–328. 10.1080/19479832.2011.577458.</p><p>¹⁰: Müslüm Hacar and Türkay Gökgöz (2019). A New, Score-Based Multi-Stage Matching Approach for Road Network Conflation in Different Road Patterns</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eea089a6d72e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[State of the art — OpenStreetMap extraction synchronization under quality constraints]]></title>
            <link>https://medium.com/@frederic.rodrigo/state-of-the-art-openstreetmap-extraction-synchronization-under-quality-constraints-3d46907c5151?source=rss-92b83f95ef5c------2</link>
            <guid isPermaLink="false">https://medium.com/p/3d46907c5151</guid>
            <category><![CDATA[open-data]]></category>
            <category><![CDATA[data-synchronization]]></category>
            <category><![CDATA[qa]]></category>
            <category><![CDATA[openstreetmap]]></category>
            <dc:creator><![CDATA[Frédéric Rodrigo]]></dc:creator>
            <pubDate>Wed, 04 Jan 2023 13:49:22 GMT</pubDate>
            <atom:updated>2023-01-04T13:49:22.187Z</atom:updated>
            <cc:license>https://creativecommons.org/licenses/by-sa/4.0/</cc:license>
            <content:encoded><![CDATA[<h3>State of the art — OpenStreetMap extraction synchronization under quality constraints</h3><p><em>We explore here the subject of synchronizing a copy of OpenStreetMap data while trying to ensure the quality of this copy. We study existing tools and strategies.</em></p><p><em>This article is an English translation of my own </em><a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/"><em>French article from Teritorio Blog</em></a><em>.</em></p><h3>Context</h3><p>OpenStreetMap is a collaborative map data project. The data is continuously updated by contributors. The nature of the contributors and their motivations are varied¹ ². The contributors are individuals, lobbyists (cycling, hiking…) or professionals from local authorities, small or large companies³ ⁴.</p><p>These actors contribute to OpenStreetMap as a digital commons to share knowledge of the territory and its dissemination. But also, with an often primary objective to reuse themselves the data they contribute to create and maintain with the rest of the community.</p><p>The issue of data quality is a recurring question. It concerns two aspects.</p><ol><li>Data from the OpenStreetMap common database or all modifications are taken directly into account, without prior validation. Tools for monitoring and validating data after the submission are available.</li><li>Data from OpenStreetMap extracted and then reused and disseminated by actors via other channels.</li></ol><p>Quality criteria can be global to the community or specific to actors, sub-communities or thematic.</p><p>Here we aim to ensure the quality of the second type: use and disseminate data.</p><p>The objective is not to guarantee quality in an absolute way, that would require a reference for comparison. If we use OpenStreetMap, it is because we do not have this reference or a satisfying one. OpenStreetMap is then the solution that has the best coverage, the best means of dissemination or the quickest update.</p><blockquote>In contrast to absolute quality, the objective is to guarantee the relative stability of quality. That is, to ensure that the quality remains stable or improves.</blockquote><h3>Existing solutions for addressing quality</h3><h4>Addressing quality a priori</h4><p>It is about controlling the “contributed” data before it is sent to the OpenStreetMap database.</p><p>Contributions to OpenStreetMap are made by an open set of tools that send changes to a common API. The API service does not perform any validation of the data changes themselves.</p><p>The data editing tools are based on the same data “schema” which is not formal. It can be seen as a customary schema⁵. These “customs” are not unified, although there is no shared formalism, these different tools have nuances⁶. Note, that these customs also have nuances according to the territories and the groups of contributors.</p><p>These varied uses of the schema(s) can only be amplified at the level of the validation of data prior to sending it to the OpenStreetMap API.</p><p>The tools have more or less validation rules, themselves more or less optional. However, JOSM, the most used editor, offers the most validation rules⁷. iD, the second most used editor, also provides another set of validation rules⁸.</p><p>Taking all of this into account, it is obvious that we cannot assume that OpenStreetMap’s data quality rules are respected, but only that they tend to be closer to customary usage.</p><h4>Addressing quality data quality a posteriori</h4><p>To improve the quality of the data in the OpenStreetMap database there are validation tools: global, thematic or territorial. They validate the current state of the database.</p><p>These validation tools also have the advantage of not being restricted to the current data area during contribution sessions. Indeed, the editing tools only validate the data on the working areas.</p><p>These validation tools report possible anomalies that contributors can take into account to improve the data.</p><p>There are mainly three tools of this kind that work in a similar way: Keep Right⁹, OSM Inspector¹⁰ and Osmose-QA¹¹. They analyze the data on a daily basis with rules (again, specific to each tool) and produce lists of reports that can be viewed on a map. All contributors can view and process these reports.</p><h4>Addressing the quality of changes a posteriori</h4><p>In addition to monitoring the current state of the OpenStreetMap database, there is at least one tool for monitoring changes made by contributors: OSMCha¹². Other minor tools exist, they are not detailed here, for example: osm-analytic-tracker¹³ and osmada¹⁴.</p><p>Contributions are sent to the OpenStreetMap API in work sessions called changesets. These changesets gather the modifications made by a contributor with a tool in a work session. Note that these changesets are not transactional change groups in the database meaning.</p><p>In fact, these changesets often have a form of consistency of their own, although this is not required. For example, a territorial consistency linked to a contribution session in the field, or a thematic consistency linked to a contribution session with the use of a quality reporting tool.</p><p>The use of rules for validating changes and the internal consistency of changesets allow potential quality problems to be reported.</p><p>Like other quality tools, contributors can take advantage of these reports to correct the data.</p><h4>An iterative approach</h4><p>Quality processing is therefore an iterative approach that consists of continuous improvement of existing data.</p><p>However, in parallel, other contributions are made without quality assurance.</p><p>It is therefore possible to imagine that on an ad hoc basis and within a thematic and/or territorial perimeter we can get closer to a given quality objective. However, this state is only local and will not remain so in the time.</p><h4>Quality data extraction strategy</h4><p>As a reminder, we want to extract, reuse and distribute quality data based on OpenStreetMap.</p><p>By extraction, we mean here a total or partial synchronized copy according to territorial and/or thematic breakdowns.</p><p>Quality criteria are not defined here, they are outside the approach of the method discussed here. The quality criteria are discussed below.</p><h4>Extraction and correction outside OpenStreetMap</h4><p>The simplest approach is to make an extraction. If these data do not correspond to the quality objectives, we can directly correct the extracted data.</p><p>This approach has the drawback of not reporting the corrections in OpenStreetMap. The rest of the community and ourselves will not benefit from it during the next extraction.</p><p>A solution is to make the same corrections in OpenStreetMap in parallel. This is obviously not a desirable approach.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/536/0*enVIC65T-_5038e0.png" /><figcaption>Figure 1: Uncontrolled contribution to OpenStreetMap. Uncontrolled extraction. Correction of the extraction.</figcaption></figure><h4>Extraction and correction iterations in OpenStreetMap</h4><p>The alternative is to make the corrections directly in OpenStreetMap and to perform the data extraction again.</p><p>The advantage is to make the corrections only once and to share them with the community. To be efficient, it is necessary to have the tools to make this extraction in an automated way and with short delays of taking into account the corrections.</p><p>This approach has the disadvantage of integrating data contributed at the same time outside of the quality criteria during the iterations. This has the following consequences:</p><ol><li>to require more iterations to converge towards the desired quality level;</li><li>incorporate enough “turbulence” to risk never reaching the quality criteria at a given time. Forcing either to finish the corrections directly in the data extracted from OpenStreetMap, or to lower the expected quality level.</li></ol><p>Neither of these approaches are desired.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/583/0*q29Gfc3_g-oIiRa9.png" /><figcaption>Figure 2: N iterations of correction in OpenStreetMap followed by extractions.</figcaption></figure><h4>Updating extractions</h4><p>Updates of these extractions can be done by reproducing the same process again. That is, by iterating on the OpenStreetMap data extraction until the quality criteria are met again.</p><p>These iteration loops can take time to make quality convergent. This implies that the time to perform these iterations, a new extraction cannot be done.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/721/0*bjpnLZbVHsAXDzdS.png" /><figcaption>Figure 3: M update iterations.</figcaption></figure><h4>Difference flow</h4><p>Contributions to the common OpenStreetMap database are made in continuous flow. The same is true for the replications of the database and the extractions that can be made from it. It is possible to update them by applying in continuous or delayed flow these same modifications.</p><h4>Continuous update of the extractions</h4><p>In order to maintain the quality criteria of the extraction, it is necessary to control that if after an update the quality criteria are no longer met, then it is not possible to apply this update.</p><p>It is then necessary to correct the data in OpenStreetMap so that the cumulative updates meet again the quality criteria.</p><p>This approach has the advantage of making updates automatic as long as the quality criteria are respected. Note that the same result could have been achieved by re-extraction. Updating by differential flow only reduces the amount of data to be validated and the processing time.</p><p>Once the updates no longer meet the quality criteria, it is necessary to intervene in OpenStreetMap to return to this state. Note that this method has the same drawbacks as the previous re-extraction approach. It only allows to reduce the delay between the extraction and the original, as long as the quality criteria are respected.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/583/0*6sUhTooJYs0Schlt.png" /><figcaption>Figure 4: Diff update of the extraction.</figcaption></figure><h4>A third way: partial update</h4><p>This approach consists in starting with OpenStreetMap data as is, or after a first quality improvement by the previous approach. The extraction is then updated with partial modifications, which once applied do not introduce a decrease in quality.</p><p>If updates do not meet the criteria, they are rejected and reported. The data must be corrected in OpenStreetMap and the accumulated partial updates can then be integrated when the quality is satisfactory again.</p><p>This ensures the invariant of stability or growth of the extracted data quality.</p><p>The advantage of this partial update is that any updates or corrections that can be made are integrated quickly and automatically. Data rejected for quality reasons can be processed asynchronously.</p><p>However, this approach poses problems of consistency of the extraction state with only partial updates.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/583/0*HrReVUzyZ-4cRnfZ.png" /><figcaption>Figure 5: Partial update of the extraction.</figcaption></figure><h3>OpenStreetMap data structure and exchange</h3><h4>Meta-scheme</h4><p>OpenStreetMap data is not structured like traditional map data. It is based on:</p><ul><li>the “nodes”, points;</li><li>the “ways”, broken lines;</li><li>the “relations”, groups of points, lines or groups;</li><li>the “tags”, free key-value pairs.</li></ul><p>There is no scheme in the classical sense for the definition of fields. This is a matter of customs.</p><h4>Filters and Overpass API</h4><p>The first way to filter data is through lists of tags: keys only, or key-values to keep or reject. Filters can also be based on the nature of the support (nodes, ways and relations).</p><p>Filters on the links between elements can then be used: topology, spatial relationship, semantic…</p><p>These filters can be performed by tools on binary files, in databases such as PostgreSQL+PostGis or by a language and an dedicated tool to OpenStreetMap data: Overpass API¹⁵.</p><h4>Diff</h4><p>OpenStreetMap data is distributed by export (“dump”) in a specific XML¹⁶ or PBF¹⁷ binary format. These formats are relational and not spatial.</p><p>Updates (“diff”) are distributed in an identical format. They contain only the modified objects. These updates are released by minutes, hours or days, depending on the provider. These updates are global or territorial.</p><p>These updates can be accumulated and combined: diff(a→b) + diff(b→c) = diff(a→c).</p><h4>Changeset</h4><p>Changesets are groups of changes, in the same format as diffs. A changeset is associated with a contribution session.</p><p>A changeset can be spread over time, modify the same object several times, modify objects contributed by other contributors in parallel to other changesets.</p><p>It is not possible to replay changesets in a unary way, they are not transactional, they cannot be accumulated and combined.</p><h3>Existing solutions</h3><h4>Change Tracking Solutions: OSMCha</h4><p>OSMCha¹⁸ is a free software tool for quality control of changes already contributed to OpenStreetMap. It is an a posteriori control.</p><p>Contributors can take of the reports and correct the data in OpenStreetMap.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/0*R15gf5Md6LFh1EKx.png" /><figcaption>Figure 6: Changes in time and space. Vertical lines, changes in versions of the same object over time. Addition in green, modification in orange, deletion in red. The groups are the changesets, without obligation of temporal or spatial coherence. Only the precedence of the versions of the objects is guaranteed.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/888/0*xqS1bbQHkdvN_UM_.png" /><figcaption>Figure 7: OSMCha. User interface for viewing changes reported.</figcaption></figure><p>OSMCha is not a data synchronization solution, but it does allow for post-processing control.</p><p>It offers however a change control open to the community. The validation is done collaboratively.</p><p>It is the history of changesets that is addressed. Changesets or objects may already be outdated at the time of manual control by a contributor.</p><p>Reports may be addressed by nobody.</p><h4>Synchronizations with IdeoMap, by Teritorio</h4><p>IdeoMap is Teritorio’s historical solution for synchronizing an OSM database extraction. This solution is internal to Teritorio and is not public.</p><p>IdeoMap allows you to configure a region and thematic data to replicate. These thematic are defined by OpenStreetMap tag filters.</p><p>The initial extraction is done by retrieving data from OpenStreetMap as is. Requests to the Overpass API are made to retrieve the data by theme and region. IdeoMap converts all objects into points.</p><p>Updates are triggered manually. For each pair (region, theme) a request to the Overpass API is made to perform a new extraction. The list of differences between the local extraction and the new extraction is displayed to the user. When the version of the OpenStreetMap object has changed, the object is identified as different.</p><p>For each object in the difference list, the user can choose to include it in the local copy.</p><p>For differences that are not suitable, the user can go to OpenStreetMap and correct the data. Then request a new differential update.</p><p>The choice and timing of the integration of updates, object by object, is entirely up to the user.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/0*G-6VsKBZkWbOU8PZ.png" /><figcaption>Figure 8: IdeoMap, synchronization management. Version of the synchronized objects in bold. The objects are completely independent.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/0*_WumuKgfZv8WxFoj.png" /><figcaption>Figure 9: IdeoMap, user interface. Extract from the list of objects available for synchronization.</figcaption></figure><p>Criticism of this approach:</p><ul><li>The IdeoMap solution displays relatively little context for deciding whether or not to integrate objects. Apart from the name of the last contributor, information is to be found outside the solution.</li><li>Synchronization can only be done with the current state of OpenStreetMap.</li><li>Objects with differences are manually checked. Validators can quickly be overwhelmed by the volume of data to be validated.</li><li>The synchronization tool processes all object types, but only produces points.</li><li>The objects are processed in an independent way.</li><li>The tool is not independent of any other formatting tool for the web.</li><li>The tool can only track and synchronize a configured list of tags. Other concurrent tags on OpenStreetMap objects are not taken into account.</li></ul><h4>Synchronizations with LeBonTag, by Geonov</h4><p>LeBonTag is an open source solution for synchronizing thematic data extractions for OpenStreetMap.</p><p>A region and thematic filters are configured. Thematic control and attributes can be assigned to validators.</p><p>The initial import is done on date and as is with all the regional data from OpenStreetMap.</p><p>During each daily update, a differential between the initial import date and the current state is produced via the Overpass API, for all OpenStreetMap data.</p><p>The objects targeted by the filters whose version is different from the one in the synchronized copy are submitted to the users who are in charge of the validation.</p><p>The versions of the validated objects are integrated one by one in the synchronized copy. The objects that do not satisfy the validators have to be corrected in OpenStreetMap. The corrections will be retrieved in the next update.</p><p>Before an object can be included in the synchronized copy, it needs to be validated in all thematic in which it is targeted. If attributes are submitted to different validators, all validators must have validated the object.</p><p>Criticism of this approach:</p><ul><li>Objects with differences are manually checked. The validators can quickly be overwhelmed by the volume of data to be validated.</li><li>Object updates are done independently.</li><li>The tool is adapted to follow nodes or ways, but not relations.</li><li>The tool lacks contextual information to help validation (intermediate modifications of the history, editing software used…)</li><li>You have to wait until the next day to get the corrected data into OpenStreetMap back.</li><li>The Overpass API is not adapted to synchronize the volume of non-thematic data on large regions.</li></ul><h4>Synchronizations with MaRS, by Facebook</h4><p>Facebook uses OpenStreetMap for mapping in its various applications. In this context they have contributed massively to OpenStreetMap. They have also implemented a solution to ensure the quality of the maps they distribute.</p><p>This controlled replication of OpenStreetMap data is updated in flux and republished as an export from time to time. This distribution of OpenStreetMap data is called Daylight¹⁹. This version of the data is reused by other actors such as Esri²⁰ or MapTiler²¹.</p><p>To produce this controlled replication, Facebook has developed a specific tool: MaRS²² ²³. This tool is not distributed, is not accessible and its configuration is not known, only Daylight, the produced data result is available.</p><p>The objectives of this solution are the following.</p><ul><li>Have a copy of the OpenStreetMap data as close as possible to the original.</li><li>Have a representation of the real world as accurate as possible.</li></ul><p>The strategy is to address both axes independently.</p><ul><li>Quality is addressed by flagging suspicious changes and correcting them as quickly as possible in OpenStreetMap.</li><li>The actual representation of the world is handled by being as up-to-date as possible with the original OpenStreetMap data.</li></ul><p>As for the other tools, it is assumed that only the original OpenStreetMap database should be edited.</p><p>Contributions to OpenStreetMap are made in changesets whose internal consistency is uncertain. The idea here is to address the issue of consistency of changes by not treating objects one by one, nor by changeset, or cumulative changesets. But rather by groups of related (topologically and contextually) modified objects. The temporal interval of the changes taken into account in these groups is not important. The groups are then the atomic integration unit to the synchronized copy of OpenStreetMap. They are called LoChas (logical changesets).</p><p>The goal is to ensure local consistency when a group of partial changes is integrated into the replication.</p><p>The longer we wait to integrate the changes, the more likely the LoChas will aggregate more and more objects from one to the next. It is therefore necessary to have algorithms to cut LoChas into units of reasonable size while trying to integrate the changes quickly.</p><p>For this purpose an automatic integration of acceptable changes helps to keep the stock of LoChas low while their sizes small. This acceptance of LoChas is handled by rules, machine learning and if necessary human validation and correction of data in OpenStreetMap.</p><p>This approach allows to process in flow the partial integration of changes while keeping the local copy integrity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/0*0PnD8J315kqOcRY-.png" /><figcaption>Figure 10: MaRS, synchronization management. Grouping in space of objects in LoChas. In bold the synchronized LoChas and version of the objects.</figcaption></figure><p>Criticism of this approach:</p><ul><li>It is an internal Facebook solution, not easily replicable. Little information is available about the software.</li><li>The public release of Daylight is interesting (and required by the data license), but the production criteria are not known. Being produced in-house, it is also not possible to produce variants. Daylight is currently released about once a month.</li></ul><h4>General criticism of the approaches</h4><ul><li>Only LeBonTag is an open source synchronization tool.</li><li>Only OSMCha is a collaborative tool open to the community and collaborative work. The other tools are intended for internal usage. However, there are use cases where several entities could collaborate on the same region to validate data together.</li><li>Only MaRS produces output data in OpenStreetMap format.</li><li>Only MaRS addresses the issue of changes consistency by introducing the concept of LoCha.</li></ul><h3>Quality and acceptability of changes</h3><h4>IdeoMap, by Teritorio</h4><ul><li>The solution targets OpenStreetMap tags. A change on these tags requires a human revalidation.</li><li>Geometry changes are not monitored.</li><li>Objects have to be validated one by one and independently from each other.</li></ul><p>There are no tool-specific criteria or other possible configurations than tags to monitor.</p><h4>LeBonTag, by Geonov</h4><ul><li>The solution targets OpenStreetMap tags. A change on these tags requires a human revalidation.</li><li>Geometry changes are monitored. Small differences in geometry are filtered and discarded to not be considered as modifications.</li><li>A list of contributors allows to automatically accept objects for which they are the last contributor.</li><li>A confidence index is given to the contributors to help the validation work. Contributors are rated according to the validation or invalidation of their previous contributions.</li><li>The objects are to be validated one by one and independently from each other.</li></ul><p>There are no tool-specific criteria or other possible configurations than tags to monitor.</p><h4>MaRS, by Facebook</h4><p>Unlike other solutions, the idea is to automatically validate everything that can be validated. The objective is to minimize the need for human validation while reducing validation times.</p><p>Unlike other tools, objects are not validated independently, but grouped in a coherent way: LoChas.</p><ul><li>There are rules to automatically accept changes, starting with minor geometry changes and non-targeted tags. All these rules are internal and not publicly available.</li><li>A validation engine built by machine learning is then used. Its behavior as well as the data used for its training and its model are internal and not publicly available.</li><li>The remaining LoChas are then manually reviewed. The necessary corrections are made in OpenStreetMap.</li></ul><h4>OSMCha</h4><p>OSMCha is the only public tool that provides validation rules for changes. The validation is done at the level of changesets.</p><p>We note the existence of several types of control rules:</p><ul><li>rules about the context of contribution: trust in the user, editing tool used ;</li><li>rules about the changes themselves: for example, deleting dozens of objects at the same time;</li><li>rules about the final state after applying the changeset, targeting only the content of the changeset: for example, introducing an insult in a name.</li></ul><h4>Overall criticism of the approaches</h4><p>Few change validation rules are publicly available. The only one available is the OSMCha one about changesets and not LoChas.</p><p>Note that other quality tools, such as Keep Right, OSM Inspector and Osmose-QA also validate the final state. But unlike OSMCha, they validate the whole data set and not only the changes. For example, Osmose-QA can detect that two identical bakeries are next to each other (which is a duplicate), while the changes themselves can be completely valid (addition of a single bakery).</p><p>It can be noted that different levels of validation can be set up to facilitate validation.</p><ul><li>Automatically accept all trivial changes.</li><li>Control the change itself.</li><li>Control the final state after change.</li><li>Control the global state after change (none of the studied synchronization tools offer this).</li><li>Validation can be based on rules, automatic learning and manual control.</li><li>Using the contribution context (meta-information).</li></ul><h3>Conclusion</h3><p>MaRS seems to be the tool with the most functionality. Unfortunately, it is an internal tool, not reusable and with little public information available.</p><p>MaRS is not a collaborative tool, nor a tool that can be configured for its own use; it is not a tool that addresses thematic data.</p><p>OSMCha provides a collaborative aspect, but is not a data synchronization tool and change review is voluntary.</p><p>LeBonTag and IdeoMap are aimed at local authorities and deal with regional and thematic data but do not automate the validation of changes.</p><p>Only MaRS addresses the issue of consistency of synchronized data.</p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote1anc">1</a>] Des TIC au TOC1. Contribuer à OpenStreetMap : entre commun numérique et utopie cartographique. Marina Duféal et Matthieu Noucher 2017. <a href="https://journals.openedition.org/netcom/2635">https://journals.openedition.org/netcom/2635</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote2anc">2</a>] ECCE Carto- Des Espaces de la Contribution à la Contribution sur l’Espace — Profils, pratiques et valeurs d’engagement des contributeurs d’OpenStreetMap (OSM). Marina Duféal, Camille Jonchères, Matthieu Noucher 2016. <a href="https://shs.hal.science/halshs-01371544/">https://shs.hal.science/halshs-01371544/</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote3anc">3</a>] <a href="https://wiki.openstreetmap.org/wiki/Organised_Editing/Activities">https://wiki.openstreetmap.org/wiki/Organised_Editing/Activities</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote4anc">4</a>] Corporate Editors in the Evolving Landscape of OpenStreetMap. Jennings Anderson, Dipto Sarkar and Leysia Palen 2019. <a href="https://www.mdpi.com/2220-9964/8/5/232">https://www.mdpi.com/2220-9964/8/5/232</a></p><p>[<a href="https://fr.wikipedia.org/wiki/Coutume">5] https://fr.wikipedia.org/wiki/Coutume</a></p><p>[<a href="https://fr.wikipedia.org/wiki/Usage_local_ayant_force_de_loi">6] https://fr.wikipedia.org/wiki/Usage_local_ayant_force_de_loi</a></p><p>[<a href="https://josm.openstreetmap.de/browser/josm/trunk/resources/data/validator">7] https://josm.openstreetmap.de/browser/josm/trunk/resources/data/validator</a></p><p>[<a href="https://github.com/openstreetmap/iD/tree/develop/modules/validations">8] https://github.com/openstreetmap/iD/tree/develop/modules/validations</a></p><p>[<a href="https://wiki.openstreetmap.org/wiki/Keep_Right">9] https://wiki.openstreetmap.org/wiki/Keep_Right</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote10anc">10] </a><a href="https://wiki.openstreetmap.org/wiki/OSM_Inspector">https://wiki.openstreetmap.org/wiki/OSM_Inspector</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote11anc">11] </a><a href="https://wiki.openstreetmap.org/wiki/Osmose">https://wiki.openstreetmap.org/wiki/Osmose</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote12anc">12] </a><a href="https://wiki.openstreetmap.org/wiki/OSMCha">https://wiki.openstreetmap.org/wiki/OSMCha</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote13anc">13] </a><a href="https://github.com/MichaelVL/osm-analytic-tracker">https://github.com/MichaelVL/osm-analytic-tracker</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote14anc">14] </a><a href="https://github.com/Cartocite/osmada">https://github.com/Cartocite/osmada</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote15anc">15] </a><a href="https://wiki.openstreetmap.org/wiki/Overpass_API">https://wiki.openstreetmap.org/wiki/Overpass_API</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote16anc">16] </a><a href="https://wiki.openstreetmap.org/wiki/OSM_XML">https://wiki.openstreetmap.org/wiki/OSM_XML</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote17anc">17] </a><a href="https://wiki.openstreetmap.org/wiki/PBF_Format">https://wiki.openstreetmap.org/wiki/PBF_Format</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote18anc">18] </a><a href="https://wiki.openstreetmap.org/wiki/OSMCha">https://wiki.openstreetmap.org/wiki/OSMCha</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote19anc">19] </a><a href="https://daylightmap.org/">https://daylightmap.org/</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote20anc">20] </a>Dawn of OSM Daylight in ArcGIS <a href="https://www.esri.com/arcgis-blog/products/arcgis-living-atlas/mapping/dawn-of-osm-daylight-in-arcgis/">https://www.esri.com/arcgis-blog/products/arcgis-living-atlas/mapping/dawn-of-osm-daylight-in-arcgis/</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote21anc">21] </a>Detailed maps with quality control <a href="https://www.maptiler.com/news/2021/12/detailed-maps-with-quality-control/">https://www.maptiler.com/news/2021/12/detailed-maps-with-quality-control/</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote22anc">22] </a>MaRS: How Facebook keeps maps current and accurate. Saurav Mohapatra, 2019. <a href="https://engineering.fb.com/2019/09/30/ml-applications/mars/">https://engineering.fb.com/2019/09/30/ml-applications/mars/</a></p><p>[<a href="https://www.teritorio.fr/support/blog-technique/etat-de-lart-synchronisation-dextraction-dopenstreetmap-sous-contrainte-de-qualite/#sdfootnote23anc">23] </a>“Keepin’ it fresh (and good)!” — Continuous Ingestion of OSM Data at Facebook. Ski-U-Mah, 2019. <a href="https://2019.stateofthemap.us/program/sun/keepin-it-fresh-and-good-continuous-ingestion-of-osm-data-at-facebook.html">https://2019.stateofthemap.us/program/sun/keepin-it-fresh-and-good-continuous-ingestion-of-osm-data-at-facebook.html</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3d46907c5151" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Optimization of RGB DEM tiles for dynamic hill shading with Mapbox GL or MapLibre GL]]></title>
            <link>https://medium.com/@frederic.rodrigo/optimization-of-rgb-dem-tiles-for-dynamic-hill-shading-with-mapbox-gl-or-maplibre-gl-55bef8eb3d86?source=rss-92b83f95ef5c------2</link>
            <guid isPermaLink="false">https://medium.com/p/55bef8eb3d86</guid>
            <category><![CDATA[maplibre]]></category>
            <category><![CDATA[vector-tiles]]></category>
            <category><![CDATA[dem]]></category>
            <category><![CDATA[mapbox-gl]]></category>
            <dc:creator><![CDATA[Frédéric Rodrigo]]></dc:creator>
            <pubDate>Tue, 11 Jan 2022 13:47:00 GMT</pubDate>
            <atom:updated>2022-01-11T13:47:00.283Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Dynamic hill shading and terrain elevation use raster tiles in a specific encoded format. These tiles have the drawback of being quite heavy. Here we study a solution that reduces this volume by 60%.</em></p><p><em>This article is an English translation of my own </em><a href="https://makina-corpus.com/sig-webmapping/optimisation-tuiles-mnt-rgb-ombrage-dynamique-mapbox-gl-maplibre-gl"><em>French article from Makina Corpus Blog</em></a><em>.</em></p><p>The French BD ALTI® is a Digital Elevation Model (DEM). At 25 m, it contains a point of terrain elevation on the territory every 25 m. It is a raster data, that is to say, it is made of pixels. Each pixel is a square of 25 m per side.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/813/1*X9AXMd0NqGzkOzDoR4gLpQ.jpeg" /><figcaption>Raw visualization of a DEM. The color gradient from black to white is related to the altitude.</figcaption></figure><p>To use a terrain model on web maps we can:</p><ul><li>Pre-compute hill shading: i.e. make lighter the faces exposed to sun and darker the ones in shadow. This shading is an image that we can manipulate as for a raster map background in the form of PNG raster tiles.</li><li>Compute vector hill shading tiles, which are a vectorized version of the previous tiles. These are more efficient to transfer on the web. A graphic style can be applied on the client side but the graphic rendering of the relief is not as fine.</li><li>Provide directly the terrain model. The computation of the hill shading being performed on the client side, especially in Web GL. We can with this way apply a graphic style to the hill shading. The position of the light source can be adjusted or even be moved dynamically on the client side: for example when the map is rotated or to make the sun move. These are raster elevation tiles in PNG file format, with an encoding of the altitude called RGB (red, green, blue).</li><li>Extract contour lines from the terrain model and distribute them as vector tiles.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dZ9I4PXgRCqAbLplOEIcSQ.jpeg" /><figcaption>Pre-computed terrain hill shading in white and black. Elevation model rendered as stylized hill shading. Contour and shading. Vectorized and stylized hill shading with a color palette.</figcaption></figure><p>In a previous article we saw how to use the 75 m BD ALTI® terrain model of the French National Geographic Institute (IGN) to produce tiles for Web GL maps (Mapbox GL, MapLibre GL, Césium…). Since then, the IGN has made available almost its entire catalog in OpenData, including the 25 m version of the BD ALTI® and the RGE Alti distributed at 1 m and 5 m but whose real accuracy varies depending on the location.</p><p>Now, we presented how to use a digital terrain model to produce dynamic hill shading raster tiles (RGB) and contour vector tiles. So we adapted the process to the new 25 m version. The 75 m version allowed to produce raster tiles up to zoom level 11, while the 25 m version allows to go up to zoom level 12.</p><p>Indeed, with a latitude of 45 ° in metropolitan France we have:</p><ul><li>zoom level 8: 431 m/pixel,</li><li>zoom level 9 : 216 m/pixel,</li><li>zoom level 10: 108 m / pixel,</li><li>zoom level 11: 54 m/pixel,</li><li>zoom level 12: 26 m/pixel.</li></ul><p>For each additional zoom level, the amount of data required is approximately twice.</p><p>Furthermore, the total weight of these raster tiles is quite large. The more hilly a tile is, the heavier this PNG RGB encoded tile weighs. Tiles of 300 KB to 400 KB are common in mountains areas. These are images with 512 pixels on each side.</p><p>The zoom level is also important: at maximum zoom 12, the terrain will be relatively less rugged than at lower zooms. At lower zoom levels, the area covered by a tile will be larger, and therefore more varied.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*hqgkDH9hTSIfAUR0ldUkYQ.png" /><figcaption>Tile at zoom level 12, DEM encoded in PNG RGB: 310 Kb.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*EAVQprzleSUDVQ8U6rB-pw.png" /><figcaption>Tile of zoom level 8, DEM encoded in PNG RGB: 430 Kb.</figcaption></figure><p>These images are not made to be viewed directly, it is RGB encoded data.</p><p>The relationship between the altitude and the color of each point is :</p><pre>altitude = -10000 + ((Rouge * 256 * 256 + Vert * 256 + Bleu) * 0.1)</pre><p>The vertical resolution of these images is thus encoded with a vertical resolution of 10 cm. The horizontal resolution depends of course on the zoom level, but also on the latitude of the tile coordinates.</p><h3>RGB tiles, a big problem</h3><p>The RGB encoded DEM offers the best visual result while offering the largest number of possibilities on the client side. In addition to shading, it also allows 3D rendering of the map (2.5D in fact).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*vQJYzlmVoCLbXp1J1vzCGQ.jpeg" /><figcaption>Map warping according to terrain model and shading. View with Mabox GL JS 2, not free. MapLibre GL will soon support this same functionality.</figcaption></figure><p>However, these RGB tiles are still heavy to load for the client. A map on a 1300x900 pixel web page at zoom level 8 with terrain shading and partly in mountains area consumes 3.0 MB of vector map data tiles and 7.0 MB of PNG RGB tiles for hill shading.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/667/1*fDBjAfXXTj25TfMoIhIUBQ.jpeg" /><figcaption>1300x900 pixel map.</figcaption></figure><h3>Optimizing the size of RGB encoded tiles</h3><p>This size problem occurs all the time, but especially if you want to pre-download hill shaded cartography on mobile for offline use… which can be relevant in the mountains area.</p><h3>Switch to JPEG format</h3><p><a href="https://en.wikipedia.org/wiki/JPEG">JPEG</a> is a lossy image compression format. That means that it will adjust the content of the image in a way that is not very visible to improve the compression. The JPEG is adapted to the compression of photographies.</p><p>The compression is more effective when the content is more predictable in relation to the rest of the image. Basically, the more “abruptly” the colors of the pixels change, the harder is to compress it. In other words, the lower the entropy, the easier it is to describe.</p><p>Terrain hill shading is based on a relative difference in elevation. The lighting and shading depend on whether the terrain is rising or falling.</p><p>Lossy compression changes the data and introduces artificial artifacts of terrain variations. These artifacts, combined with the fact that the compression is done for color perception to the human eye while our images contain data, completely disqualify the use of JPEG for this purpose.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*-15QxJhy0PeESWNdmSaHlQ.jpeg" /><figcaption>RGB tiles compressed in JPEG with a quality of 90 on 100. 240 KB.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*fL5M6kqr4zosrrgdRxKRVg.jpeg" /><figcaption>Hill shading produced by JPEG compression.</figcaption></figure><h3>WebP</h3><p>Instead of the PNG image format, it is also possible to use the <a href="https://en.wikipedia.org/wiki/WebP">WebP</a> format which can be lossless or not. It is based on a more modern algorithm originally designed for video compression. It allows a better compression rate than PNG.</p><p>The processing of the BD Alti 25 m over France in PNG RGB for the zoom levels from 5 to 12 gives a total of 3.7 GB. The same tiles but in lossless WebP give a total of 2.2 GB, which represents a gain of 40%.</p><p>However, WebP is not yet a fully supported format by all web browsers.</p><p><a href="https://caniuse.com/?search=webp">Statistics</a> tell us that by 2022, 5% to 7% of users will be using browsers that do not support it.</p><p>Depending on the use case, it may still be acceptable to serve these users maps without hill shading in regard to the size gain provided by WebP.</p><h3>Optimization of PNG tiles nevertheless</h3><p>The PNG image format, like lossless WebP, cannot produce images smaller than it already does with its compression algorithm.</p><p>However, there are upfront techniques for reducing the size of PNGs, such as quantization. This is the adjustment of pixel colors to reduce the number of different colors and use a color palette instead of a full color space RGB (red, green, blue). The palette contains a maximum of 256 colors. As an example the zoom level 8 tile above initially contains 14,616 different colors. However, the generic “quantization” is not adapted to the altimetry data encoded in the image. Given the RGB encoding formula for altimetry, changing the value of green has 256 times more impact on the encoded altitude than changing the value of blue.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*EAVQprzleSUDVQ8U6rB-pw.png" /><figcaption>Tile at zoom level 8 containing 14,616 different colors.</figcaption></figure><h3>The inherent problem with the compression of these images</h3><p>We must think about the nature of the encoded data and not about the colors represented in the image. The three colors resulting from the encoding of the altimetry cannot be treated in a similar way. Red has 256 times more weight than green, which itself has 256 times more weight than blue. Standard image processing tools are not aware of this particularity.</p><p>If we look at the different colors separately of a level 8 tile, we see clearly that red does not vary, green vary a little and blue a lot.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/768/1*Ap813xARu18GdHvnE16lAg.png" /><figcaption>Decomposition of the of red, green and blue. Note that the first is really “red”, but very dark red, uniform value: 1 of 255.</figcaption></figure><p>We see that the blue channel is much noisier than the others, especially at low zoom levels where the altitude varies a lot from one pixel to its neighbors, almost randomly. If we remove the blue channel (we can’t really remove it, but set it to 0 for all pixels), then the same PNG-compressed image is only 91 KB, or 80% smaller. This is the very noisy data that makes the image difficult to compress. The more random the values, the greater the entropy, and therefore the more inefficient the compression.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*ma70HhfOW8N81YFN7sVmmg.png" /><figcaption>Tile at zoom level 8 containing 0 for the blue value. 97 KB, that is 77% less.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*Ds83Rw7y6TeHkPGVmH4CeQ.png" /><figcaption>Tile at zoom level 12 containing 0 for the blue value. 41 KB, or 87% less.</figcaption></figure><p>The blue channel has an amplitude of 256 levels, one level represents 10 cm. We have therefore introduced a maximum error of 256 * 0.1 = 25.6 m in altitude.</p><p>For example: at a zoom level 8, the distance between two pixels is 431 m, an altimetric error margin of 25 m can be acceptable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/256/1*2KiiYGoFTMRJSdnAGEZN9Q.gif" /><figcaption>Animation showing the hill shading at zoom 8 before and after changing to 0 the values stored in the blue. Having trouble seeing the animation? That’s a good sign!</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/256/1*vxKI6BbTSu1HROziBvTouA.gif" /><figcaption>The same area with an zoomed x4 extract to see better what is going on.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/256/1*krzV18G6BZn-DAwFiZqk3Q.png" /><figcaption>The differences in hill shading values before and after the change.</figcaption></figure><h3>Extending the reduction of the accuracy of the altitude</h3><p>We can extend this idea of reducing the precision level of the encoded altitude according to the zoom level. This is already done for maps where the accuracy and the level of detail depend on the scale of representation.</p><p>Removing the blue encoded part is in fact equivalent to rounding the altitude to the nearest 25 m and setting the last 8 bits (the bits encoded in blue) to 0. We can extend this by varying the level of precision on which we round the altitude and therefore the number of last bits that we set to 0 depending on the zoom level.</p><p>We have decided to delete the last 11 bits for zoom level 5, i.e. to round to within 200 m. For zoom level 12, we delete the last 4 bits, i.e. rounding to the nearest 80 cm. Between zoom 5 and 12 the number of bits deleted is a linear interpolation. Note that zoom level 12 is the last one, so it plays a special role. When the map is displayed with a zoom level higher than 12, it is the tiles of zoom level 12 that are stretched.</p><p>The processing of the BD Alti 25m now weighs 1.3 GB in PNG in place of 3.7 GB, a 65% reduction in size, and 0.8 GB in WebP instead of 2.2 GB. This is also a size reduction of 65%. If we combine the accuracy reduction and the switch to WebP we can even get an 80% gain from original PNG.</p><p>We could make other choices about the number of final bits deleted to further reduce the size of the tiles at the detriment of visual quality, or conversely to increase it. Note also that we could make a specific choice about the precision of the last level of tiles, here zoom 12. Knowing that these tiles will be stretched to be displayed at the additional zoom levels.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/667/1*fDBjAfXXTj25TfMoIhIUBQ.jpeg" /><figcaption>Loading the same map on a web page now takes only 4.0 MB of PNG and 2.9 MB of WebP instead of 7.0 MB (minus 42% and minus 58% respectively).</figcaption></figure><h3>Proposed enhancement to the rio-rgbify project</h3><p>The free software “<a href="https://github.com/rasterio/rasterio">rasterio</a>” (rio) is a tool for processing raster images, typically orthophotographies. “rio-rgbify is a plugin to rasterio for generating RGB elevation tiles.</p><p>We propose to add an option to rio-rgbify to allow to adjust the accuracy of the elevation and thus reduce the volume of the tiles produced.</p><p><a href="https://github.com/mapbox/rio-rgbify/pull/34">Add round-digits option to have better image compression by frodrigo · Pull Request #34 · mapbox/rio-rgbify</a></p><h3>Data and production script</h3><p>The complete procedures to produce the tiles for dynamic RGB shading as well as the vector contour tiles are available, as well as the results of the processing on the DB ALTI® 25m in PNG and WebP MBTiles.</p><p><a href="https://www.data.gouv.fr/fr/datasets/bd-alti-r-25-m-tuiles-pour-courbes-de-niveau-et-ombrage-dynamiques-1/">BD ALTI® 25 m - Tuiles pour courbes de niveau et ombrage dynamiques - data.gouv.fr</a></p><h3>Conclusion</h3><p>The approach presented here allows a significant optimization of the image size for dynamic hill shading and terrain elevation. The level of accuracy of the elevation can be adjusted to keep the visual impact almost imperceptible. The gain is both important for direct display by reducing network transfers and therefore user waiting time. It is also very important for pre-downloading these tiles for offline use, reducing download time and storage requirements.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=55bef8eb3d86" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Web mapping: comparing vector tile servers from Postgres / PostGIS]]></title>
            <link>https://medium.com/@frederic.rodrigo/web-mapping-comparing-vector-tile-servers-from-postgres-postgis-405055e69084?source=rss-92b83f95ef5c------2</link>
            <guid isPermaLink="false">https://medium.com/p/405055e69084</guid>
            <category><![CDATA[vector-tiles]]></category>
            <category><![CDATA[openstreetmap]]></category>
            <category><![CDATA[postgis]]></category>
            <dc:creator><![CDATA[Frédéric Rodrigo]]></dc:creator>
            <pubDate>Mon, 03 Aug 2020 10:22:44 GMT</pubDate>
            <atom:updated>2020-08-03T10:22:44.359Z</atom:updated>
            <content:encoded><![CDATA[<p>Many vector tile servers based on the ST_AsMVT() function of PostGIS are available. Makina Corpus presents here an overview of the specificity of the different solutions.</p><p>This article is an English translation of my own <a href="https://makina-corpus.com/blog/metier/web-mapping-comparaison-des-serveurs-de-tuiles-vectorielles-depuis-postgres-postgis">French article from Makina Corpus Blog</a>.</p><h3>Vector tiles</h3><p>Maps on the web are made up of tiles, i.e. pieces of maps that are loaded when the map is moved or zoomed. These pieces can be images, called “raster”, or geometries — point, line, polygons — called “vector”. Maps composed of vector tiles represent a more recent technique and offer more fluidity and interactivity. This is due to the fact that the data composing the map is in the browser and not just an image representing it.</p><p>A vector tile service can be described by a <a href="https://github.com/mapbox/tilejson-spec">TileJSON</a>. It is a meta-information file which gives, in particular, the list of layers expected in the tiles as well as the lists of attributes available on the objects. The TileJSON also gives the application ranges of the layers: geographical area and available zoom levels.</p><h3>Vector tiles production technique</h3><p>We are interested here in the geographic data stored in databases that we wish to present on the web in the form of vector tiles. The type of database used to do this is essentially Postgres with its spatial data extension PostGIS.</p><p>Historically for a tile, queries are made in the database. The data — geometries and attributes — are retrieved and then processed by the calling program. In the case of raster tiles, the data is drawn in an image and then sent to the web browser. In the case of vector tiles, they are converted to the <a href="https://docs.mapbox.com/vector-tiles/specification/">Mapbox Vector Tile</a> (MVT) binary format and sent to the web browser.</p><p>PostGIS has in these last versions implemented, then optimized, the support of MVT vector tiles. Previously, it was possible to produce GeoJSON or SVG. Today, the support of the MVT format implemented directly in the database simplifies things. Serving tiles is now “just” a matter of retrieving the MVT and sending it to the web browser.</p><p>MVT tiles use integer coordinates to represent geometries. PostGIS takes care of the simplification of geometries, discretization into integer values and the consistency problems this can cause. They can be composed of several layers, for example rivers, a boundary, roads…</p><p>A full range of software has appeared to produce and serve MVT tiles from a Postgres / PostGIS base. These softwares allow to serve tiles in HTTP from the content defined in SQL queries. They all have in common to be built on the <a href="https://postgis.net/docs/manual-dev/ST_AsMVT.html">ST_AsMVT()</a> function of PostGIS.</p><pre>SELECT<br>    ST_AsMVT(*)<br>FROM (<br>    SELECT<br>        ST_AsMVTGeom(<br>            geom,<br>            ST_TileEnvelope(12, 513, 412),<br>            extent =&gt; 4096,<br>            buffer =&gt; 64<br>        ) AS geom,<br>        name,<br>        description<br>    FROM<br>        points_of_interest<br>    WHERE<br>        geom &amp;&amp; ST_TileEnvelope(12, 513, 412, margin =&gt; (64.0 / 4096))<br>) AS t</pre><p><em>Usage of ST_AsMVT() and ST_AsMVTGeom().</em></p><p>These software are built to meet two somewhat distinct objectives:</p><ul><li>produce tiles for map backgrounds,</li><li>produce “subject” data tiles that will be displayed in addition to a background map.</li></ul><h3>Vector tile servers for background maps</h3><p>This kind of server returns tiles that depend only on the tile coordinates (x, y) and the zoom level (z). Typically these tiles contain many layers of data.</p><h4>Postserv</h4><p><a href="https://github.com/openmaptiles/openmaptiles-tools/blob/master/bin/postserve">Postserv</a> is a very simple server that is part of the <a href="https://openmaptiles.org/">OpenMapTiles</a> project <a href="https://github.com/openmaptiles/openmaptiles-tools">toolkit</a>. It is described as not production-ready.</p><p>It has the advantage of using a layer description in tm2source format (in yaml). This is a common format for listing layers used in a background map. The tm2source includes one SQL query per layer. The SQL can contain variables to adjust the behaviour, such as the zoom level.</p><pre>- Datasource:<br>    dbname: openmaptiles<br>    geometry_field: geometry<br>    max_size: 512<br>    srid: 900913<br>    table: (SELECT geometry, ref, class FROM layer_aeroway(!bbox!, z(!scale_denominator!)))<br>      AS t<br>  id: aeroway<br>  properties:<br>    buffer-size: 4</pre><h4>Postile</h4><p><a href="https://gitlab.com/Oslandia/postile">Postile</a> is a solution close to Postserv. It is designed for production while taking a tm2source as a list of layers to be served.</p><p>It offers access to the layers one by one. It also allows to use an MBTiles archive of pre-calculated tiles rather than building them on demand.</p><h4>Tilekiln</h4><p>Build by Paul Norman, <a href="https://github.com/pnorman/tilekiln">Tilekiln</a> is a project that is not yet mature. This one has the particularity of using <a href="https://jinja.palletsprojects.com/en/2.11.x/">jinja2</a> templates to set up SQL queries in the software before sending them to Postgres.</p><pre>SELECT<br>    ST_AsMVTGeom(ST_PointOnSurface(way), {{bbox}}, {{extent}}) AS way<br>  FROM planet_osm_polygon<br>  WHERE way &amp;&amp; {{bbox}}<br>    AND boundary = &#39;administrative&#39;<br>    AND admin_level = &#39;2&#39;<br>    AND name IS NOT NULL<br>{% if zoom &lt;= 12 %}<br>    AND way_area &gt; {{tile_area}}*0.05^2<br>{% endif %}<br>    AND osm_id &lt; 0</pre><p>The project is able to produce a TileJSON descriptor from its configuration.</p><h4>T-rex</h4><p><a href="https://github.com/t-rex-tileserver/t-rex/">T-rex</a> is one of the most advanced servers in its category. This server can, in addition of PostGIS, use GDAL data sources. The SQL definition of the layers is done in a configuration file in toml format. Variables — such as zoom — can be injected into the SQL code.</p><pre>[[tileset.layer]]<br>name = &quot;buildings&quot;<br>datasource = &quot;buildings&quot;<br>geometry_field = &quot;geometry&quot;<br>geometry_type = &quot;POLYGON&quot;<br>buffer_size = 10<br>simplify = true<br>  [[tileset.layer.query]]<br>  sql = &quot;&quot;&quot;<br>    SELECT name, type, 0 as osm_id, ST_Union(geometry) AS geometry<br>    FROM osm_buildings_gen0<br>    WHERE geometry &amp;&amp; !bbox!<br>    GROUP BY name, type<br>    ORDER BY sum(area) DESC&quot;&quot;&quot;</pre><p>The server provides a TileJSON descriptor and a test web interface.</p><h4>Tegola</h4><p><a href="https://github.com/go-spatial/tegola">Tegola</a> is also a mature solution. Tegola can use data from PostGIS or in GeoPackage. This solution can serve multiple tile definitions and offers access by layer. In addition, Tegola has a tile cache and cache invalidation system.</p><p>This server also provides a TileJSON descriptor and a test web interface.</p><h3>Overlaying data vector tile server</h3><p>Servers providing overlay data include only the requested layer in the tile. Some servers allow parameters in the tile URL. These parameters are sent to the SQL query to control the content of the produced tiles: for example filtering the data by date, by user…</p><p>This type of server does not deal with SQL queries, they access existing tables or functions returning records.</p><p>Functions returning tiles can be defined in SQL. They can be considered as views with parameters.</p><pre>CREATE OR REPLACE FUNCTION tile_source(z integer, x integer, y integer, query_params json) RETURNS bytea AS $$<br>DECLARE<br>  mvt bytea;<br>BEGIN<br>  SELECT INTO mvt ST_AsMVT(tile, &#39;public.function_source&#39;, 4096, &#39;geom&#39;) FROM (<br>    SELECT<br>      ST_AsMVTGeom(ST_Transform(geom, 3857), TileBBox(z, x, y, 3857), 4096, 64, true) AS geom<br>    FROM public.table_source<br>    WHERE geom &amp;&amp; TileBBox(z, x, y, 4326)<br>  ) as tile WHERE geom IS NOT NULL;<br>  RETURN mvt;<br>END<br>$$ LANGUAGE plpgsql IMMUTABLE STRICT PARALLEL SAFE;</pre><p><em>Example of a function returning tiles.</em></p><h4>Dirt</h4><p><a href="https://github.com/tobinbradley/dirt-simple-postgis-http-api">dirt-simple-postgis-http-api</a> allows you to obtain the contents of a table in vector tiles or in other formats such as GeoJSON. It also allows to apply some simple functions, such as obtaining the centroid of geometries while using filters.</p><p>It does not allow to define your own SQL queries.</p><h4>pg_tileserv</h4><p><a href="https://github.com/CrunchyData/pg_tileserv">pg_tileserv</a> is a young project, developed by the famous Paul Ramsey (among others, the creator of PostGIS). The project already contains all the good ideas for this kind of server: data from a table or a function returning records, parameters to filter the data, parameters to adjust the creation of vector tiles, etc.</p><h4>Martin</h4><p><a href="https://github.com/urbica/martin">Martin</a> is a more mature project that served as a model for pg_tileserv. It also can use a table or function as a data source and supports parameters to filter data.</p><h3>Overview</h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7fafe468cbbeb6483cd953056167297c/href">https://medium.com/media/7fafe468cbbeb6483cd953056167297c/href</a></iframe><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/41104d554a5a76dfa383cf8ab0a66164/href">https://medium.com/media/41104d554a5a76dfa383cf8ab0a66164/href</a></iframe><p>The features of the different alternatives presented are similar, especially for the most advanced projects. However, there are some small differences that may lead to choose them for certain use cases. For example:</p><ul><li>only T-rex allows to choose the projection,</li><li>only Postserv and Postile can use a tm2source,</li><li>not all servers offer a TileJSON descriptor,</li><li>only Martin and pg_tileserv produce URL-based configurable tile.</li></ul><p>In summary, use Postserv and Postile for generic background map (usable with OpenMapTiles for example), T-rex and Tegola for the variety of their functionalities for custom background map. For on-demand and URL customizable data tile layer, Martin is the most advanced solution while the new pg_tileserv is a promising one.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=405055e69084" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[ImpOsm2pgRouting: Route planning on OpenStreetMap road network with the benefit of updates]]></title>
            <link>https://medium.com/@frederic.rodrigo/imposm2pgrouting-route-planning-on-openstreetmap-road-network-with-the-benefit-of-updates-1e70f280ac5e?source=rss-92b83f95ef5c------2</link>
            <guid isPermaLink="false">https://medium.com/p/1e70f280ac5e</guid>
            <category><![CDATA[routing-software]]></category>
            <category><![CDATA[routing]]></category>
            <category><![CDATA[openstreetmap]]></category>
            <category><![CDATA[imposm]]></category>
            <category><![CDATA[pgrouting]]></category>
            <dc:creator><![CDATA[Frédéric Rodrigo]]></dc:creator>
            <pubDate>Thu, 27 Feb 2020 11:38:21 GMT</pubDate>
            <atom:updated>2020-02-27T11:38:21.196Z</atom:updated>
            <content:encoded><![CDATA[<p>Approach for importing and maintaining an up-to-date road graph of OpenStreetMap data and using it to calculate routes with pgRouting.</p><p>This article is an English translation of my own <a href="https://makina-corpus.com/blog/metier/2020/calcul-d2019itineraires-sur-un-reseau-de-voirie-openstreetmap-en-profitant-des-mises-a-jour">French article from Makina Corpus Blog</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*ASOJVnqoYEZvFrjDCmIdhw.jpeg" /><figcaption><a href="http://www.consta.de/">Constantin Litvak</a>, CC By Sa</figcaption></figure><h3>OpenStreetMap</h3><p>For those who does not still know it, <a href="https://www.openstreetmap.org/">OpenStreetMap</a> is a collaborative mapping project under a free license. The primary goal was to map the streets of the world, but it now goes far beyond that. The OpenStreetMap database contains a network of roads annotated with attributes such as name, type (“street”, “motorway”…) or speed limits. Unlike other map data “providers”, modifications are made available immediately: no prior validation and continuous broadcast of modifications.</p><h3>Route calculation</h3><p>A route planner is a software program that will use a road network (graph) to determine the most appropriate route. This path is rarely the shortest in distance. For example by car, you want to use the fastest route and in fact use longer but faster roads, as well as respecting constraints such as one-ways. We will therefore try to calculate the route with the lowest “cost”. Each segment of the graph has a cost associated with it. It is calculated according to the length and attributes such as the type of way, but this can include for example the fact that you have to climb when the calculation is made for bicycles.</p><p>Among the recurring main functionalities there is also the matrix calculation. This is a “distance calculator” (in cost units) that can give for example the travel time between a set of cities.</p><h3>Route planners with OpenStreetMap</h3><p>The OpenStreetMap ecosystem contains several software dedicated to this task. They are optimized to reduce the time to calculate a point-to-point route, this is the nominal use case. The corollary of this speed of execution is the pre-calculation, which is time-consuming and reduces the flexibility of the possible calculation on requests. As these solutions are only able to process OpenStreetMap data, they provide “profiles”. These profiles describe which OpenStreetMap data should be selected among the available data and how to calculate the “cost” of each segment.</p><p>Some of these software are designed to respond quickly even on large scale requests:</p><ul><li><a href="https://github.com/Project-OSRM/osrm-backend">OSRM</a>: implementing the Dijkstra Multi-Level (MLD) and Contraction of Hierarchy (CH) algorithms,</li><li><a href="https://github.com/graphhopper/graphhopper">Graphhopper</a> implementing the Dijkstra and Contraction of Hierarchy (CH) algorithms,</li><li><a href="https://github.com/valhalla/valhalla">Valhala</a>: implementing the Dijkstra Multi-Level (MLD) algorithm.</li></ul><p>In fact, it is not the <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra</a> algorithm that is really implemented, but improvements, typically a bidirectional <a href="https://en.wikipedia.org/wiki/A*_search_algorithm">A-star</a>.</p><h3>Generic route planner</h3><p>In addition to these specialized software, other solutions using generic data sources exist. The most common is <a href="https://pgrouting.org/">pgRouting</a>. Because of its genericity, it does not come with a data importer, profiles or cost functions, or even with its own storage system. pgRouting is a module for the Postgres database. It is necessary to import at first step the data in the database, then to prepare the graph. On request, we must provide the graph with the cost of the segments to pgRouting, then it does the calculation.</p><p>With the exception of importing the data and putting it into a routable network, pgRouting does not use pre-calculation. The preparation time is brief but the time to calculate a route is therefore longer. Consequently the calculations use simple algorithms derived from Dijkstra. This approach allows much more flexibility: the cost function as well as the graph to be routed can be dynamic according to the request (“I want to take moderate slopes by bike with my trailer, but I do not want to go through the city centre”).</p><h3>Import OpenStreetMap data for pgRouting</h3><h4>Generic OpenStreetMap data importers</h4><p>Several tools exist to read an OpenStreetMap extract file (.pbf), filter and import into a database and then apply post-processing. They can also import update files that are available every minute or daily.</p><ul><li><a href="https://wiki.openstreetmap.org/wiki/Osmosis">osmosis</a></li><li><a href="https://wiki.openstreetmap.org/wiki/Osm2pgsql">osm2pgrouting</a></li><li><a href="https://imposm.org/docs/imposm3/latest/">imposm</a></li></ul><p>The database schema depends on the tool and the configuration. But in all cases these generic tools do not directly import a road network ready to use in pgRouting.</p><p>pgRouting requires as input for its calculation a list of segments described by a start identifier, an arrival identifier and the cost of crossing the segment. The calculation goes from segment to segment using the arrival identifier of a segment as the departure identifier of potential next segments. pgRouting does not require the geometry.</p><p>The next logical step after import is to build the graph of segments from the imported OpenStreetMap data.</p><h4>osm2pgRouting</h4><p>The <a href="https://github.com/pgRouting/osm2pgrouting">osm2pgRouting</a> solution is an OpenStreetMap data importer for pgRouting. It reads the old XML data format and understands the OpenStreetMap data ontology. However, it does not contain a data interpretation profile for segment cost.</p><p>This solution is softly maintained and in particular does not have the ability to use the new OpenStreetMap extract binary file format (.pbf), nor able to load large volumes of data and finally it does not allow updates from OpenStreetMap.</p><h3>Set up a generic importer and create the graph of segments</h3><p>We would like to be able to do short distance route calculations on an OpenStreetMap road network over large areas. The data must be kept up to date very regularly so that if the result of a route calculation is not satisfactory, the data can be corrected in OpenStreetMap and the correction in the route planner can be used almost immediately (maximum delay of 1 minute).</p><p>To achieve this goal it is necessary to use pgRouting, as it does not require a pre-calculation step. It will also be necessary to make quick updates from OpenStreetMap data with a generic data importer. Because of the use of a generic data importer, we will also have to create the segment graph ourselves.</p><h4>Import with Imposm</h4><p>Imposm is the latest tool to read data from OpenStreetMap and import it into a database. As osm2pgsql it is oriented for map production but can be used for other tasks.</p><p>OpenStreetMap data consists of nodes, points, ways, relationships (object groups) described by free attributes (tags). We are interested here in a road network that is made up of ways annotated with certain tags (the road is described by ways with key tags highway). We will use an Imposm mapping file to describe the OpenStreetMap data to import.</p><pre>tables:<br>  ways:<br>    type: linestring<br>    mapping:<br>      highway: [__any__]<br>    columns:<br>    - name: osm_id<br>      type: id<br>    - name: geometry<br>      type: geometry<br>    - name: tags<br>      type: hstore_tags</pre><p><em>Configure of Imposm to load the linestring with tags </em><em>highway=* into a table (</em><em>ways automatically prefixed by </em><em>osm, so </em><em>osm_ways) containing the OpenStreetMap identifier, geometry and the set of tags.</em></p><h4>Create a navigable network</h4><p>Then it is required to convert this set of polygonal paths into segments. There is a difference in topology between the imported data and the data needed for route calculations. For calculations we need segments from one intersection to the next. However, the polygonal paths in OpenStreetMap do not impose this structure. A polygonal path can pass through an intersection without ending there and can also end between two intersections.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*MhJb0o5_JKH1WwSMRar2ag.png" /><figcaption>Topology of the data in OpenStreetMap and after cutting at intersections.</figcaption></figure><p>So the first step is to extract all the intersections. These are not the geometric intersections of polygonal paths, but the intersections in the topological meaning of the OpenStreetMap road network. That is, when polygonal paths are explicitly connected to each other by a node. These intersections are numbered and are called “vertices” of the graph. In particular, we does not want to be able to jump from a bridge to a way passing below vertically at the point where they intersect spatially.</p><pre>SELECT<br>    (ST_DumpPoints(geometry)).geom AS point<br>FROM<br>    import.osm_ways<br>GROUP BY<br>    point<br>HAVING<br>    count(*) &gt;= 2</pre><p><em>Collecting intersections.</em></p><p>The second step is to cut the OpenStreetMap polygonal paths along these same intersections. We do not use the <a href="https://postgis.net/docs/ST_Segmentize.html">ST_Segmentize()</a> function of PostGIS for this purpose, because it cut using a length. The appropriate function for our case is <a href="https://postgis.net/docs/ST_Split.html">ST_Split()</a> which cuts one geometry by another.</p><pre>SELECT<br>    osm_id,<br>    (ST_Dump(ST_Split(<br>        geometry,<br>        ST_Collect(osm_ways_junctions.point))<br>    )).geom AS geometry,<br>    tags<br>FROM<br>    import.osm_ways<br>    JOIN imposm2pgr.osm_ways_junctions ON<br>        osm_ways_junctions.point &amp;&amp; osm_ways.geometry<br>GROUP BY<br>    osm_id,<br>    geometry,<br>    tags</pre><p><em>Cutting of polygonal paths on topological intersections that spatially intersect its geometry.</em></p><p>The ends of each segment must then be reconciliated to the intersection numbers.</p><p>For each segment, all that remains is to gather the elements as the network on which we wishes to calculate routes. This means store it, and extract the desired OpenStreetMap tags and optionally calculate the cost to cross the segment (if the cost is not on request).</p><p>To do this we can use the following database table definition.</p><pre>CREATE TABLE network (<br>    id serial PRIMARY KEY,<br>    osm_id bigint NOT NULL, -- required field, for update<br>    source_vertex_id int, --required field, for routing<br>    target_vertex_id int, -- required field, for routing<br>    geometry geometry(LineString,3857) NOT NULL, -- Advised, for display<br>    cost float,<br>    highway varchar,<br>    name varchar<br>)</pre><p>For example, if you want to make a shortest route planner, the cost may simply be the length of the segment: <a href="https://postgis.net/docs/ST_Length.html">ST_Length(geometry)</a>. The road name will be extracted from the OpenStreetMap tags if it is available with tags-&gt;&#39;name&#39; (using the syntax of the Postgres hstore extension).</p><h4>Update</h4><p>Imposm allows you to wait for OpenStreetMap data updates and apply them when they are available. It will download and apply to the database according to the mapping defined during the import. Modifications are made on the OpenStreetMap polygonal paths table. It is necessary to report them on the graph segments.</p><p>To do this, a database trigger collects the modifications made on the polygonal paths table by Imposm. At the end of the transaction, it deletes all the impacted segments and recalculates a new version of them by going through the steps of extracting the intersections and cutting into segments. This update procedure is minimal in the sense that it only modifies the segments of the graph that have actually been modified in OpenStreetMap and is therefore fast.</p><h3>Compute a route with pgRouting</h3><p>Then it is possible to use the loaded and continuously updated graph to calculate routes using only conventionally pgRouting usage.</p><pre>SELECT<br>    ST_Collect(network.geometry) AS geometry,<br>    sum(path.cost) AS total_cost<br>FROM<br>    pgr_dijkstra(&#39;SELECT * FROM selected_network&#39;, 1480, 1503, true) AS path<br>    JOIN network ON<br>        network.id = path.edge</pre><p><em>Calculating the geometry of a route.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/607/1*XcoUKFWoba2IiOAjF7LBKg.png" /><figcaption>Visualizing the route on the graph.</figcaption></figure><h3>ImpOsm2pgRouting</h3><p>This new approach described here is implemented in the “ImpOsm2pgRouting” project. It is intended as an alternative to load large volumes of OpenStreetMap data into a database and use them with pgRouting while keeping the database up to date from OpenStreetMap. This synchronization can be done with a maximum delay of one minute and thus allow to correct the road in OpenStreetMap and to benefit from it almost immediately for the route calculation.</p><p>This project allows you to load and keep the data up to date. It does not force how the network graph should be stored, nor how it should be used. This remains the responsibility of the user.</p><p>It can be used as an external tool to manage the network data on a new or existing project, for example by using it as a Docker container.</p><p><a href="https://github.com/makinacorpus/ImpOsm2pgRouting">https://github.com/makinacorpus/ImpOsm2pgRouting</a></p><p>The project is available on Github and open for contribution.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1e70f280ac5e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Optimization of OpenStreetMap background vector tile production for an on request service: Makina…]]></title>
            <link>https://medium.com/@frederic.rodrigo/optimization-of-openstreetmap-background-vector-tile-production-for-an-on-request-service-makina-5f6dba98a232?source=rss-92b83f95ef5c------2</link>
            <guid isPermaLink="false">https://medium.com/p/5f6dba98a232</guid>
            <category><![CDATA[vector-tiles]]></category>
            <category><![CDATA[openmaptiles]]></category>
            <category><![CDATA[openstreetmap]]></category>
            <category><![CDATA[open-source]]></category>
            <dc:creator><![CDATA[Frédéric Rodrigo]]></dc:creator>
            <pubDate>Tue, 04 Feb 2020 11:10:33 GMT</pubDate>
            <atom:updated>2020-02-04T11:10:33.195Z</atom:updated>
            <cc:license>https://creativecommons.org/licenses/by-sa/4.0/</cc:license>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gqe2nwNYG5qb39yEG_KVAA.png" /></figure><h3>Optimization of OpenStreetMap background vector tile production for an on request service: Makina Maps</h3><p>Implementation of a software stack for serving vector tiles on request. The approach is based on the optimization of OpenMapTiles and the extension of Kartotherian.</p><p>This article is an English translation of my own <a href="https://makina-corpus.com/blog/metier/2020/optimisation-de-la-production-de-tuiles-vectorielles-de-fond-de-carte-openstreetmap-pour-un-service-a-la-demande">French article from Makina Corpus Blog</a>.</p><p>Web and mobile map backgrounds based on data from OpenStreetMap, or alternatives, are distributed in the form of image tiles — called “rasters” — or data tiles — called “vector”. These tiles are the result of the map being divided into a grid. There is a grid for each level of scale (zoom) that we wish to represent.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/523/1*omAdzRjnQX1yppSg1WbfSw.png" /><figcaption>Pyramid of tiles.</figcaption></figure><p>Vector tiles offer more possibilities than raster. Among these advantages, interactivity or on-the-fly graphic style change directly on the client side (browser or mobile application). On the server side, this also means that the same vector tiles need to be sent to all users, regardless of the graphic style to be applied: the only concern is about serving data.</p><p>Makina Corpus wished to set up an on request vector tile service for the generation of OpenStreetMap backgrounds maps called “Makina Maps”.</p><h3>State of the art</h3><h4>Vector tiles</h4><p>In the case of online mapping solutions, vector tiles are available at URLs that follow the pattern {zoom}/{x}/{y}.&lt;extentsion&gt;. The extension is .mvt for Mapbox Vector Tiles, but can also be .pbf, the content remaining the same. These tiles are light in size — a few tens or hundreds kilobytes — and describe the geometries and attributes of objects.</p><p>The geometries included in the vector tiles are the result of cutting out the original geometries from the tile grid. This content is also filtered and simplified according to the zoom level, both on the geometry and on the attributes and their values, in order to keep the tiles light.</p><h4>Production of vector tiles</h4><p>These tiles are pre-calculated and stored to be served by the web server.</p><p>In the case of offline applications, these tiles are archived in MBTiles and embedded with the application. But the size, depending on the geographical area to be covered, are quickly huge.</p><p>Several software stacks exist to produce these tiles: among the free, and therefore open, solutions are <a href="https://openmaptiles.org/">OpenMapTiles</a> and <a href="https://github.com/kartotherian/kartotherian">Kartotherian</a>. Note that Mapbox also has its own in-house solution.</p><h4>Tile production: a heavy industry</h4><p>All these solutions are used to offer global coverage, they also have in common the fact that they pre-calculate the tiles for the whole world. To produce all the tiles 20 up to 30 days are needed with 8 CPUs to an OpenMapTiles instance. The alternative is to parallelize the calculation on a cluster of machines, to be able to process everything faster, even in one day.</p><p>The calculation time of a tile is variable according to the data it contains: it depends of the volume of data but especially of the complexity of the database query to obtain them. The simplest queries, for “empty” tiles of uniform terrain, in the middle of the ocean or the desert for example, take only a few milliseconds. In contrast, a tile at zoom level 14 — the most detailed level in OpenMapTiles — can take up to 15 seconds over complex terrain — while using an SSD database, which is faster read-write than HDD.</p><h4>Updating OpenStreetMap Data</h4><p>OpenStreetMap data changes daily and it is preferable to keep its background map updated. Updating is done by applying OpenStreetMap changes to the database (changes called “diff”). This process identifies tiles that contain data that have evolved and need to be regenerated.</p><h4>Distribution of data</h4><p>In the case of OpenMapTiles, the database contains three object types.</p><ol><li>First, objects selected in OpenStreetMap because they are desired in the vector tiles.</li><li>These same objects are generalized: simplified, filtered or grouped for use in intermediate zoom levels that do not require the full detail of OpenStreetMap. This generalization is a pre-calculation to make the data lighter. The advantage is that vector tiles can then be produced more quickly.</li><li>For the lowest zoom levels, other external data sources of OpenStreetMap are used. They are even simpler and therefore lighter and particularly suitable for these levels of detail. These include, for example, data from <a href="http://www.naturalearthdata.com/">Natural Earth</a>.</li></ol><p>This distribution of data, especially with the help of pre-calculations, makes vector tiles faster to produce. The longest tiles to compute are those with the highest level of detail and the heavy in data: zoom 14. In contrast, raster tiles produced under the default OpenStreetMap mapping style — named <a href="https://github.com/gravitystorm/openstreetmap-carto">OpenStreetMap Carto</a> — do not use a generalization step.</p><h4>Pre-calculation strategy and on request rendering of raster tiles</h4><p>The strategy for raster tiles is to pre-calculate the low zoom level from 0 up to 13 for example. This is the most time-consuming step, as it involves large volumes of data and simplification calculations. The other zoom levels from 14 up to 20 are calculated and rendered on the fly as image tiles from the database.</p><p>Note that where it is mandatory to compute on the server side all zoom levels from 0 up to 20 for raster tiles, vector tiles only go to zoom level 14, which already contains all the details for the following scales. Vector tiles of level 14 should therefore extract and contain more data volume than their raster equivalents.</p><h3>Statement on strategies and constraints</h3><p>Low-detail tiles require pre-calculations from generalization in the database or during tile extraction, as they cover large portions of the territory using detailed data in OpenStreetMap. On the other hand, raster solutions can compute tiles for detailed levels on request. Unfortunately, this strategy is not available with vector tiles, because the most detailed level, zoom 14, is heavy.</p><p>It would therefore be useful to be able to take advantage of the benefits of rendering on request in software stacks for vector tile generation. The on request service first of all significantly reduces the computing power required. This eliminates the need for the pre-generation stage of all tiles, which, for the whole world, takes weeks or a lot of hardware resources. The other advantage is that the time between updating the data in OpenStreetMap and their availability in the vector map can be reduced.</p><h3>Bottleneck identification</h3><p>First of all, an analysis of the performance of vector tile production by OpenMapTiles allows to understand which zoom levels are the slowest.</p><pre>  7.6 tiles/s at z0,    1 tiles in 0:00:00.1<br> 14.4 tiles/s at z1,    1 tiles in 0:00:00.1<br>  3.1 tiles/s at z2,    1 tiles in 0:00:00.3<br> 11.8 tiles/s at z3,    1 tiles in 0:00:00.1<br>  5.5 tiles/s at z4,    1 tiles in 0:00:00.1<br>  3.4 tiles/s at z5,    2 tiles in 0:00:00.5<br>  2.3 tiles/s at z6,    2 tiles in 0:00:00.8<br>  4.6 tiles/s at z7,    2 tiles in 0:00:00.4<br>  3.1 tiles/s at z8,    2 tiles in 0:00:00.6<br>  1.7 tiles/s at z9,    2 tiles in 0:00:01.1<br>  3.8 tiles/s at z10,   4 tiles in 0:00:01.1<br>  4.8 tiles/s at z11,   9 tiles in 0:00:01.8<br>  2.0 tiles/s at z12,  20 tiles in 0:00:09.7<br>  7.0 tiles/s at z13,  80 tiles in 0:00:11.3<br>  0.9 tiles/s at z14, 252 tiles in 0:04:40.0</pre><p><em>Performance of generation of zoom levels of all tiles in urban areas — Paris area — in tiles per second.</em></p><p>Performance analysis shows that zoom level 14 is clearly below the others.</p><p>Given the pre-calculation of generalization and the use of simplified data, the most detailed zoom levels are indeed the slowest. Note that this slowness on the most detailed zoom tiles is magnified exponentially by the fact that each zoom level contains four times as many tiles as the previous one.</p><p>The tiles are composed of thematic layers of data. Each layer is the result of a database query. These queries are limited to the geographical extent of the tile but can be more or less complex depending on the thematic and zoom level. It is interesting to look at the tile generation performances for each of these layers.</p><pre> 1,653.2 tiles/s water               252 tiles in 0:00:00.1<br> 5,191.9 tiles/s waterway            252 tiles in 0:00:00.0<br>   253.0 tiles/s landcover           252 tiles in 0:00:00.9<br>   313.6 tiles/s landuse             252 tiles in 0:00:00.7<br>28,975.5 tiles/s mountain_peak       252 tiles in 0:00:00.0<br>12,825.7 tiles/s park                252 tiles in 0:00:00.0<br>   905.4 tiles/s boundary            252 tiles in 0:00:00.2<br>10,076.8 tiles/s aeroway             252 tiles in 0:00:00.0<br>    37.1 tiles/s transportation      252 tiles in 0:00:06.7<br>     1.0 tiles/s building            252 tiles in 0:04:05.2<br> 7,096.4 tiles/s water_name          252 tiles in 0:00:00.0<br>    84.6 tiles/s transportation_name 252 tiles in 0:00:02.9<br>   971.5 tiles/s place               252 tiles in 0:00:00.2<br>    46.8 tiles/s housenumber         252 tiles in 0:00:05.3<br>    52.2 tiles/s poi                 252 tiles in 0:00:04.7<br>15,672.6 tiles/s aerodrome_label     252 tiles in 0:00:00.0</pre><p><em>Layer generation performance of zoom level 14, in tiles per second.</em></p><p>The buildings layer is by far the most time consuming to produce, with an average extraction time from the database of one second — 1.04 s — per tile. It takes 95% of the total extraction time. It is therefore the prime bottleneck that makes this generation of tiles impracticable for an on request service.</p><h3>Optimization</h3><p>OpenMapTiles uses several SQL tables to store buildings according to their attributes or natures in OpenStreetMap. Reducing this number of tables combined with a restructuring of SQL queries makes the database lighter and improves performance.</p><pre>1.5 tiles/s at layer building, 252 tiles in 0:02:49.6</pre><p>Than the extraction time of the buildings per tile takes only 0.7 seconds. This is a significant gain of about 30%, but is still insufficient for interactive use.</p><h3>Change of strategy for buildings</h3><h4>Reduction of the multitude</h4><p>Buildings are a problem because they are numerous, ubiquitous in the city and with a detailed geometry. This “problem” is particularly true in area where buildings was imported in OpenStreetMap — like in France. On a tile of level 14 in a dense urban area, in median value 25,000 buildings are found, the largest tiles have up to 100,000. All these buildings have to be stored, but also indexed and retrieved from the database.</p><p>In light of this problem, the first idea could be to use the grouping function — also called clustering CLUSTER of the database. It allows to group together on disk data that will be requested simultaneously from the database. Simultaneous access to the data is based here on the criterion of geographical proximity. Note that this grouping of data in the database can be done during the creation of the database or on demand, but its state is not preserved during updates.</p><p>The application of the CLUSTER strategy addresses the problem of data access, but not the one of the volume of objects stored and indexed. This idea of grouping building could be taken up at a topological level. A group — aka cluster — is defined by “close” elements. In the above case the proximity is spatial, but it can also be semantic or visual. A group of close buildings match with the concept city. A small cutting unit is necessary. The lower level on the scale of proximity of buildings is the block.</p><p>Even though the PostGIS spatial data extension of the PostgreSQL database has several functions for grouping spatial data — including <a href="https://postgis.net/docs/ST_ClusterIntersecting.html">ST_ClusterIntersecting</a>, which allows to group objects that touch each other — the idea, in terms of computation, is to keep it as simple and fast as possible: group buildings according to an arbitrary grid.</p><p>The interest is to no longer store and retrieve individual buildings, but groups of contiguous buildings. If in a rural or sparsely populated urban area this will only make little changes, in a dense urban environment the number of objects processed will be considerably reduced. Nevertheless, a cluster does not merge objects. When creating the vector tiles, the clusters are ungrouped and each building get back its independence. Thus, nothing changes in the content of the produced vector tiles, but the generation performance is significantly improved.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/627/1*l1B64UCOe18eqcS-xwW_og.png" /><figcaption>Clusters of buildings following a grid, fast calculation by rounding the minimum coordinates X and Y.</figcaption></figure><pre>4.4 tiles/s at layer building, 252 tiles in 0:00:56.7</pre><p>This new strategy makes it possible to extract the buildings on average of 225 ms. This is now an acceptable delay for an on request service, even if it is at the upper limit for this use.</p><h4>Pre-calculation, the dark side</h4><p>The grouping techniques described can significantly reduce the response time, but a pre-calculation step remains unavoidable. It consists of processing all buildings in an initial calculation to assign them to a cluster. As the number of buildings is large, this calculation duration is not negligible. These clusters must also be stored, which duplicates one of the most important data layers. However, the weight of the clusters table is reduced by half compared to the original table.</p><p>When updating data from OpenStreetMap the original table of buildings is modified. The cluster table has to be derived from it again. Unfortunately, this calculation is long: 5 hours for a clustering of all buildings of Europe.</p><h4>Differential cluster update</h4><p>Since the full calculation time for groupings is too long, only buildings that have actually changed during updates should be considered. The strategy is to track the changes made in the main table of buildings using observation mechanisms — database trigger — that will keep an history of the changes. This history is then used to reproduce the grouping calculation only on the clusters in which buildings have been changed: only these clusters are ungrouped to update the buildings that have evolved, and then recalculated.</p><h3>On request vector tile software stack: “Makina Maps”</h3><p>The two main open source software stacks for pre-calculating vector tiles are OpenMapTiles and Kartotherian. They are made of a set of free softwares that can be composed or interchanged.</p><p>In order to distribute vector tiles on request, a web server is necessary but also one or more styles to display them. Other solutions such as <a href="https://github.com/maptiler/tileserver-gl">TileServer GL</a> — by the developers of OpenMapTiles — are made to serve pre-calculated tiles and styles.</p><p>However for an on request service, we need to have all these components: from the database to production of the tiles and styles web service. We also need tiles caching to improve performance and data update from OpenStreetMap. The update should involve invalidation of the tiles cache when the data contained therein has changed.</p><p>For the design of Makina Maps, the choice was made to assemble OpenMapTiles for the tiles schema and the database, Kartotherian for the tiles extraction and server. Modules to serve styles have been added to Kartotherian. The whole is exposed through a NGINX web server which also be a tiles cache.</p><p>This new free software stack is available on Github, it is <em>light</em> compared to a pre-generation solution. For example, tiles can be used for:</p><ul><li>a French region in 10 min, instead of 1 hour;</li><li>the whole of Europe in 15 hours, instead of a week.</li></ul><p>This solution contains everything you need to quickly and simply serve vector tiles and styles from scratch.</p><p><a href="https://github.com/makinacorpus/makina-maps">makinacorpus/makina-maps</a></p><h3>Conclusion</h3><p>The improved performance of OpenMapTiles makes it possible to provide vector tiles on request. By chaining all server components into a single software stack, OpenStreetMap based background vector tiles are more accessible and easy to deploy.</p><p>The OpenMapTiles improvements detailed here are proposed for integration into the project source code.</p><p>The new Makina Maps software stack is free software available on Github and open for contribution.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5f6dba98a232" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Cassini Vector Style]]></title>
            <link>https://medium.com/@frederic.rodrigo/cassini-vector-style-7e1877e0a77b?source=rss-92b83f95ef5c------2</link>
            <guid isPermaLink="false">https://medium.com/p/7e1877e0a77b</guid>
            <category><![CDATA[mapbox-gl]]></category>
            <category><![CDATA[openstreetmap]]></category>
            <category><![CDATA[cassini]]></category>
            <category><![CDATA[openmaptiles]]></category>
            <category><![CDATA[makina-corpus]]></category>
            <dc:creator><![CDATA[Frédéric Rodrigo]]></dc:creator>
            <pubDate>Fri, 31 Jan 2020 09:50:36 GMT</pubDate>
            <atom:updated>2020-01-31T09:57:18.736Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ekDESBMHUPC-Hg7_jsMkCQ.jpeg" /></figure><p>The Cassini map is the first detailed and topographic map of France, made using distances measured from the ground. Its creation was ordered by French King Louis XIV. The works take place from 1683 up to 1818. Four generations of the Cassini family worked to produce it. See the <a href="https://en.wikipedia.org/wiki/Cassini_map">Wikipedia article</a> for more details.</p><figure><img alt="Extract of the Cassini map" src="https://cdn-images-1.medium.com/max/937/1*nc346hTNR0gZnIjDp_YMtw.jpeg" /><figcaption>Extract from Cassini map. Source gallica.bnf.fr / Bibliothèque nationale de France.</figcaption></figure><p>The French National Institute of Cartography (IGN GeoPortail) offers to display the <a href="https://www.geoportail.gouv.fr/donnees/carte-de-cassini">digitized Cassini map</a>, in a colored version. However, this map has been drawn at a fixed scale, which does not adapt to the zoom level as we can navigate. We present here our approach to reproduce it in a vector way.</p><h3>A Cassini style vector map</h3><p>Producing a vector map style in <a href="https://docs.mapbox.com/mapbox-gl-js/style-spec/">Mapbox GL format</a> based on Cassini style is a challenge. The original style is largely graphic and partly figurative. Modern mapping conventions are not yet present. It is necessary to adapt to the constraints of modern tools. For this project we use the actual OpenStreetMap data through vector tiles proposed by the <a href="https://openmaptiles.org/">OpenMapTiles</a> project without reworking them. We will be able to enjoy the Cassini style world wide.</p><p>For the sake of simplicity, we stick to a monochrome version and ignore the relief and the terrain coverage (woods, moors, swamps, beaches, meadows and vineyards).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*P08fgELxwEQqEd7ScRFlzQ.jpeg" /><figcaption>Preview of the result of the style in Mapbox GL format.</figcaption></figure><p><a href="https://makinacorpus.github.io/cassini-gl-style/#11.11/43.6019/1.4356">GL Style Package Preview</a></p><h3>From single-scale to multi-scale</h3><p>One difficulty is to build a multi-scale zoomable vector map from a single-scale Cassini map. The Cassini map is made at the scale of one <em>ligne</em> per cent <em>toises</em>. As a reminder, a <em>ligne</em> is a French unit of measurement established in the Middle Ages and is equal to one-twelfth of a Fench <em>inch</em>, or 2.256 millimeters. As for the <em>ligne</em>, it corresponds to 6 French <em>feet</em>, that is to say 1.949 meters. The original scale is (we take out the calculation) … ~1:86,400.</p><h4>Cities and other places</h4><p>In the Cassini style the inhabited or ruined places are represented by pictograms according to their characteristics. There is no notion of order between these pictograms. They are always represented with the same size.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/896/1*04FG1VFC2SQVtoxh2YEu1g.jpeg" /><figcaption>Extract from the simplified legend of the Cassini map.</figcaption></figure><p>On the one hand, we do not have the necessary attributes in OpenMapTiles to distinguish Abbeys (<em>abbayes</em>) from Priories (<em>prieurés</em>), for example, or some features does not make sense anymore, like Commandery (<em>commanderies</em>, for Knights Templar) or Fiefdoms (<em>fiefs</em>, for Lord). On the other hand, this pictogram catalogue is not suitable for the modern classification of places. We want to show the size of cities and their predominance (capitals, or local “capitals”).</p><p>OpenMapTiles categorizes cities according to their size (city, town, village, hamlet, isolated_dwelling). Cities are then filtered by zoom level of the vector tiles, according to a priority based notably on category and administrative importance.</p><p>We select the following symbols and consider them ordered from the most important to the least important. In order to make them intuitive, we use both a progression of size and complexity of the pictogram:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/139/1*HPLnOrgSgH9NdGZNgJxZ2Q.png" /><figcaption>Parish, Farm and Black square.</figcaption></figure><ul><li>Parish, (<em>Parsoiſse</em>, also written <em>paroisse</em> in modern French, since the letter “<a href="https://en.wikipedia.org/wiki/Long_s"><em>ſ</em></a>&quot; no longer exists),</li><li>Farm or <em>Metairie</em> (rented farm),</li><li>Black square, isolated building (not present in the legend above).</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/240/1*hXgtMIEWWN_LUXRQreMiNw.png" /></figure><p>The idea is to keep this progression of ordered symbols and reuse it at different scales. Thus the pictograms will not represent the same categories of places according to the zoom level, but only a notion of order. As we zoom in on the map, the level of detail increases. We then introduce more categories (city size) to be represented and we shift the pictograms of lower importance to objects of lower categories.</p><h4>Roadway</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/428/1*IXgjBp_8myOL3HZNyjCjAg.jpeg" /><figcaption>Extract from the simplified legend of the Cassini map</figcaption></figure><p>Same problem, same approach!</p><p>To represent the roadway, the legend of Cassini shows paved roads (<em>route pavée</em>), tree avenues (<em>avenue d’arbre</em>, it is almost a pleonasm, an avenue was by definition lined by trees) and paths (<em>sentier</em>).</p><p>We will retain the pattern of tree-lined paved lanes for major roads. Unpaved avenues are represented only by tree-lined lanes, with no linear layout. We ignore this representation, which is less common in the Cassini map and does not correspond to our modern intuition that the lane should be signified by a linear line. The paths are drawn with two parallel dotted lines.</p><p>We make the choice for the less important roadways to use a representation that is not present in the Cassini map: two continuous lines, but this time without the tree lines.</p><p>Here again, the categories of roadways to be considered “important” will vary according to the zoom level. For low zoom levels, only the most important raodways are represented. We will use only one type of representation, and in order to make the rendering less cumbersome, we will only keep the version without the trees.</p><p>For purely aesthetic reasons, we choose to not represent motorways and railways.</p><h4>Extrapolate other scales</h4><p>When we zoom out we can imagine quite easily what it should look like. We reduce the number of objects to represent, we shift the levels of importance of the pictograms and representations to maintain differentiability between the displayed elements. The Cassini map is already at a small enough scale that we do not need to use other modes of representation for these elements.</p><p>On the contrary, when we increase the scale we introduce more details that have little or no treatment in the Cassini map. So we need to extrapolate them.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/847/1*F6FtaIN3sT55Nmuwnp0vtA.jpeg" /><figcaption>City of Paris. Source: gallica.bnf.fr / Bibliothèque nationale de France.</figcaption></figure><p>We take our inspiration from what we see for large cities. The buildings blocks are represented with outline and slightly filled in.</p><p>In the OpenMapTiles we don’t have the blocks. On the other hand, we have the built-up areas and the buildings themselves. We play with these two elements to adjust the representation in function of the zoom level. In all case we fill these polygons with a very small grid pattern.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/423/1*89F5cOlZ6v6ighyMY1XKBg.gif" /><figcaption>Transition between the representations of the buildings.</figcaption></figure><p>We use the built-up areas with a progressive opacity of appearance between zoom levels 11 to 14 and a disappearance between 14 and 14.5. In addition to this, we make buildings appear progressively between zoom levels 14 and 15.</p><p>In the Cassini map, the streets of the big cities are only gap between blocks of buildings. This approach makes it easy to distinguish streets in dense urban fabric where houses are contiguous, but less in modern residential areas where buildings are spaced apart.</p><p>We will therefore make an in-between and keep the layout of the main axes as we already do for the other zoom levels. However, for the streets, service roads and other paths we choose to not trace them in order to reproduce the spirit of the Cassini map with this gap between the buildings.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/1*TM-fh262TBImS45EmSHPYQ.jpeg" /><figcaption>Representation of the name of the streets.</figcaption></figure><p>From zoom 16, we consider that there is enough space between the blocks of buildings to write the names of the streets (even in the historical centers of cities with narrow streets). This addition of street names is a new concept compared to the Cassini map, which does not deal with this at all. A new type of representation has been added here.</p><h3>The realization of the style</h3><h4>Background</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/322/1*v_py3ZhWcLAOi5SqMF1Wrg.jpeg" /><figcaption>Background texture.</figcaption></figure><p>The background of the map is a texture representing old paper. It is highly visible on the map. The Cassini style uses almost no opaque filling and was originally entirely monochrome.</p><h4>Coastline</h4><p>On the Cassini map, the seas are not filled, the paper remains raw. The coastline is decorated on the sea side by figurative waves.</p><p>In everything that follows, “sea” and “ocean” refer to the same thing. In fact, in the Cassini map the Atlantic Ocean is named “Ocean Sea” (<em>Mer Océane</em>).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/925/1*Elg-BmV24PYhnuFubXHtdA.jpeg" /><figcaption>Representation of the coastline on the Cassini map. Source: gallica.bnf.fr / Bibliothèque nationale de France.</figcaption></figure><p>Since we cannot reproduce the original pattern in vector style, we will use another symbology. We will decorate the coast lines with an additional parallel lines.</p><p>Here we want to draw only the coastline without filling the seas. OpenMapTiles provides polygons for oceans and not for continents. This is a common choice; we consult land more often than ocean. This saves processing costs.</p><p>We draw the coastline by a line wide of 3 pixels, followed by a 1 spacing pixel, then a new line wide of 1 pixel. The question then arises is where set this 5 pixels width relative to the coastline.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/386/1*LoIVzduJZpM6uKKy9FZQig.gif" /><figcaption>Difference in the position of the coastline, inside and outside.</figcaption></figure><p>We can center the 3 pixels line on the coastline or center all 5 pixels. If we center on the line of 3 pixels we will have 1.5 pixels inside the coasts and 3.5 outside. This will create an exaggerated effect of the size of the islands. On the other hand, putting the 3 pixels line inside the coasts will reduce the interior surface of the islands and continents.</p><p>We choose to offset the line 3 pixels wide towards the inside of the coasts: 2 pixels inside and 1 outside. So there are 2 pixels inside and 2 pixels outside separated by 1 pixel. To draw offset from the coast line, we use negative and positive offsets depending on the side considered.</p><p>However, this approach does not work for all zoom levels. OpenMapTiles uses two different data sources for the oceans. From zoom 0 to zoom 7, it is an unique single simplified polygon. From zoom 8 and above, the detailed data are from OpenStreetMap. But for this, they are first cut into rectangles by the project <a href="https://osmdata.openstreetmap.de/data/water-polygons.html">OSM Data</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*yUuUDhZUeqXEZmJ4IEbK8Q.png" /><figcaption>Cut of oceans in OSMData.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/505/1*fBi-9fcq6LR4II_MwFBuFg.png" /><figcaption>Contours of ocean polygons.</figcaption></figure><p>This cut allows to have smaller polygons and therefore easier to process. However, they also introduce arbitrary cut indistinguishable from the coastlines. This cut is made to be treated as surface polygons and not outline. If we keep the same drawing strategy for the coastline we get line into the ecean along these arbitrary cut.</p><p>From zoom 8 we can not draw the coastline on the coastline. We have to draw it outside the ocean polygons, i.e. on the land side. These arbitrary cuts in the oceans will then be drawn entirely on the neighbor polygons. This is where our trick comes in; we draw the oceans again, on top, this time filling these polygons with the same texture as the background. This will hide the polygon cut patterns in the oceans, but not the ones on the land side.</p><p>On the other hand, drawing on the land side makes the surface of islands and continents look smaller. From this scale (zoom 8 and more) it will be less noticeable. We can only observe it on small islands and isthmuses.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/1*ofBNAiNiAECS0F7_mUGm5Q.jpeg" /><figcaption>Consequence of a large negative offset.</figcaption></figure><p>To draw outside the ocean polygons, on the land side, we can use a negative offset. Unfortunately large negative offsets introduce a lot of artifacts and give an undesirable result.</p><p>We will start with another technique and take advantage of the fact that we have already chosen to redraw the ocean polygons with the texture of the background to hide undesirable draw.</p><p>We draw a thicker coastline centered on the coastline. We will even draw it three times. The first time for the 3 pixels wide line, we draw a line of 10 pixels wide ((3+1+1) × 2). We hollow it by redrawing a line still centered on the coastline with the background texture of 4 pixels wide (2 × 2). This will leave two parallel lines of 3 pixels wide on either side of the coastline. Finally we draw a line of 2 pixels wide (1 × 2). As the whole is distributed on the coastline and we hide the half on the ocean side, we get the expected result: 1 pixel, 1 skipped pixel and 3 pixels.</p><p>There is still one problem to deal with. We are working in vectorial mode so the zoom levels are passed in a continuous way and not levels by levels as for raster tiles. The two lines to represent the coastline are not positioned in the same way in relation to the coastline depending on the zoom level. For low zooms, the lines are roughly centered on it, but for higher zooms they appear completely inside the coasts (although drawn on the coastline with hidden half). There will therefore be a jump in the coastline when crossing zoom level 8.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/393/1*5ns2kW5tctlsNFxkDW0BEg.gif" /><figcaption>Zoom in on the coastline.</figcaption></figure><p>To avoid this we will gradually move the lines between zoom levels 6 and 8. Here we will not go into technical details and interpolation calculations between the two drawing models, as well as the passing of : “under the mask of the oceans to above”, to be able to draw inside the oceans. All these considerations could suggest great complexity. However, in practice for all the zoom levels, only six layers are needed to achieve this result.</p><p>For a better design, we use discrete dotted lines for the small line of the coastline, its width and opacity vary according to the zoom level. The background of the map being a texture, we use in all cases a slight transparency to bring out the “grain of the paper”.</p><h4>Rivers and water bodies</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/730/1*WBWUG7PxIUCCRoYMxyIlhQ.jpeg" /><figcaption>Representation of the water in Cassini map. Source: gallica.bnf.fr / Bibliothèque nationale de France.</figcaption></figure><p>Unlike the seas, water bodies are filled with a pattern. Large rivers are filled with parallel lines to the riverbanks signifying the water flow. But like the waves of the oceans we cannot easily reproduce this pattern. Moreover, OpenMapTiles does not distinguish between water bodies and rivers. We choose to apply the same pattern everywhere.</p><p>Lakes are represented by a single polygon in OpenStreetMap. However, riverbanks are a series of polygons placed end to end. Representing the entire riverbank by a single polygon would make it too complex to maintain and manipulate. So we have to face the same problem again as arbitrary ocean cuts, but this time to draw the riverbanks. It is necessary to trace the riverbanks, then to hollow out the riverbanks themselves to erase the junctions between the polygons placed end to end, and to finish applying the pattern of the water surfaces.</p><p>There are, however, two ways of representing rivers in the Cassini map, as in OpenStreetMap. With surface for large rivers or with line for smaller ones and when the zoom level becomes low.</p><p>We will represent the water bodies and riverbanks of large rivers in the same way as linear rivers. For linear streams we will add thickness to the line to represent them in the same way as rivers with polygons. We do not represent them in pure linear form, we always represent the riverbanks and the water.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/947/1*iqrExOH7e-ixAKphFhk_Dg.jpeg" /><figcaption>The confluence of <em>the Doubs</em> and the Saône, and a little further downstream the Dheune.</figcaption></figure><h4>Roadway</h4><p>The basic pattern of the representation of the roadway is two parallel lines. A naive approach might be to make two offset plots from the road line, but this produces artifacts. Another approach is to use line casings, which precisely draw two lines on either side of a line. Unfortunately both approaches are not satisfactory at junctions.</p><p>It is necessary to erase the artifacts after drawing the roadway. It is necessary to draw a hollow in all cases. So we will use a 6 pixels thick line and then hollow it with a 2 pixels line with the background texture. In the end, this gives the effect of two parallel lines of 2 pixels with clear junctions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/984/1*s0HCgX-lQHi4LNLLAcfr8g.jpeg" /><figcaption>Without and with additional hollow.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/443/1*cxFy6viV00HWN773FqPb1w.jpeg" /><figcaption>The different types of roadway.</figcaption></figure><p>For the most important class the roadway must be decorated with tree line. These trees will be represented by a single pixel. The idea here is to represent them on both sides at once, using a dotted hollow line. In order to give a slightly more “hand drawn” effect to these dashed lines, we try to make them slightly irregular. We use a pattern of 1 pixel for one tree, then 2.5 pixel spacing, followed by 1.2 pixels wide for the next tree and finally 2.2 pixels wide before starting the pattern again. This “tree” layer must be positioned before the general layout of the roadways to take advantage of the clear by the central hollow of the roadway.</p><h3>Decorations</h3><p>On Cassini, no monster nor muse in the oceans, just boats. The map is decorated with rigging (not yet old) and the names of the bays and seas. In order to capture this spirit, we manually create a complementary dataset of points to anchor the boats and lines to support the names of the seas. This dataset will be a complementary source of vector tiles. We will limit ourselves to decorating the French coasts.</p><p>We scale the boats according to the zoom (this technique is a bad idea, see below). Their size will be adapted according to the zoom level to use a fixed space in the ocean.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/920/1*ZYKm7K6FlmXYHFmRxDOHIA.jpeg" /><figcaption>Fixed-space boats in the ocean.</figcaption></figure><h3>Sprites</h3><p>On a style in Mapbox GL format it is possible to include small graphic elements, <em>sprites</em>, to use them as symbols. A small star for a capital city, an envelope for a post office… or use them as fill patterns: trees for forests or waves for water… sprites in Mabox GL styles are vector images, but converted to bitmap images. While is vector, Mabox GL does not support vector sprites.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/669/1*Wpjl0v-YD8D-VyM_AH2d8w.png" /><figcaption>Bright style sprites</figcaption></figure><p>The goal here is to build a style largely based on images. We hijack and abuse of sprites.</p><p>The sprites in the Mapbox GL style format are both a bitmap image in PNG format and a description in JSON file format that gives the positions of the sprites in the image. The <a href="https://github.com/mapbox/spritezero">spritezero</a> tools is used to produce these two files from a list of vector images in SVG format.</p><p>However, we do not start from vector images but from images that are already in bitmap format. So we will have to create the PNG and JSON files ourselves.</p><p>In our sprites we embed the background texture. It is large and gives the effect of paper. The sprites are usually not made to include large images. We include boats to put in the seas, symbols of cities and villages, and patterns for fresh water and urban areas. These images were taken from the Cassini map itself.</p><p>It is technically possible to scale the sprites during display. But the result is not graphically good with Mabox GL JS. In practice, if you want to display sprites in different sizes, you have to embed these sprites in different resolutions. But we do not do it here. With the exception of the boats, we keep the sprites in their original size. We have only one version of each sprite.</p><h3>Font</h3><p>Cassini map already uses typesetting for all these place names. We choose a font close to the style of the map: “GoudyBookletter1911”, available in the public domain. However, Mapbox GL styles use their own file format for fonts. They are binary files stored in PBF format. Each file contains a range of UTF-8 characters. The goal is to download only the blocks of characters actually used in the display, even if these files are relatively small.</p><p>We convert the font with the <a href="https://github.com/mapbox/node-fontnik">node-fontnik</a> tool created by Mapbox.</p><h3>Hosting the style</h3><p>A style in Mapbox GL format is composed of a style file in JSON format. It describes the draw of objects. It is accompanied by two files for the sprites (PNG and JSON) and the files for the fonts (named <em>glyphs</em>). They are entirely static resources, we can host them on Github.</p><p>Next to that, we have vector tiles for the display of the map data, in OpenMapTiles format, and vector tiles for our additional data decoration (ship positions and support lines for sea and ocean names). Here we use MapTiler services for OpenMapTiles and Mapbox services for complementary vector tiles.</p><h3>Let’s gain a little more height, Cassini style in 3D</h3><p>Let’s extrapolate some more. What if we added an extra dimension to Cassini map? The OpenMapTiles vector tiles contain enough information to extrude the buildings in 3D (in 2.5D to be exact).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/885/1*fBjPDfmBiPnsgO0CTqLGpg.jpeg" /><figcaption>3D Cassini.</figcaption></figure><h3>Conclusion</h3><p>The creation of this vector style in the Mapbox GL format was an opportunity to explore the possibilities and limitations of producing maps largely based on images and with a goal to reproduce an existing style. While modern tools ease representation, they also introduce graphic and aesthetic limitations. The representation of relief and land cover has been ignored here, the issue would require additional work that does not look so simple.</p><blockquote>The style in Mapbox GL format is available on Github.</blockquote><p><a href="https://github.com/makinacorpus/cassini-gl-style">makinacorpus/cassini-gl-style</a></p><blockquote>The online demonstration</blockquote><p><a href="https://makinacorpus.github.io/cassini-gl-style/#11.11/43.6019/1.4356">GL Style Package Preview</a></p><p>This article is an English translation of my own <a href="https://makina-corpus.com/blog/metier/2019/carte-de-cassini-vectorielle">French article from Makina Corpus Blog</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7e1877e0a77b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Création de tuiles pour le web depuis les orthophotographies de la BD Ortho® en Licence Ouverte]]></title>
            <link>https://medium.com/@frederic.rodrigo/cr%C3%A9ation-de-tuiles-pour-le-web-depuis-les-orthophotographies-de-la-bd-ortho-en-licence-ouverte-f47503475128?source=rss-92b83f95ef5c------2</link>
            <guid isPermaLink="false">https://medium.com/p/f47503475128</guid>
            <dc:creator><![CDATA[Frédéric Rodrigo]]></dc:creator>
            <pubDate>Fri, 22 Jun 2018 10:04:06 GMT</pubDate>
            <atom:updated>2018-06-22T12:27:06.209Z</atom:updated>
            <cc:license>https://creativecommons.org/licenses/by-sa/4.0/</cc:license>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uosSQpS-rst1I0E20ZassA.jpeg" /></figure><h3>En entrée : la BD Ortho®</h3><p>L’IGN met à disposition sa BD Ortho® et son ORTHO HR® sous divers format et divers droits de réutilisation. En OpenData ce n’est pas deux mais trois versions de la BD Ortho® qui sont disponibles sous Licence Ouverte.</p><p>- La France entière y compris les DOM sont disponibles dans une version à la résolution réduite à 5 m par pixel : <a href="http://professionnels.ign.fr/bdortho-5m">http://professionnels.ign.fr/BD Ortho-5m</a></p><p>- Pour les régions et départements qui sont co-auteurs avec l’IGN de ces orthophotographies et qui souhaitent les partager en OpenData, elles sont disponibles en résolution de 50 cm ou 20 cm par pixel : <a href="http://professionnels.ign.fr/bdortho-50cm-par-departements">http://professionnels.ign.fr/BD Ortho-50cm-par-departements</a> et <a href="http://professionnels.ign.fr/orthohr">http://professionnels.ign.fr/orthohr</a></p><p>Les données fournies par l’IGN sont des images géoréférencées utilisant des projections différentes en fonction de la zone couverte.</p><p>Quelle que soit la version de la BD Ortho®, chaque département est une archive multipartie au format 7z. Elles contiennent des images géoréférencées au format JPEG2000 ou TIFF. Pour chaque département ces images forment une mosaïque (en d’autre termes, ce sont aussi des tuiles). Plusieurs projections cartographiques sont utilisées en fonction de la zone : métropole et différents DOM.</p><h3>En Sortie : des tuiles utilisables sur des cartes web</h3><p>Le but est de pouvoir servir des tuiles en utilisant cette imagerie. Pour fabriquer ces tuiles il faut reprojeter, mettre à l’échelle et découper les images d’origines. Il y a deux approches possibles pour cela :</p><p>- Précalculer toutes les tuiles. Les traiter à l’avance prend du temps, mais ensuite les servir sur le web est facile : il suffit simplement d’accéder à un fichier image. Il n’y a également pas besoin de conserver les images d’origine.</p><p>- Calcul à la volée. Chaque fois que l’on souhaite visualiser une tuile il faut effectuer des calculs de projection et de mise à l’échelle, cela prend donc du temps.</p><p>Pour fabriquer une seule tuile de zoom faible, il faut réunir beaucoup de données des images de base. Cela prend donc du temps en terme d’accès à toutes ces données et en terme de temps de calcul. Pour les tuiles de niveau de zoom plus élevées, le volume de données étant réduit, les calculs sont plus rapides. Par ailleurs, les tuiles de faible niveau de zoom, couvrant de larges parties du territoire, sont également les plus consultées. Les tuiles les plus longues à calculer sont les plus utilisées, elles sont donc les plus intéressantes à précalculer. Le niveau de zoom à partir duquel on choisit de basculer des tuiles précalculées à des tuiles calculées à la volée dépend de la vélocité souhaitée pour la mise à disposition, du temps que l’on est prêt à accorder au précalcul et du souhait ou non de conserver les images d’origines.</p><p>Le parti prit ici est de tout précalculer.</p><h3>Télécharger la BD Ortho® à 5 m</h3><p>La première étape est d’obtenir les archives, qui sont disponibles ici : <a href="http://professionnels.ign.fr/bdortho-5m">http://professionnels.ign.fr/BD Ortho-5m</a></p><p>Pour télécharger toutes les archives à 2 Mo/s il y en a pour 8 h 30. On se retrouve avec 64 Go d’archives compressées. Il faut ensuite les extraire, cela prend encore une heure et produit 72 Go d’images. On peut ensuite supprimer les 64 Go d’archives, elles ne sont plus nécessaires.</p><h3>Réassembler tous les morceaux : une très (très) grande image</h3><p>Une fois les archives récupérées et extraites, on se retrouve avec 8572 morceaux au format JPEG200 et TIFF.</p><p>Le principe est de fabriquer une très (très) grande image que l’on va reprojeter et mettre à l’échelle puis découper en tuiles. Mais cette image serait bien trop grande pour être manipulé comme un tout unique. Pour la métropole, à 5 m par pixel, cela représente une image de 232 000 pixels par 216 000 pixels. Nous allons donc simuler cette grande image avec <em>gdalbuildvrt</em>. Cet outil va créer une image virtuelle en utilisant les images des mosaïques d’origines. Quand on fait effectue calculs sur cette image virtuelle (découpage, reprojection…) seules les images sous-jacentes de la partie traitée sont utilisées. Cette image virtuelle est prise en charge par tous les outils basés sur GDAL (Qgis, MapServer…).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/407/1*alaPEgYeftwt3vx_9hEOqg.png" /><figcaption>La couverture d’une des images des mosaïques.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/407/1*t7Osgk-e0brDiw8xqo_Paw.png" /><figcaption>Un extrait de cette image en pleine résolution de 5 m par pixel.</figcaption></figure><p>En utilisant <em>gdalbuildvrt</em> nous construisons pour chacune des zones, utilisant une projection différente, un descripteur d’image virtuelle.</p><p>Pour la métropole bien que tout soit en Lamber93 dans les données fournies par l’IGN, les définitions des projections dans les fichiers ne sont pas toutes identiques. Il est nécessaire de forcer l’utilisation de projections différentes. Bien qu’anormal, cela va quand même fonctionner. Par ailleurs les mosaïques des départements débordent largement de leur limites et sont posées sur fond blanc. Il est donc nécessaire d’en tenir compte en supprimant le fond blanc car l’image virtuelle est l’empilement de toutes les mosaïques individuelles, et par la même de toutes les images individuelles des mosaïques.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/779/1*ttBoN7gPoD6_trLdBNdpoQ.png" /><figcaption>Toute la mosaïque pour le département de la Gironde.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*EUpheEVIWQMlsxs9fy6k-w.png" /><figcaption>Aperçu de la même mosaïque dans la projection finale souhaité.</figcaption></figure><p>On crée un descripteur d’image virtuelle pour chacune des projections.</p><h3>Des tuiles pour tous</h3><p>L’objectif final est d’obtenir des tuiles pour chaque niveau de zoom dans une seule et même projection adaptée au tuilage mondial. C’est la projection « Pseudo Mercator », popularisée par Google et qui « l’avantage » de rendre la terre plate et carré.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/384/1*xKW_UDNtY1_sCdlLZWp94A.jpeg" /><figcaption>Une pastèque cubique, par solution_63, CC-by, <a href="https://www.flickr.com/photos/solution_63/181465051/in/photostream/">https://www.flickr.com/photos/solution_63/181465051/in/photostream/</a>.</figcaption></figure><h3>Reprojection et mise à l’échelle</h3><p><em>gdal_translate</em> permet de faire des conversions d’images géoréférencées entre des formats et des projections différentes. Il est bien sûr capable de traiter les images virtuelles que l’on a préalablement définit.</p><p>En sortie les tuiles sont des images dans un format classique, on choisit ici JPEG plutôt que PNG. Il est plus adapté à de la photographie et permet une compression avec perte dont on va se satisfaire à la vue du volume de données. Les tuiles en JPEG vont être stockées dans une archive au format MBTiles, format conçu pour cet usage.</p><h4>Niveau de zoom</h4><p>En métropole 5 m par pixel correspondent à un niveau de zoom entre le zoom 14 et le zoom 15. On va donc reprojeter et mettre à l’échelle l’image pour produire les niveaux de zooms 14 et inférieur.</p><p>Pour une même résolution de 5 m par pixel, le niveau de zoom des tuiles n’est pas le même suivant la latitude. Il faut donc ajuster le niveau de zoom que l’on va produire en fonction de la projection.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/383/1*jU7xgmSO9N87y9M9Qs-qlg.png" /><figcaption>Dunkerque au niveau de zoom 16, latitude 51° Nord. © <a href="https://www.openstreetmap.org/copyright">Contributeurs de OpenStreetMap</a>.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/383/1*cGs4oRpZ-ql0umXynNa_5Q.png" /><figcaption>Fort-de-France au niveau de zoom 16, latitude 14°Nord. © <a href="https://www.openstreetmap.org/copyright">Contributeurs de OpenStreetMap</a>.</figcaption></figure><h4>Mise à l’échelle</h4><p>Le processus de mise à l’échelle peut être réalisé avec différents algorithmes. Il faut principalement arbitrer entre la qualité de l’image produite et le temps de calcul que cela va prendre.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/592/1*FjxhNQUx0yjE0L5jCBoNbA.png" /><figcaption>Rendu des différents algorithmes de mise à l’échelle disponibles dans DGAL.</figcaption></figure><p>À noter que les images de base de la BD Ortho® à 5 m sont déjà une mise à l’échelle de la BD Ortho® d’origine. Le choix effectué à l’IGN pour faire cela est de prendre l’algorithme le plus simple et rapide, donc celui qui donne la plus mauvaise qualité d’image (pour ensuite diffuser le résultat en JPEG2000 en utilisant le mode de compression sans perte…).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/255/1*WvO4DKXQqDXoRMO8F0DwFw.png" /><figcaption>Tuile pleine résolution produite en utilisant la BD Ortho® à 5 m. Les rangées de vigne sont défigurées par la mise à échelle trop simple de la BD Ortho® à 5 m.</figcaption></figure><p>Le calcul du MBTiles pour la métropole au niveau de zoom 14 prend 14 h sur un seul CPU.</p><h3>Construction des autres niveaux de zoom</h3><h4>Par miniature</h4><p>La suite GDAL offre l’outil <em>gdaladdo</em>. Il permet de construire la miniature d’une image. Pour du MBTiles on peut se représenter les tuiles d’un niveau de zoom comme la miniature des tuiles du niveau de zoom supérieur. Cette « miniature » peut ensuite être également stockée dans le MBTiles. Le défaut de cette approche est que l’on refait une mise à l’échelle du zoom 14 qui est lui-même une mise à l’échelle et une preprojection de la mosaïques de la DB Ortho® à 5 m qui est elle-même une mise à l’échelle (de mauvaise qualité) de la DB Ortho® d’origine. Bref, le résultat, du fait des traitements multiples, n’est pas vraiment de qualité.</p><h4>Par calcul direct</h4><p>Une autre façon de procéder est d’utiliser <em>gdal_translate</em> pour produire ces autres niveaux de zooms. La qualité de l’image finale est meilleure car il n’y a pas d’étape d’intermédiaire. L’autre avantage est que l’on peut effectuer les calculs en parallèle et non en séquences car tous les niveaux de zoom ont la même image virtuelle comme source.</p><p>On va par contre obtenir un MBTiles par niveau de zoom et non un seul MBTiles pour la pyramide de tuiles. Il va donc falloir réassembler les différents niveaux de zoom dans un seul MBTiles.</p><h3>Production des MBTiles</h3><p><em>gdal_translate</em> ne supporte pas de produire des MBTiles en multi-thread. Il ne peut le faire qu’en utilisant un seul CPU.</p><p>Pour utiliser au mieux la machine et avoir un résultat plus rapidement on va utiliser la commande <em>parallel</em>. Elle prend en entrée une liste de commandes à exécuter et lance ensuite autant de tâches en parallèle qu’il y a de CPU. Dès qu’une tâche est terminée la suivante est démarrée. On va lancer autant de tâches qu’il y a de niveaux de zoom à produire multiplié par le nombre de projections d’origines à traiter.</p><p>Avec 8 CPU la dernière tâche se termine au bout de 20 h. Le résultat est 60 fichiers MBTiles pour un total 8,5 Go. La taille est bien plus réduite que la taille des images d’origine et ce grâce à l’utilisation de la compression JPEG et malgré la génération plusieurs niveaux de zoom.</p><h4>Fusion des MBTiles</h4><p>Les fichiers MBTiles sont en fait des bases de données SQLite qui stockent les images. Il faut copier dans un même MBTiles toutes les images pour une même projection. On pourrait également tout mettre dans un seul MBTiles quelle que soit la projection d’origine, mais garder un MBTiles par zone permet une réutilisation plus facile.</p><h3>Critiques</h3><p>Les départements n’ont pas une teinte uniforme entre eux. On les distingue à faible niveau de zoom.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/632/1*UyLfT8OzfxGmuudFHOcJVw.png" /></figure><p>La BD Orhto® couvre les terres et s’arrête tout de suite après la côte. De plus on peut constater sur l’eau des reflets permettant de distinguer les limites des photographies entres elles. Il faudrait étendre et lisser les surfaces couvertes par l’eau pour obtenir un meilleur aspect visuel.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/544/1*yNG3wAXYJPr45sEQ4U253g.png" /></figure><p>En suivant cette procédure, des tuiles ont été construites jusqu’au niveau de zoom 9, au delà de quoi la France ne représente plus qu’une petite surface isolée entourée de vide. Il vaut mieux alors utiliser une vue plus globale du monde.</p><p>Une pyramide de tuiles libres construitent depuis les images satellites Landsat est justement disponible pour les niveaux de zoom de 0 à 8. Ce MBTiles fait 400Mo et est dans le Domaine Public. Il est disponible ici <a href="https://archive.org/details/landsat">https://archive.org/details/landsat</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/501/1*hkMJ5-Fdl2NXl-W-9uuo9Q.png" /></figure><p>On a utilisé la BD Ortho® à 5 m pour construire le niveau de zoom 14. Pour la moitié des départements il existe des versions OpenData en Licence Ouverte de la BD Orhto® à 50 cm et à 20 cm. Il serait donc intéressant d’en profiter pour créer les niveaux de zoom plus évelés. Cela fera l’objet d’un second article.</p><h3>Ressources</h3><p>La BD Ortho® : <a href="http://professionnels.ign.fr/bdortho-5m">http://professionnels.ign.fr/bdortho-5m</a></p><p>Les scripts de production des MBTiles : <a href="https://github.com/Mapotempo/tiles-bd-ortho">https://github.com/Mapotempo/tiles-bd-ortho</a></p><p>Les MBTiles : <a href="https://www.data.gouv.fr/fr/datasets/pyramide-de-tuiles-depuis-la-bd-ortho-r/">https://www.data.gouv.fr/fr/datasets/pyramide-de-tuiles-depuis-la-bd-ortho-r</a></p><p>La carte glissante : <a href="https://maps.mapotempo.com/styles/satellite-hybrid/#12/42.5744/2.0985">https://maps.mapotempo.com/styles/satellite-hybrid</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f47503475128" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Experiment on switching from SQL to Redis to request OpenStreetMap topological data]]></title>
            <link>https://medium.com/@frederic.rodrigo/pbf2redis-eae7fcada735?source=rss-92b83f95ef5c------2</link>
            <guid isPermaLink="false">https://medium.com/p/eae7fcada735</guid>
            <category><![CDATA[openstreetmap]]></category>
            <category><![CDATA[redis]]></category>
            <category><![CDATA[osmose]]></category>
            <category><![CDATA[tile38]]></category>
            <dc:creator><![CDATA[Frédéric Rodrigo]]></dc:creator>
            <pubDate>Sun, 03 Sep 2017 20:48:59 GMT</pubDate>
            <atom:updated>2017-09-03T20:48:59.594Z</atom:updated>
            <cc:license>https://creativecommons.org/licenses/by-sa/4.0/</cc:license>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*g98zYcE5trhdZsHsYg52EQ.png" /></figure><p>In short. A custom data storage and manually tuned query steps on a database fully in memory should offer better performance than a SQL interpreter with an automatic planner for sub steps of a database on disk with generic structures and indexes.</p><p>The goal is to explore how the tool Osmose-QA, Quality Assurance for OpenStreetMap data can be speedup.</p><h3>SQL vs Redis</h3><p>With SQL databases, the query is send to the server, the data are fetched, assembled, then the result is returned to the caller.</p><p>Redis is a in memory key-value “database” (better called “store”). Commands available are very low level, like “get”, “set” or “delete” on a key. Values can be strings (binary strings), arrays (aka lists), sets or dictionaryies (aka hashs). Operations on values are available like set intersection, set union, array pop or push… Results of operations can be returned to the caller or stored in a key. See the Redis commands like some sort of assembler. Set some values in registers, then run a command, and do it again. No secondary build-in index is available. The unique available index is the primary one on Redis key. The caller program make multiple calls to Redis server to build the aimed result. Lua scripting is possible on the server side, but very limited. It can used to avoid some round-trips between caller and server when there is no need of logic. The logic (condition, loop) is only on caller side.</p><p>We aim to compare SQL on a tuned Osmosis loaded database and Redis for queries on the Paris area.</p><p>Osmosis data in Postgres for the area 6GB, with the spatial PostGis indices 7GB.</p><h3>Load OpenStreetMap data in Redis</h3><p>For each OpenStreetMap objects (nodes, ways, polygons) store the tags as hash in Redis addressed by a Redis key build on object type and id. In addition, for nodes store latitude and longitude, for ways store node ids composing it, for relations store members.</p><p>Add indices to retrieve objects by tags (or by tags plus values). The Redis key is the OpenStreetMap tag key. For each tag key, store a set of object ids using it.</p><p>For the purpose of the test (and hardware limitation) we just index the tags: “highway”, “railway” and “power”.</p><p>Loaded Redis use 4.3GB of memory. There is no kind of spatial index.</p><h3>Port a very simple request from SQL to Redis</h3><p>Goal: locate OpenStreetMap nodes with level crossing tag where there the railway or the highway are not present.</p><pre>Algorithm:<br>    For each level crossing:<br>        Fetch way using this node<br>        Check if there is at least one railway and one highway</pre><h4>SQL</h4><pre>SELECT<br>  nodes.id,<br>  ST_AsText(nodes.geom),<br>  MIN(ways.id)<br>FROM<br>  nodes AS nodes<br>  JOIN way_nodes ON<br>  way_nodes.node_id = nodes.id<br>  JOIN ways AS ways ON<br>  ways.id = way_nodes.way_id AND<br>  ways.tags != &#39;&#39;::hstore AND<br>  ways.tags ?| ARRAY[&#39;highway&#39;, &#39;railway&#39;]<br>WHERE<br>  nodes.tags != &#39;&#39;::hstore AND<br>  nodes.tags?&#39;railway&#39; AND<br>  nodes.tags-&gt;&#39;railway&#39; IN (&#39;level_crossing&#39;, &#39;crossing&#39;)<br>GROUP BY<br>  nodes.id,<br>  nodes.geom<br>HAVING<br>  NOT BOOL_OR(ways.tags?&#39;highway&#39;) OR<br>  NOT BOOL_OR(ways.tags?&#39;railway&#39;)</pre><p>Explain</p><pre>GroupAggregate  (cost=4028.54..4028.58 rows=1 width=244)<br>Filter: ((NOT bool_or((ways.tags ? &#39;highway&#39;::text))) OR (NOT bool_or((ways.tags ? &#39;railway&#39;::text))))<br>-&gt; Sort  (cost=4028.54..4028.55 rows=1 width=244)<br>   Sort Key: nodes.id, nodes.geom<br>   -&gt; Nested Loop  (cost=35.89..4028.53 rows=1 width=244)<br>      -&gt; Nested Loop  (cost=35.89..3926.27 rows=12 width=116)<br>         -&gt; Bitmap Heap Scan on nodes  (cost=35.89..3808.93 rows=10   width=108)<br>            Recheck Cond: ((tags ? &#39;railway&#39;::text) AND (tags &lt;&gt;   &#39;&#39;::hstore))<br>            Filter: ((tags -&gt; &#39;railway&#39;::text) = ANY (&#39;{level_crossing,crossing}&#39;::text[]))<br>            -&gt; Bitmap Index Scan on idx_nodes_tags  (cost=0.00..35.88 rows=983 width=0)<br>               Index Cond: (tags ? &#39;railway&#39;::text)<br>         -&gt; Index Scan using idx_way_nodes_node_id on way_nodes  (cost=0.00..11.72 rows=1 width=16)<br>            Index Cond: (node_id = nodes.id)<br>      -&gt; Index Scan using pk_ways on ways  (cost=0.00..8.51 rows=1 width=136)<br>         Index Cond: (id = way_nodes.way_id)<br>         Filter: ((tags &lt;&gt; &#39;&#39;::hstore) AND (tags ?| &#39;{highway,railway}&#39;::text[]))</pre><p>Execution time: cold run : 15 s, hot run : 160 ms (second run with disk cached in memory).</p><h4>Redis</h4><p>The Redis client is in Ruby.</p><pre># Get all node with railway=level_crossing or railway=crossing and store it in register REG1<br>redis.sunionstore(REG1, &#39;Node:Key:railway:Value:level_crossing-&gt;nids&#39;, &#39;Node:Key:railway:Value:crossing-&gt;nids&#39;)</pre><pre># store it in register REG1<br>redis.sunionstore(REG1, &#39;Node:Key:railway:Value:level_crossing-&gt;nids&#39;, &#39;Node:Key:railway:Value:crossing-&gt;nids&#39;)</pre><pre># For each node<br>redis.sscan_each(REG1) { |nid|<br>  r = redis.pipelined {<br>    # Intersect the list of ways ids using this node with the list of ways using highway and railway tags, sotre in registers REG2 and REG3<br>    redis.sinterstore(REG2, &quot;Node:#{nid}-&gt;wids&quot;, &#39;Way:Key:highway-&gt;wids&#39;)<br>    redis.sinterstore(REG3, &quot;Node:#{nid}-&gt;wids&quot;, &#39;Way:Key:railway-&gt;wids&#39;)</pre><p>Execution time: 250 ms.</p><p>The results for the in memory data are of the same magnitude. Maybe the goal was “too simple”, lets try with something just “simple”.</p><p>Note: I know the SQL query and the Redis one does not return exactly the same result. A good point to the first one to find the difference.</p><h3>Port a more complex query, but still a simple one</h3><p>Goal: Find ways tagged with “highway” having common nodes with ways tagged with “power”.</p><h4>SQL</h4><p>The SQL version was tuned in Osmose-QA. First, normal SQL form is not used, the ways have an array of used node ids (in addition of the join table between ways and nodes). We use the intersection of the node ids arrays to find the common nodes. Secondly, the query is speedup by avoiding the join on way_nodes table by using a spatial index on way geometry bounding box.</p><pre>SELECT<br>  highway.id AS highway_id,<br>  powerline.id AS powerline_id<br>FROM<br>  ways AS highway<br>  JOIN ways AS powerline ON<br>    powerline.linestring &amp;&amp; highway.linestring AND<br>    powerline.nodes &amp;&amp; highway.nodes AND<br>    powerline.id != highway.id AND<br>    powerline.tags != &#39;&#39;::hstore AND<br>    powerline.tags?&#39;power&#39; AND<br>    powerline.tags-&gt;&#39;power&#39; IN (&#39;line&#39;, &#39;minor_line&#39;, &#39;cable&#39;)<br>WHERE<br>  highway.tags != &#39;&#39;::hstore AND<br>  highway.tags?&#39;highway&#39;</pre><p>Explain</p><pre>Nested Loop  (cost=127.30..18570.93 rows=1 width=16)<br>  Join Filter: ((powerline.nodes &amp;&amp; highway.nodes) AND (powerline.id &lt;&gt; highway.id))<br>  -&gt; Bitmap Heap Scan on ways powerline  (cost=127.30..13920.64 rows=57 width=736)<br>     Recheck Cond: ((tags &lt;&gt; &#39;&#39;::hstore) AND (tags ? &#39;power&#39;::text))<br>     Filter: ((tags -&gt; &#39;power&#39;::text) = ANY (&#39;{line,minor_line,cable}&#39;::text[]))<br>     -&gt; Bitmap Index Scan on idx_ways_power  (cost=0.00..127.28 rows=3849 width=0)<br>  -&gt; Index Scan using idx_ways_linestring on ways highway  (cost=0.00..81.57 rows=1 width=736)<br>       Index Cond: (powerline.linestring &amp;&amp; linestring)<br>       Filter: ((tags &lt;&gt; &#39;&#39;::hstore) AND (tags ? &#39;highway&#39;::text))</pre><p>Execution time: cold run : 23 min, hot run : 6 min (second run with disk cached in memory).</p><h4>Redis</h4><pre># Loop over ways having the tag &quot;highway&quot;<br>redis.sscan_each(&#39;Way:Key:highway-&gt;wids&#39;) { |wid|<br>  # Fetch nodes id of the way<br>  nids = redis.smembers(&quot;Way:#{wid}-&gt;nids&quot;)<br>  # Add way node ids to register set collecting them<br>  redis.sadd(REG1, nids)<br>}</pre><pre># Loop over ways having the tag &quot;power&quot;<br>redis.sscan_each(&#39;Way:Key:power-&gt;wids&#39;) { |wid|<br>  # Check if it is a powerline<br>  if [d_line, d_minor_line, d_cable].include?(redis.hget(&quot;Way:#{wid}-&gt;tags&quot;, d_power))<br>    # Fetch nodes id of the way<br>    nid = redis.smembers(&quot;Way:#{wid}-&gt;nids&quot;)<br>    # Then add way node ids to the register set collecting them<br>    redis.sadd(REG2, nid)<br>  end<br>}</pre><pre># Intersects the two node ids set and store the result into the register REG3<br>redis.sinterstore(REG3, REG1, REG2)</pre><p>Execution time: 54 s.</p><p>It need tuning to choose the operations order but the result look promising.</p><h4>Redis with Lua</h4><p>One block of code is duplicated and it is executed unconditionally.</p><pre># Fetch nodes id of the way<br>nids = redis.smembers(&quot;Way:#{wid}-&gt;nids&quot;)<br># Add way node ids to register set collecting them<br>redis.sadd(REG1, nids)</pre><p>We can use a Lua micro-script to avoid sending two commands one by one. Since the second is systematically after the first one, we can avoid to send back the result of the first one to the caller program, then resend it to Redis.</p><p>We load a Lua script into Redis, it will be name and callable by a hash.</p><pre>-- Load a Lua script to append to register set the content of an other set<br>redis.call(&#39;sadd&#39;, KEYS[1], unpack(redis.call(&#39;smembers&#39;, KEYS[2])))</pre><p>Then we call it from Ruby</p><pre>redis.evalsha(sadd_smembers, [REG1, &quot;Way:#{wid}-&gt;nids&quot;])</pre><p>Execution time: 32 s.</p><p>So, lot of time was lost in exchange between the caller program and Redis.</p><h3>Redis, Tile38 and spatial index</h3><p>Like in the original SQL we can try to use a spatial index to speedup the process.</p><p>The idea, follow the SQL plan but with Redis. In place of building two very large sets of node ids to intersect then, we can narrow the set of node ids if we are able to know witch ways can potentially intersect an other. That the point of the usage of the spatial index.</p><p>Recently Redis add a support of Geohash to convert the couple latitude and longitude to a hash string. The hash can be inserted in a Redis sorted set. Some simple operations are available using this. Unfortunately this does not work for bounding box, and even worst for bounding box intersection.</p><p>But a Redis similar project dedicated to spatial objects is available: Tile38. It’s so close to the Redis concept than you can use Redis client to connect to a Tile38 database. It offer new operations and type of value : the spatial ones. In particular it can index geometry with R-Tree, avoiding flat scan and intersection on very large Redis set of ids. So, now we have a secondary in memory databases !</p><p>Tile38 with spatial data loaded and indexed: 300MB.</p><p>Bad luck ! Exution time: 59 s.</p><h3>Economies of scale</h3><p>Unfortunately in Osmose-QA software we run lot of SQL queries in batch. e can consider we are always in hot run. But more, because we query the same kind of objects over many queries, we pre-select and pre-index this data in temp tables.</p><p>On a real fly, the last SQL use a temps table with pre-selected “highway” and spatial index on it. With that optimization, the true execution time is: cold: 44 s, hot: 4 s.</p><p>We can do some kind of pre-select (or indexing) with Redis. The common operation we can factorize over Redis queries can be the switch from way ids for a tag to the node ids of ways using a tag.</p><p>With this factorization we can improve the fastest Redis implementation we have from 32 s to 1 s has the longest task is looping over the numerous way ids tagged with “highway”.</p><h3>Memory improvement</h3><p>We focus on the execution time, but we can also reduce memory foot print by removing duplicate strings used by tags. Replace string by an integer and store the string and the integer in a dictionary. Then just store the dictionary as a hash in a key of Redis.</p><p>I think lot of other memory improvement can be done.</p><h3>Is it worth it ?</h3><p>I learned lot of thing doing this experimentation. Osmose-QA need 2 days of computing on 15 servers to analyze of the whole data of OpenStreetMap. It runs in loop. Event small speed improvement have value. Nevertheless using Redis need lot of try and tuning of strategy and operations order. The result code is far less readable than the SQL one, and we try only on simple queries.</p><p>You are still reading ? You’re nice !<br>You understood what I’m talking about ? We’re both lucky !<br>You have idea of improvement ? Amazing !</p><p>The source code: <a href="https://github.com/frodrigo/pbf2redis">https://github.com/frodrigo/pbf2redis</a></p><p><a href="http://osmose.openstreetmap.fr/">Osmose-QA</a>: A tools for analyze the quality of OpenStreetMap data and report issue to the contributors.</p><p><a href="https://wiki.openstreetmap.org/wiki/Osmosis">Osmosis</a>: OpenStreetMap data loader in Postgres/PostGis database.</p><p><a href="http://tile38.com/">Tile38</a>: in-memory statial object store.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=eae7fcada735" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>