Construction of parallel curves in web mapping applications
In the course of working on a web map within the project, the task of displaying metro lines on a map arose. It would seem that in this difficult? In fact - nothing, as long as you do not need to visualize the various routes, physically passing through one place. We encountered such a situation while trying to display the Amsterdam metro lines.
The first thought that comes to mind is simply to duplicate those segments along which several routes pass, slightly shifting them relative to each other, changing the geographical coordinates. However, as a result of such an action, we get lines that merge with each other on small scales, and on large ones, on the contrary, fly apart in different directions, that is, looking at a similar map, it is impossible to understand that these routes physically pass in one place.
A more correct way is that the shift of lines relative to each other should be specified in pixels, taking into account the thickness of the lines. An approximate procedure should be as follows:
')
If more than 2 routes go through the same place, then it makes sense to use negative increments along with positive ones to evenly position the segments in both directions relative to the real route.
The calculation of the coordinates of a segment that is shifted relative to the baseline by a certain distance is essentially the task of finding a parallel curve .
Since the Leaflet cartographic library is used in the web map of the Metro for All project, it was decided to try to find some plug-in to build parallel curves. And such a plugin was found - Leaflet.PolylineOffset , an example .
On a test dataset, everything looks pretty good. However, when trying to draw real data (metro lines), a number of unacceptable artifacts appeared (line overshoots, disappearing lines at certain scale levels), and therefore an attempt was made to search for an alternative way to find parallel curves.
It is worth noting that during the writing of this article, the commit # e2166fa was added to the Leaflet.PolylineOffset code , eliminating most of the above artifacts. However, problems with the display of segments on a small scale remained.
Artifacts when using the Leaflet.PolylineOffset plugin
If you look at the code Leaflet.PolylineOffset, it becomes clear that this is a lightweight plugin that implements including all the mathematics for calculating parallel curves. However, finding parallel curves is not at all a trivial task; moreover, there is no such function even in the JTS Topology Suite . This is what one of the main developers of JTS Topology Suite, Martin Davis, says about this:
Therefore, there is every reason not to trust the algorithm that is used in Leaflet.PolylineOffset.
For your information : the implementation of the function for finding parallel curves is available in the GEOS library, code .
One of the most well-known and functional libraries in JavaScript, designed to perform all sorts of spatial operations on objects in a two-dimensional space - JSTS Topology Suite . This is the JavaScript port of the JTS Topology Suite library mentioned above. However, as already noted, the JTS Topology Suite does not have a function for constructing parallel curves; therefore, it is not found in the JSTS Topology Suite. One could, of course, understand the algorithm implemented in GEOS and transfer it to JavaScript using the appropriate functions of the JSTS Topology Suite, but we will consider another option that is not so precise, but as practice has shown, it is quite enough to solve a specific problem: visualize various routes that physically pass through the same place, without tangible artifacts. Not the fact that the algorithm described below will be acceptable to work with another data set, but all the same - there will be at least some starting point.
In JSTS Topology Suite there is the possibility of building a one-way buffer (in one direction or another, depending on the sign). An example of building a one-way buffer (blue line - the outer ring of the constructed polygon, green - the original line):
Unilateral buffer
Also in the JSTS Topology Suite there is the possibility of constructing a “raw” parallel curve (allowing self-intersection). An example of constructing such a curve (the black line is the “raw” curve, the red dots are its nodes):
"Raw" parallel curve
The final parallel curve (blue) will be recruited from the nodes of the "raw" curve relating to the outer ring of the one-way buffer:
Total parallel curve
The code of the resulting function to calculate a parallel curve:
The code of the entire module of the module can be taken on github . To clone it yourself, run the command:
There are also examples of use.
As a result, we obtained a result that also contains small artifacts at a certain scale level, but not in the same amount as Leaflet.PolylineOffset. No departures and disappearances of the lines are observed.
Result
The first thought that comes to mind is simply to duplicate those segments along which several routes pass, slightly shifting them relative to each other, changing the geographical coordinates. However, as a result of such an action, we get lines that merge with each other on small scales, and on large ones, on the contrary, fly apart in different directions, that is, looking at a similar map, it is impossible to understand that these routes physically pass in one place.
A more correct way is that the shift of lines relative to each other should be specified in pixels, taking into account the thickness of the lines. An approximate procedure should be as follows:
')
- When changing the scale level, we determine the pixel coordinates of the base segment;
- We calculate the increment of the next segment in pixels: if you want the second line to be displayed close to the first without gaps, then the offset should be equal to the line thickness (we assume that all segments have the same width);
- Calculate the coordinates of the new segment, taking into account the increment;
- Draw the resulting segment on the map.
If more than 2 routes go through the same place, then it makes sense to use negative increments along with positive ones to evenly position the segments in both directions relative to the real route.
The calculation of the coordinates of a segment that is shifted relative to the baseline by a certain distance is essentially the task of finding a parallel curve .
Since the Leaflet cartographic library is used in the web map of the Metro for All project, it was decided to try to find some plug-in to build parallel curves. And such a plugin was found - Leaflet.PolylineOffset , an example .
On a test dataset, everything looks pretty good. However, when trying to draw real data (metro lines), a number of unacceptable artifacts appeared (line overshoots, disappearing lines at certain scale levels), and therefore an attempt was made to search for an alternative way to find parallel curves.
It is worth noting that during the writing of this article, the commit # e2166fa was added to the Leaflet.PolylineOffset code , eliminating most of the above artifacts. However, problems with the display of segments on a small scale remained.
Artifacts when using the Leaflet.PolylineOffset plugin
If you look at the code Leaflet.PolylineOffset, it becomes clear that this is a lightweight plugin that implements including all the mathematics for calculating parallel curves. However, finding parallel curves is not at all a trivial task; moreover, there is no such function even in the JTS Topology Suite . This is what one of the main developers of JTS Topology Suite, Martin Davis, says about this:
In fact, it was a tricky to implement goal. I'm still thinking about doing offset lines, though.
Therefore, there is every reason not to trust the algorithm that is used in Leaflet.PolylineOffset.
For your information : the implementation of the function for finding parallel curves is available in the GEOS library, code .
One of the most well-known and functional libraries in JavaScript, designed to perform all sorts of spatial operations on objects in a two-dimensional space - JSTS Topology Suite . This is the JavaScript port of the JTS Topology Suite library mentioned above. However, as already noted, the JTS Topology Suite does not have a function for constructing parallel curves; therefore, it is not found in the JSTS Topology Suite. One could, of course, understand the algorithm implemented in GEOS and transfer it to JavaScript using the appropriate functions of the JSTS Topology Suite, but we will consider another option that is not so precise, but as practice has shown, it is quite enough to solve a specific problem: visualize various routes that physically pass through the same place, without tangible artifacts. Not the fact that the algorithm described below will be acceptable to work with another data set, but all the same - there will be at least some starting point.
In JSTS Topology Suite there is the possibility of building a one-way buffer (in one direction or another, depending on the sign). An example of building a one-way buffer (blue line - the outer ring of the constructed polygon, green - the original line):
Unilateral buffer
Also in the JSTS Topology Suite there is the possibility of constructing a “raw” parallel curve (allowing self-intersection). An example of constructing such a curve (the black line is the “raw” curve, the red dots are its nodes):
"Raw" parallel curve
The final parallel curve (blue) will be recruited from the nodes of the "raw" curve relating to the outer ring of the one-way buffer:
Total parallel curve
The code of the resulting function to calculate a parallel curve:
offsetPoints: function(pts, offset) { var offsetPolyline, ls = new jsts.geom.LineString(this.pointsToJSTSCoordinates(pts)); if (offset != 0) { // Parameters which describe how a buffer should be constructed var bufferParameters = new jsts.operation.buffer.BufferParameters(); // Sets whether the computed buffer should be single-sided bufferParameters.setSingleSided(true); var precisionModel = new jsts.geom.PrecisionModel(); var offsetCurveBuilder = new jsts.operation.buffer.OffsetCurveBuilder(precisionModel, bufferParameters); var offsetCurve = offsetCurveBuilder.getOffsetCurve(ls.points, offset); var offsetBuffer = jsts.operation.buffer.BufferOp.bufferOp2(ls, offset, bufferParameters); var offsetPointsList = []; for (var i=0, l=offsetCurve.length; i<l; i++) { var offsetCurveNode = new jsts.geom.Point(offsetCurve[i]); if (offsetBuffer.touches(offsetCurveNode)) { var offsetPoint = offsetCurve[i]; if (!(isNaN(offsetPoint.x) || isNaN(offsetPoint.y))) { offsetPointsList.push(offsetPoint); } } } offsetPolyline = offsetPointsList; } else { offsetPolyline = ls.points; } return this.JSTSCoordinatesToPoints(offsetPolyline); } The code of the entire module of the module can be taken on github . To clone it yourself, run the command:
git clone --recursive git@github.com:drnextgis/Leaflet.PolylineOffset.git There are also examples of use.
As a result, we obtained a result that also contains small artifacts at a certain scale level, but not in the same amount as Leaflet.PolylineOffset. No departures and disappearances of the lines are observed.
Result
Source: https://habr.com/ru/post/244203/
All Articles