Data structure of the OpenStreetMap project, take a look under the skirt service

Prologue



The OpenStreetMap (OSM) project of open geo-information data under the free license CC-BY-SA (and soon under the Open Database License) is widely known so as not to waste time on its detailed presentation. The main feature of the project and its main advantage compared to any other analogues is the principle of completely open geographic data that can be used by anyone and any way (under the CC-BY-SA license) and can be freely supplemented and specified by any project participant. Like any other data, geographic data is just as structured during storage and processing. In this article I will try to describe the main parts of the OSM data structure, focusing more on accepted data types and representing them in a spatial form.

In general, the entire data structure can be represented schematically in the following figure:
Figure 1. OpenStreetMap data structure
Figure 1. OpenStreetMap data structure.

All data can be divided into three main groups:

  1. data types that describe the object itself as a hierarchical connection, as a kind of spatial entity that has its own final result — the known coordinates of all parts of the object;
  2. the information part is a descriptive characteristic of an object that does not have a direct relationship to the spatial geographical structure of the object (its name, physical, logical and other properties);
  3. service attributes of the object necessary for organizing the process of storing and processing information in the form of a data set, such as a unique identifier, the state of the object in the database, the time the object was last edited in the database, etc.


I will not dwell on the service attributes of objects, I will only note that they are possessed by any independent object in OSM and their specific characteristics and the binding of certain attributes are determined by a specific version of the project API. This is currently an API version 0.6.

Part 1. Basic types of geographic data in OpenStreetMap



There are basically three basic types: a point ( node ), a line ( way ) and a relation ( relation) In this case, I do not use the translation of the data types themselves, but their actual property. The types node, way, and relation themselves are called that way, because that's how they were originally invented. Without exception, all objects in OSM are described by these three data types, after which they are informationally populated with tag combinations. The data model in OSM is built on a hierarchical reference structure, which implies that any subsequent data type does not contain the information contained in the previous types but forms a new entity, referring to a certain set of objects of the previous type. It should also be mentioned that any object in the OSM data structure has its own identifier (ID), unique within this type of object. It is by this identifier that the link to the object itself occurs. Consider the structure of basic types in order.

The first type: a point (node) is a minimal data set that contains information about a pair of coordinates: latitude, longitude (lat, lon) and is basic in a hierarchical model. This is the only data type that stores geographic information itself - coordinates, in the form of latitude and longitude. The OSM data model operates exclusively on two-dimensional data within the WGS84 projection. In the future, we will assume that the coordinates are not the information component of the point object, but an integral part of its structure. In XML notation, an object of this type will look like this:



One point with a unique id of 19 and a pair of coordinates. Coordinates in OSM are used in decimal notation, since it is much easier to handle than coordinate formats with minutes and seconds. The point itself can be an independent object that describes some kind of point object (geometric primitive) or not have its own information component at all, but be part of another object (line or relationship). At the same time, looking a little ahead, I note that a point can simultaneously be an independent object that carries unique information and be part of another object.

Second data type: line (way)- This is a collection of pointers to objects of type a point (node). At a minimum, the line consists of one point, i.e. must contain at least one reference to an existing dot object. A single-point line does not contradict the OSM data structure, but contradicts the concepts of elementary geometry and causes fainting and panic in some data processing algorithms that are too vulnerable, therefore the correct line always contains at least references to two existing point-type objects.

The correct XML notation of an object of the line type will be to describe all the necessary points, followed by the line itself, which lists all its points. In the simplest version, it will look like this:



The order of listing points in a line is important; it characterizes the sequence of points in a line and the direction of the line itself, i.e. the line always has a beginning and an end, even if it is closed (in this case they just coincide). In this example, we first described two points by specifying their coordinates, and then described a line, referring to the id of these points. One point can be included in any number of line objects, and it should be described only once, i.e. a point may be common to two lines, in which case a link to it is contained in both lines. Thus, an integral graph of objects is constructed (most often a road graph for calculating routing), which is a collection of objects (lines) that are connected through their common members (points).

If we want to create another line from the existing points 19 and 23, then we will describe it like this:



In our case, points 19 and 23 are already described above, and point 23 became part of two lines 24 and 48 and became common to them.

