Coming July 1: My 14-part blog series on mobile development

Since winter 2012, I've learned a lot about mobile development using Cordova/Phonegap. I've also learned that a lot of books gloss over some of the more difficult topics such as archiving and signing apps for iOS, some important nuances of app approval for iOS viz-a-viz the FileTransfer API, and how one signs an APK for distribution.

Over the last few months I wrote up 14 postings to the GreenInfo Network Intranet, covering Cordova start to finish, from a basic glossary and installing with npm, to pitfalls of offline tiles and App Store approval.

The first in the series will be July 1.

Hats off to GreenInfo Network my generous employer who supports my learning process, and who allows me to share the benefits with you.

FOSS4G 2014 is in Portland, OR

It's not new news that FOSS4G is in Portland, Oregon, USA this year. For me, this is most welcome since I live about 2 hours away from Portland and have friends who I'd be glad to see (much nicer than a motel).

It's also not news that I'm on the schedule, giving two presentations.
Warning: Some minor spoilers below.

Jumpstart your mobile app

My first dive into mobile app development, was of course using Phonegap (aka Cordova). The result was a starting place for future mobile apps: MobileMapStarter

MobileMapStarter is jQuery Mobile, Leaflet, a Map Settings panel to switch between basemaps and toggline online/offline mode for the map tiles, and a facility for downloading map tiles for that offline capability to work. It's really slick stuff, and is my most popular single project in Github.

More info:  https://github.com/gregallensworth/MobileMapStarter

Regional Conservation Strategy Viewer

The Intertwine Alliance is a conservation-oriented organization, with a regional focus on the Portland-Vancouver region of Oregon and Washington. Their Regional Conservation Strategy (RCS) is an information-packed document outlining conservation goals and strategies, specific regions of interest, and a model of habitat valuation.

This habitat valuation model is used to estimate the possible impact of projects, e.g. if you were to pave here how valuable would that habitat be that we're wrecking? And the RCS Viewer is a browser-based tool for perusing that model, selecting prefab areas or drawing/uploading your own areas, then getting back statistics and pie charts showing how valuable that land is.

And knowing what not to pave, is starting to make a difference.

More info:   http://www.regionalconservationstrategy.org/

See you there?

At least two clients will be there that I know, and it's likely there are more who've not mentioned it to me. It'll be quite cool to meet them outside of work, to learn from others, and of course ... to share my own discoveries and inventions with the world.

Joining line segments end-to-end... in JavaScript

So, a situation came up on a project.

• 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.

I touched upon a topic similar to this back in the Cleveland project. Given a set of linestrings from pgrouting, we needed the segments "flipped" so the vertices were in sequence. For drawing vector lines onto a map, the vertex sequence isn't really relevant, but if you're iterating over vertices to form elevation profiles (or to point out mile markers, or to zoom to "the halfway point" and "the 25% mark") then the sequence does count.

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.

I'm not dead !

My goodness, have I been remiss in posting. March 14 is over three months gone, and was about my rather proud achievement of writing a Dougie-P in PHP. Well, a lot of good stuff has been in the works -- which is why I've been busy.

Some highlights and teasers:

• A 14-chapter series on mobile development with Cordova/Phonegap , starting with a Mac and ending with an app published in the store.
• A re-visitation of my line-joining algorithm, to make a straight line out of a jumbled set of line segments. Combined with Z data and Highcharts, some nice elevation profiles can be had.
• And a word about my upcoming presentations at FOSS4G, which in 2014 is being held in Portland, OR only 2 hours from my home.

Yes, really, I'm not dead! Just working. :)