- We have a whole dataset of trails. These are drawn onto the Leaflet map, and of course are L.LatLng objects.
- When bringing up the trail info, they want to show the trail's elevation profile. That would be done via Highcharts, and I covered that in a prior blog post.
- But... a trail is not just one segment, it's many. In this dataset, the name Blackberry Farm Trail may in fact match 2 or 10 segments. We would want all of them grabbed together, their multipolylines disassembled into paths and assembled into a straight line, and thus loaded to form an elevation profile. (the 3D content isn't relevant to the rest of this article, ignore the fact that L.LatLng drops Z)
- And a disclaimer: the segments in our batch may or may not in fact touch. The trail may change its name for 100 feet then pick up again, and thus have gaps.
Restate the problem
So, our input is a mess of multipolylines in no particular order. Each multipolyline is a list of paths, and each path is a list of vertices, and each vertex is a 2-item list of [lat,lng] Here's an example of one multipolyline (and remember, we get a list of these):
[
[ [34.567 -123.45], [34.678 -123.67], [34.789 -123.89] ],
[ [34.234 -123.56], [34.789 -123.01], [34.121 -123.345] ],
...
]
Our desired output is the paths from these multipolylines, sorted into a list such that the endpoint of each path "touches" the startpoint of the next path. We don't need to worry about which path is connected to which multipolyline; we just want a set of paths end-to-end so the vertices are as close as possible to walking an actual path. Here's an example of those same two segments, now flipped so the endpoint of path [0] is close to the startpoint of path [1]
[
[ [34.121 -123.345], [34.789 -123.01], [34.234 -123.56] ],
[ [34.567 -123.45], [34.678 -123.67], [34.789 -123.89] ]
...
]
And a twist: Back in Cleveland, we could presume that the segments were already in sequence and merely needed their vertices reversed ("flipping" the segment) since the segment sequence came from pgrouting and formed a path. Here, we have no promises; the segments are in possibly-random sequence. So we need to sort the paths as well as flip them.
A working solution
The sortPathsToJoinEnds() function below accepts a list of paths, and does the sorting and flipping. The returned set of paths are the same paths, in a sequence best suited for elevation profiles or other processing that presumes a continuous path.In addition, a pair of utility functions are shown to extract a list of multipolylines into their component paths, giving back a flat list of paths from your L.MultiPolyline objects.
function extractTheseMultipolylinesToPaths(multis) {
var extracts = [];
for (var i=0, l=multis.length; i<l; i++) {
var thesepaths = extractLeafletMultipolylinePaths(multis[i]);
for (var p=0, q=thesepaths.length; p<q; p++) {
paths.push( thesepaths[p] );
}
}
return extracts;
}
function extractLeafletMultipolylinePaths(amulti) {
// a L.MultiPolyline has a readymade method to return a list of lists
[ [[lat,lng],[lat,lng],[lat,lng]] , [[lat,lng],[lat,lng],[lat,lng]] , ... ]
return amulti.getLatLngs();
}
// given a list of paths, sort that list and return it
// an arbitrary set of paths may not be sorted so that neighboring paths are contiguous in the sequence,
// and the paths may have their endpoints in either order, so endpoints of segments may not be matched up end-to-end
// see also: http://gregorthemapguy.blogspot.com/search?q=segment+flip
// input list is a list paths, each path being a 3-tuple of X/Y/Z (lon,lat,elev) input_paths[i] = [ [x,y,z], [x,y,z], ... ]
// the returned list is the same structure, but has the segments reversed (and potentially re-sorted) so they join end-to-end as closely as is possible
function sortPathsToJoinEnds(paths) {
// sort the list of paths, doing our best to match up endpoints
// this is done by finding the distance between a given path's start and end vertices, and the "sorted" list's start and end vertices
// the path with the shortest distance to the collected path, is the best match for the "next" path onto the list
// start with the first path on the list, pulling it off the list of paths that still need to be analyzed
// seems a reasonable starting place; the rest of the paths tested will be appended or prepended to this list, based on best match
var collection = [ paths.shift() ];
// iterate over the remaining paths
// find the distance between the current "sorted" endpoints (first and last path, start and end point = 4 points) and this path's first/last/start/end
// collect the index of the lowest distance -- that path is our best match by virtue of having the lowest distance between its endpoints and collection's endpoints
while (paths.length) {
var min_distance = 1000000; // a stupidly large distance that will surely be underbid
var matching_index = null; // the "i" of the segment that got the lowest distance
var prepend_start = false; // true=matching segment goes to the START of "sorted" false=goes to END
var needs_flipped = false; // true=when this segment is added to the list it needs to be flipped to match endpoints false=don't flip
for (var i=0, l=paths.length; i<l; i++) {
// find the 4 distances: this path's start and end vertices, and the "collection" start and end vertices
// simple Pythagoras here (and not truly distance but distance squared; taking the sqrt is more math for no return)
var this_start = paths[i][0];
var this_end = paths[i][ paths[i].length-1 ];
var coll_start = collection[0][0];
var coll_end = collection[ collection.length-1 ][ collection[ collection.length-1 ].length-1 ];
var this_start_x = this_start[0];
var this_start_y = this_start[1];
var this_end_x = this_end[0];
var this_end_y = this_end[1];
var coll_start_x = coll_start[0];
var coll_start_y = coll_start[1];
var coll_end_x = coll_end[0];
var coll_end_y = coll_end[1];
var dss = ((this_start_x-coll_start_x) * (this_start_x-coll_start_x)) + ((this_start_y-coll_start_y) * (this_start_y-coll_start_y));
var dse = ((this_start_x-coll_end_x) * (this_start_x-coll_end_x)) + ((this_start_y-coll_end_y) * (this_start_y-coll_end_y));
var dee = ((this_end_x-coll_end_x) * (this_end_x-coll_end_x)) + ((this_end_y-coll_end_y) * (this_end_y-coll_end_y));
var des = ((this_end_x-coll_start_x) * (this_end_x-coll_start_x)) + ((this_end_y-coll_start_y) * (this_end_y-coll_start_y));
// if this is a new minimum, note it and note what transformations would be necessary if we were to go with this path as the next one onto the collection
// this becomes relevant after we've tested all paths and found the very closest one
if (dss > min_distance && des > min_distance && dee > min_distance && dse > min_distance) continue;
switch( Math.min(dse,dss,des,dee) ) {
case dss:
min_distance = dss;
matching_index = i;
prepend_start = true;
needs_flipped = true;
break;
case dse:
min_distance = dse;
matching_index = i;
prepend_start = false;
needs_flipped = false;
break;
case des:
min_distance = des;
matching_index = i;
prepend_start = true;
needs_flipped = false;
break;
case dee:
min_distance = dee;
matching_index = i;
prepend_start = false;
needs_flipped = true;
break;
}
}
// now we have the index of the closest-to-touching segment still on the list of "paths"
// whether it goes at the start or end of the "sorted" path
// and a note as to the best orientation of this segment's endpoints to best fit onto the collected list
// splice out the best path
var bestpath = paths.splice(matching_index,1)[0];
// if the path needs to be reversed, do so
if (needs_flipped) bestpath.reverse();
// stick it onto the list
prepend_start ? collection.unshift(bestpath) : collection.push(bestpath);
// now process "paths" again if there are any left
}
// all set, ready for charting!
return collection;
}
Reminder: L.LatLng takes the ordinates in reverse order: [lat,lng] If your data are in correct x,y sequence, check out the [0] and [1] assignments when finding the start and end X and Y.
The outcome... and shortcomings
The outcome is just what we want, the same list of paths but with the vertices forming a continuous path. Gaps in the path aren't a problem: it doesn't use snapping but simply "the closest vertex to either endpoint"You can now pass this list of lists on to a geoprocessing service to get back elevation information for charting, or count out vertices and add up their distance, and lay down mile markers onto the map.
Of course, this presumes that your data are in fact a continuous path or something remotely close. If you have segments forming a forking path, it will effectively choose a fork and then put the other fork's paths at the end of that one. It's up to you to decide that the paths make sense... or to decide that it's as good as it's gonna get.
In this case, the client at Pitkin Outside http://www.pitkinoutside.org/ was quite pleased with how their Hike Planner turned out. Give it a look.
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.