Our lines 24 and 48 can be graphically represented in the projection of the Mercator as follows:

figure 2. Two lines
Figure 2. Two lines.

The captions in the figure are the id of the objects: red at the points, black at the lines; the arrow indicates the direction of the line, i.e. both lines end at point 23.

The following data type: relation. In fact, all objects except the point are already relationships, however, lines are highlighted in a separate data type as the most common, describing the basic geometric primitives: lines, polylines and polygons. For all more complex geometric objects, as well as for objects that are not purely geometric, but logical (collections, lists, hierarchies of relationships), a universal data type is designed - relations.

In general, a description of a relationship differs from a line in that a line is always a collection of points, and a relation is a collection of any objects, both points and lines, and other relationships. Therefore, in the relationship is indicated not only the id of the object, but also its type. In the most minimal case, the relation can contain a link to only one object. Using the objects described in the examples above, we can write the relation:



This is a fictitious abstract relation, describing that it includes two objects (members of the relation) - point 24 and line 19 and no longer carry any other information. In the real case, the relationship should have a type specified as a tag (information component) of the relationship object itself, and the members of the relationship should have roles in the links to the objects.

The following is an example of the most common multi-polygon relationship, which describes one closed external polygon of three points with a closed polygon cut from it, also of three smaller points. Geometric primitives (closed and non-closed polygons) and object tags will be discussed later, but for now, attention should be paid to the role parameters of the relationship objects and the presence of a tag describing the type.



The outer role indicates that the given object will be the outer contour of the graphic object, and the inner role indicates that the space inside this object must be excluded from the area of ​​the resulting object. Graphically, our multipolygon will look like this:

Figure 3. Multipolygon
Figure 3. Multipolygon

. Like a line, in a relation, the order in which the members are listed plays a role and is taken into account when using this relation. For example, the relation may be not a geometric figure, but a public transport route (logical diagram), then it includes successively sections of roads along which the bus will move and a list of points - stops at which it stops, therefore the order of including roads in the relation shows the sequence of the route , and the order of stops is the sequence of their visits.

A relation object can be a member of another relation, while the level of nesting and the hierarchy up are not limited by anything. A structural limitation is that the relation object cannot be a member of itself, i.e. contain links to yourself. Recursion in the structure of data types in OSM is unacceptable, although of course there is nothing stopping you from creating such an object and even successfully plugging it into the database.

Having defined the three basic types of objects, we need to introduce the concept of an initial and final object. Primaryan object is any object that is part of any other object, i.e. is a child of at least one object, but itself does not include any other object. In the case of OSM, this is always the point. Or its other definition - the initial object carries in its structure (not in the information part!) Only geographical coordinates and does not contain links to other objects.

The ultimatethe object is the parent hierarchy maximum in the hierarchy, which is not a child in relation to any other object, i.e. not included in any other facility. It can be any of the three types listed: points, lines, relationships. A separate point object that does not enter anywhere, consisting of one object of type a point, is not the initial object, since it is not the beginning of the hierarchy of objects, but is the final object, since the spatial description of the object ends on it.

Part 2. Information scheme of objects



The type of the object describes the geographical (spatial) properties of the object, but does not say anything about the properties of the object itself, its characteristics, purpose and more. For this, there is the information part of the OSM data structure based on the principles of object tagging, i.e. assigning them certain labels and indicating the properties of these labels. Tags are specified as a key = value pair, which in XML notation for our line 24 looks like this:



In this case, we added a property to our line, namely, we specified a highway tag with a value of primary, which in the accepted tagging scheme means that our line is the main road (a class road is below the highway, but above the secondary). There can be any number of tags for any object, which allows you to set all its basic properties and describe all secondary parameters, as well as in any form supplement the object with any information. The tagging scheme in OSM itself is at the same time its most important architectural advantage, since it allows you to describe virtually any object properties, because nobody really limits you in choosing new tags for new properties of objects; and at the same time its most painful place, since any freedom in the choice of designation methods always generates religious wars of various user groups,

If we slightly expand the informational description of our two lines 24 and 48 from the first part, we can get something like:



