Monday, October 27, 2014

A New Beta!

After a handful of incremental changes, I'm releasing a new Beta! You can access it via the link below the banner above, or by clicking here.

A quick summary of the changes:
  1. Shaded-relief USGS Quads are available (and are now the default). Big thanks to Matt at CalTopo for generously offering to share his seamless tiles!
  2. Route segments are now shown on-the-fly when planning a route. These segments are either shown as straight-line distances with a black dashed line ("un-calculated" segments), or segments of the routed trail highlighted in purple ("pre-calculated" segments)
  3. Distances for each segment are now shown on-the-fly when planning a route
  4. An "Edit this Route" button was added to the route and profile page. This returns you to the planning page, with the existing route entered, and a suitable view chosen, and prevents you from having to start from scratch for tweaks to a route.
  5. Signal processing was added to the distance and elevation change calculations. This is largely empirical, and is aimed at reducing systematic errors in elevation change and distance.
  6. Both the routes and the profiles from complete routes are learned, so that subsequent calculations of that identical route are vastly sped up

Planning a route in the Beta: Shaded-relief USGS Quads, and segment highlighting and distance calculations on-the-fly!
That said, let's dig into the details...

1. USGS 7.5" Quadrangles and shaded-relief tiles
Matt at CalTopo generously offered to share his USFS, shaded-relief, and USGS quad. tiles. So far, I've only integrated the USGS quads and the shaded relief tiles.

The new tiles will be selected as the default, but if you want to return to the Google terrain (or map, or satellite imagery) tiles, there's a control block in the upper right that can be used to do so.

I added the shaded relief as a transparent overlay (at 30% opacity) to all baselayers. This works well on all maps except the Google Map terrain map, which is already shaded, and becomes a little contrasty with the additional shading. I'll probably change inclusion of the shaded-relief to an option at some point. If you hate the shaded-relief, let me know, and I'll make this a higher priority.

I'm thinking about including other baselayers as well. OpenStreetMap is an obvious choice. I'd like to make maps of my own, but that's quite an undertaking.

Baselayer map selection in the upper right-hand corner

2. Route segment highlighting/indication on-the-fly
In the original Sierra Mapper, one of the things I didn't like was that once you had a few yellow vias included in a long route, it was hard to follow the order of the vias, and therefore hard to follow where the route went.

My first stab at rectifying this consisted of connecting the input nodes with straight lines. This worked reasonably well--you could track the order of the input route fairly intuitively.

But then I realized that doing better than that probably wouldn't be that hard. Wouldn't it be great if it could highlight the actual route?

The trouble was that the actual route is determined from a call to the Python code that solves Djikstra's algorithm for the trail network. There's no simple way to do this in real-time (unless all of that code is ported to Javascript--any volunteers?!?).

The brute force method would be to pre-calculate all of the shortest routes, and the array of coordinates that  corresponds with each route.  To do so for all routes between all nodes would require n(n - 1) individual routes and corresponding coordinate arrays, where n is the number of nodes in the network. With the current size of the trail network n = 1,250; n(n - 1) is around 1.5 million.  This would be cumbersome--and unnecessary.

So I settled on brute-forcing the routes, but only on a subsection of all possible routes: routes that connect nodes within two miles of each, and routes that have previously been calculated. In other words, whenever someone calculates a route, the segments of that route are learned, so that in the future, when identical routes are input, the route (and coordinate array) can be recalled. Likewise for all segments between nodes that are within 2 miles (as the crow flies) of each other.

There's definitely some optimization to be done here. The routes are currently saved and loaded from .csv files. This is inherently inefficient. I think a SQL database would be a better way to implement this, but my knowledge of SQL is virtually non-existent. But, at least for the Beta, this approach works...

Route highlighting on-the-fly in King's Canyon: The first segment (from Road's End to Mist Falls has already been calculated, so the route is highlighted in purple. The second segment, from Mist Falls to Sphinx Junction, has not been pre-calculated, so it's shown as a straight line.

3. Segment distances on the fly
Like the route indication on the fly, segment distances (and the cumulative route distance for all segments) are shown on-the-fly during route planning.

The same caveats for pre-calculated vs un-calculated routes apply here, so I won't belabor that again. Essentially, the routes that are pre-calculated have known distances; the routes that aren't pre-calculated have unknown distances.

In an effort to do a little better than to say that "nothing is known for the un-calculated segment length", the straight-line distance between the two nodes is calculated and shown, caveated with a greater-than sign to indicate that this is the minimum possible length of the segment.

The same route planning exercise from above, with the on-the-fly distances shown in the "Entered Route" box on the right. The segment between Road's End and Mist Falls is pre-calculated, so the correct distance of 3.67 miles is shown. The segment between Mist Falls and Sphinx Junction isn't pre-calculated, so the straight-line distance is shown, caveated with a greater-than sign: >2.39 mi. The total distance is the sum of the segment distances, which is still caveated with the greater-than sign (>6.06 mi).

4. The "Edit this Route" button
In the original Sierra Mapper, the browser's "back" button booted you back to the planning page, with an empty route and a view of the entire Sierra Nevada.

Browser "back" buttons still function this way, but in many (most?) cases that one wants to go back, it's to slightly modify the existing route. That's what the "Edit this Route" button was made for.

You'll find it at the bottom of the route/profile page. Clicking on it will take you from your routed/profiled route back to the planning page, but will retain the input node queue, and will select an appropriate map zoom and center. 

The "Edit this Route" button, at the bottom of the route/profile page

5. Signal processing to minimize systematic errors in distances and elevation changes
The method of calculated distance and elevation change--which I haven't thoroughly explained yet on this blog--essentially relies upon accurate route placement, and good elevation data from the USGS.

Errors in both of those lead to errors in the calculated distance and errors in the calculated elevation change. 

Distance changes tend to be systematically short. This is essentially because the NPS shapefiles (and the trail routes as illustrated on USGS quads) used as the main input for trail location tend to omit switchbacks and minor deviations in the route. These small errors accumulate, and result in distances that are short by anywhere between 0% and 10%. Gross errors in trail location should be fixed not by empirical tuning factors, but by fixing the route. But an empirical factor to correct for the lack of "smoothness" in the input trails seemed reasonable. I used 3%--this gave decent agreement for the calculated distances of well-known trails (The Beta calculates the distance of the JMT as 214.02 miles, while 210.4 miles is commonly cited).

Errors in elevation change are slightly more complicated. They occur primarily because a) the trail route contains error, which routes the trail up and down the surrounding terrain erroneously, or b) the underlying elevation data either contains errors, or is of insufficient resolution for these calculations. These errors typically manifest themselves as either large erroneous ascents/descents (in the case of a) ), or fast up-and-down "jaggies", in the case of b).

Again, a) should be rectified by improving trail locations.

To address the errors in b), signal processing was added; the elevation is interpolated to approximately 30 meter resolution (the resolution of the underlying USGS elevation data), and then filtered backwards and forwards with a low-pass Butterworth filter. This tends to reject errors from using trails that have higher resolution than the underlying elevation data. Since the interpolation is done at the resolution of the underlying data, rejection of real elevation changes should be minimized. 

6. "Learning" Routes
The signal processing mentioned above introduced measurable slowdown in the performance of the routing algorithm. To counter this, I implemented a change whereby routes that have been previously calculated are no longer re-calculated when a subsequent user follows the link. Doing so was wasteful, anyway.

As a result, viewing a route that has been previously calculated is many times faster than calculation for the first time.

No comments:

Post a Comment