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.

Tuesday, August 19, 2014

More SEKI, More Happy!

Non-trivial update! The entire High Sierra Trail has been added!

..AND Elizabeth and Colby Pass have been connected to Sequoia National Park from Kings Canyon National Park!

..AND Lake South America and the surrounding trails in Sequoia National Park!

Expect more updates to Sequoia National Park in the coming weeks.

The High Sierra Trail--highlighted above--and more!
1,663.9 miles of routable trails, and counting...

Wednesday, July 16, 2014

Minor Update!

It's not much, but a few trails have been added and fixed:
  1. South of Sonora Pass, in Toiyabe National Forest
  2. Between Johnston Meadow and Minaret Lake and Mine, in Inyo National Forest
  3. Between the JMT and Castle and Emily Lakes, in Inyo National Forest
The entire PCT between Crabtree Meadows and Sonora Pass is now mapped! Hooray!

Fixed some missing segments near Sonora Pass (left), and added more trails in Ansel Adams Wilderness (right)
1,582.4 miles of trail, and counting...

Sunday, July 13, 2014

...And we're live!


A momentous day is upon us.

You--my dear friend--are witness to the inaugural post for the Sierra Mapper web application. 

Grab a cup of coffee, cozy up to your phone/tablet/computer, and let's chat a little bit about what Sierra Mapper is.

So what even is this thing? This "Sierra Mapper"?

Patience, dear reader. Like most bloggers, I'm going to tell you a long-winded, self-absorbed story to answer your simple question.

Like many great ideas, this one was born from some blurry amalgam of little pieces of things that I noticed were missing.

From seeing online forum-goers, wordily describing hiking routes in the Sierra Nevada to other forum goers:

"Yeah, head up Paradise Valley, but instead of crossing Wood's Creek, keep going north, and then maybe 1/4 mile before the Baxter Pass junction--that's the first main junction--..."

A highlighted map would communicate this far better. But where could one get a highlighted map?

From trying to plan routes in the Sierra--using spreadsheets, and Tom Harrison maps, and lots and lots of time. And still not being able to easily figure out elevation profiles. Looking in disdain at my DeLorme Topo 9.0 DVD--that should help with this--but it won't run on Linux, which is my OS of choice these days. Damnit. Why isn't there a web app that can do this?

From a lot of clicking in CalTopo:

"I can put my route in here, perfect!" 

" god, this is a lot of clicking"... click-click-clickclick.

How many people have already clicked this route in? How many have to before we find a better way?

The fix--for all those things--and more, is Sierra Mapper.

I still don't get it--what is Sierra Mapper? Some kind of web app?

I actually wasn't finished--I was pausing for dramatic effect.

But yes--it is some kind of web app.

The awesome kind, because it's free, and it's useful, and--while not perfect--does those things above.

An excerpt from the output of a route through Evolution Basin. Highlighted map on the left, beautifully labelled profile on the right. Well done, sir. Well done.

Okay, so how can I use it?

To get to the web app, just click on "Go to the Web App" below the banner on this very blog. Or navigate to  Once there, click on "Instructions" in the lower left for a brief run-down--I hope you find it is quite straightforward.

Is the web app finished?

Oh--oh no. No, no no. Absolutely not.

It is far--very far--from finished. It is a fawn, with knees-knocking--looking at the world with wide-eyed curiosity. It doesn't know what it will become, and the world doesn't know what to think of it yet.

And it's probably pretty buggy.

But it works well enough to share at this point, so I implore you, dear reader, to try it out.

And please leave me feedback--what works, what doesn't work, which trails you'd like to see added--where you'd like it to go from here.

You can contact me either by leaving a comment here, or by using the contact form to the right.

This is getting pretty long winded.

I have much more to say, but I will acquiesce, and defer it to later posts.

Now go forth, learned reader! Map routes and compare routes in the glorious Sierra Nevada with minimal clicking! And gaze in awe at beautiful profiles!