Line 48 became “Pozharsky Street”, with a speed limit of 60 km / h, the number of lanes equal to two, which has a positive gradient in the direction from point 19 to point 23, which is a secondary road and elevated to the embankment relative to ground level. And line 24 is the main road (with a class higher than secondary) with 6 traffic lanes that has stationary lighting and one-way traffic allowed in the direction from point 22 to point 23, is called "Minina Avenue" and is part of the federal highway M84. Both roads have a common point 23, which is an intersection with a traffic light.

It’s not the task of one article to describe in detail the current tagging agreements, for this there is a separate draft wiki-documentation for fixing the adopted agreements [1]. Let us dwell only on the basic principles of tagging.

  • Any final object must have tags, no matter how long the hierarchy is. Any geographical (spatial) description of an object must end with at least one information property of the object. The tag “type = (multipolygon | *)” is an exception in relation objects, it is not informational, it is part of the structure of which relations are described, i.e. besides it there should be at least one tag. The definition of the final object we gave in the first part.
  • Tags can be completely on any type of object. The presence or absence of tags on one object as part of another object does not affect the necessity or prohibition of the presence of tags on another object, unless of course they logically contradict each other and are not redundant. For example, on a line there may be a tag that it is a road, and on points that are part of this road there may be tags describing point objects at these points - traffic lights, speed bumps, etc., i.e. a point not being a final object (part of the road) can nevertheless describe independently any object.
  • Tags of one object must be unique, i.e. an object cannot contain two identical tags with different values, for example, highway = primary and highway = secondary are not allowed within the same object. Some software can use enumerated types of values, for example highway = primary; secondary can be interpreted as highway = primary and highway = secondary at the same time, but most software interprets as "highway" = "primary; secondary", where "primary; secondary" will not match neither primary nor secondary.
  • Tags describing the properties of an object should only be on the object itself. It sounds so logical that it’s even a little silly, but it really causes a lot of trouble when processing data. The point is that no object properties should be duplicated on the members of this object or on the parent objects. If, for example, we take the “forest” object, described as a closed polygon with the property natural = wood, then it is not necessary to enter this property at every point from which the polygon is built, it is clear even to a small child, but things are much more complicated with relationships and multipolygons. Consider a variant with the same forest, but made not in the form of a polygon, but as a multipolygon, i.e. in the form of a relationship consisting of at least two closed polygons: external (outer role) and internal (inner role). In this case, the natural = wood property should not be on the polygon with the outer role, but on the relation itself. If the relationship includes several objects with the same properties as well as with different ones, then all properties common to all members must be described in the relation itself, i.e. in their parent object, and unique properties on each object whose properties they describe. Returning to the same forest, let's say we have several members with the outer role and some (or not at all, this is also possible) inner members. Moreover, all outer members are a forest, but each of them has its own name, so the natural = wood tag should be on the relation itself, and the unique name tags on each of the outer polygons are different. If the relationship includes several objects with the same properties as well as with different ones, then all properties common to all members must be described in the relation itself, i.e. in their parent object, and unique properties on each object whose properties they describe. Returning to the same forest, let's say we have several members with the outer role and some (or not at all, this is also possible) inner members. Moreover, all outer members are a forest, but each of them has its own name, so the natural = wood tag should be on the relation itself, and the unique name tags on each of the outer polygons are different. If the relationship includes several objects with the same properties as well as with different ones, then all properties common to all members must be described in the relation itself, i.e. in their parent object, and unique properties on each object whose properties they describe. Returning to the same forest, let's say we have several members with the outer role and some (or not at all, this is also possible) inner members. Moreover, all outer members are a forest, but each of them has its own name, so the natural = wood tag should be on the relation itself, and the unique name tags on each of the outer polygons are different. let's say we have several members with the outer role and some (or none at all, this is also possible) inner members. Moreover, all outer members are a forest, but each of them has its own name, so the natural = wood tag should be on the relation itself, and the unique name tags on each of the outer polygons are different. let's say we have several members with the outer role and some (or none at all, this is also possible) inner members. Moreover, all outer members are a forest, but each of them has its own name, so the natural = wood tag should be on the relation itself, and the unique name tags on each of the outer polygons are different.


Part 3. Geometric primitives



The main or at least the most common task for any geographical spatial data is to obtain a graphical representation of the objects described by this data. Simply put, rendering the cards themselves, schemes, plans. Algorithms, rules, styles and methods of rendering maps themselves are already a task of applied software, but it all comes down to rendering the basic geometric primitives that are obtained from objects of the three data types listed in the first part.

Further I will refer to data types in the form of their notation in OSM, i.e. node, way and relation, so as not to be confused with geometric objects by points, lines, polylines, etc., therefore below the line I will mean not the geographical spatial data type of the way in OSM, but the geometric figure - the line, which is the shortest distance between two points on the plane.

So, from what the basic geometric primitives are formed.

A point is one object of type node. Its position in a given projection on the map corresponds to its spatial position in geographical coordinates. One pair of lat / lon coordinates is translated into x / y coordinates of the map, taking into account the projection.

line features


A line is, as we have said, the shortest distance between two points, which corresponds to an object of type way containing two node objects. Any two nodes, since we operate with flat space, and therefore the distance between any two points will always be a straight line.

Polyline- this is a connected sequence of segments, where each segment is one line connected by its end to the beginning of the next segment. The whole sequence is a single integral object. Corresponds to a way object containing three or more nodes. A polyline can be a relation object containing successively connected way objects, where each subsequent way object begins with the node object that ended the previous way. A polyline can be either a way object containing a node or relation containing a way, i.e. cannot be a relation containing both way and node at the same time, however, it can be a relation object containing both way and other relations containing only way objects.

Types of polylines:

Figure 4. Polyline
Figure 4. polyline = way (node1, node2, node3, node4)

figure 5. polyline
figure 5. polyline = relation (way1 (node1, node2), way2 (node2, node3), way3 (node3, node4))

figure 6. polyline
figure 6. polyline = relation2 (way1 (node1, node2), relation1 (way2 (node2, node3) , way3 (node3, node4)))

areal objects


PolygonIs a closed polyline with the last point coinciding with the first. In data types, OSM corresponds to a way object with several (three or more) node objects, while the number of way object members is always one more, because the first node object is repeated twice: at the beginning and at the end of the list. Also, the polygon can be assembled in the form of relation, in which way are included in series, forming a jointly closed loop, i.e. the beginning of each way object corresponds to the end of one other way object. Unlike the polygon in way, the polygon in relation does not duplicate the last object in the enumeration from the first, because for way it is necessary due to the fact that it refers to node objects and only by the fact of duplicating node as the first and last element of the list of members can be judged that it is a closed polygon, and not a linear object of a polyline.

In the case of a polygon described as relation, the type = multipolygon tag on the relation object itself must be indicated. Thus, we determine that we are talking about an area geometric, and not a linear object. Polygon

types:

figure 7. polygon
Figure 7. polygon = way (node1, node2, node3, node4, node1)

figure 8. polygon
figure 8. polygon = relation (way1 (node1, node2, node3), way2 (node3, node4), way3 (node4, node1))

figure 9. polygon
Figure 9. polygon = relation3 (relation1 (way1 (node1, node2, node3), way2 (node3, node4), way3 (node4, node5), way4 (node5, node6, node7)), relation2 (way5 (node7, node8) , way6 (node8, node1)))

compound objects


Composite objects are objects that cannot be described in one primitive way, they are always built on the basis of relation objects with type = multipolygon. Polygons and polylines described as relation can always be simplified to one way object, while a compound object in the most simplified case gives at least two way objects. For example, this is an areal figure (polygon) from which another figure (smaller polygon) is mathematically subtracted. An example of a multipolygon, which is a composite object, with an illustration was given in the first part , in the description of relation objects.

Multipolygons for composite objects, as well as polygons and polylines, can be assembled from simple ways or from other relations, consisting of any number of ways. For such a multipolygon, an indication of the role for each incoming member is mandatory, whether it be a way or relation. At least one member with the outer role. It is an object or objects with this role that determine the main (external) geometric contour of the resulting object. There may not be any objects with the role of inner in the particular case, but then such a multipolygon is an ordinary polygon, simply described redundantly. Objects with the inner role indicate which areas within the outer contour are not part of the resulting shape. For example, this is a clearing in the forest or the courtyard of a house, bounded on all sides by the walls of this house.

All objects with one role in one multipolygon must be assembled into one or more closed contours that do not intersect at the boundaries.

Limitations and conventions for using graphic primitives described as relation



Despite the simplicity, consistency, and scalability of the construction of relation data objects in the real world of OSM, they have a huge number of limitations associated primarily with the limitations of the data processing algorithms of the current software. Therefore, there are a number of agreements on the use of relation objects in certain situations. All of them can be reduced to the following main points:

  1. all areal objects described by relation are multipolygons, i.e. have type = multipolygon and a mandatory role indication for outer | inner members, i.e. polygons in figures 8 and 9 are always only multipolygons;
  2. there are only two linear generally accepted objects described through relation: type = boundary for administrative boundaries and type = route for public transport routes, all other types or relation without types are just collections or lists of objects and are not processed as geometric objects; therefore, if the polylines in Figures 5 and 6 are roads or rivers or any other linear objects, except for borders or routes, and their tags are located on the relation itself, then they will not be processed and taken into account at all;
  3. all other relation objects, except type = multipolygon | boundary | route - are not graphic objects, but are used to combine objects into collections according to some arbitrary common signs that this or that software has the right to consider or ignore at its discretion.


Part 4. What to do to make it better?



So far I have described the existing OSM data structure, complementing which of the theory in reality will not work or is not implemented. Now I will try to formulate the most important structural problem of the OSM data format and what needs to be done to fix this.

As it is not difficult to see from everything described above, in OSM there is no regular data type for areal objects. No at all, is not intended as a class. Either we construct a relation object with a multipolygon, or we make a way in which the last point is equal to the first, but if in the case of a multipolygon we have certainty that the object is areal, then in the case of a simple way we do not have a single way at the structure level data suggest that the object is linear or areal. The territory of the school is, by definition, an areal object, because it describes the occupied area, while the fence around the school’s territory, as an object itself, is an exclusively linear object. But both objects begin and end with the same point. At the data processing level, we can only assume with probability

Such guesses greatly complicate the processing of data, since they require clarification on the information part, and also often lead to the fact that when storing data at the processing stage, part of the data is always duplicated as a linear and as an areal object. In order to reduce the need for guessing, OSM started the vicious practice of adding tags in the type of objects, for example, the area = yes tag is indicated for an area object or for a linear object drawn by a closed polyline with area = no. It seems to be not a panacea, but it’s a complete solution, but this has created and will cause even greater problems, such as attempts to mark the territory of the carriageway as an area object using tags for linear roads while adding area = yes. As a result, it comes at the data processing stage, and in particular when building a routing road graph,

Multipolygons were invented as a solution to describe areal objects, but the truth is with a reference to complex composite objects. Which, on the one hand, kills two birds with one stone (here’s the polygon object type = multipolygon and at the same time operations with subtracting the geometries of the objects), but precisely because of this, this universal data type is not used to describe composite linear objects, except for very rare exceptions. In addition, the multipolygon is not without a structural flaw - the ability to assume its geometric type only by the type of data object.

I believe that in the OSM structure, a separate data type is categorically necessary for designating areal objects and is a primitive that combines only links to basic node objects. This type of data, area, should uniquely describe only objects that have an area and are not linear and always be a closed object, even if the first and last points do not coincide. In turn, none of the linear way objects can in this case describe areal objects, but only linear objects. This will not eliminate the need to make relation relations for complex objects, but it will allow unambiguous interpretation of simple objects, simplifying data processing and eliminating data duplication during processing. And the vast majority of simple objects in the OSM database are compared to relation.

By analogy with area, all relations should also be divided into linear and areal geometric objects and simply arbitrary collections. Considering the small percentage of relation as objects compared to the entire database, you can of course introduce this separation according to the information part, in the same type, adding for example type = polyline by analogy with multipolygon, but for linear objects that are not processed now, but this not as important as the introduction of the basic area primitive.

I hope that after reading you have an idea of ​​the data structure in the OpenStreetMap project.

[1] - Basic rules for tagging objects in OSM, original: http://wiki.openstreetmap.org/wiki/Map_Features and translation: http://wiki.openstreetmap.org/wiki/RU:Map_Features

Also popular now: