Find The Length of a Coastline - Programming - Part 3

Sun, 12/17/2017 - 07:56

About a week ago I wrote an article where I hypothesized that I could find the length of a coast-line using an algorithm based on a map or satellite image.

This is part 3 of the programming part of that series.

The task here was to find individual sections of the image that represent islands or land-masses. This way I can target a specific land-mass to be measured and discard the rest. (Ireland, France, The Isle of Mann,...etc). 

Regardless of whether I wanted to target a specific land-mass or simply allow the program to target the largest land-mass was immaterial. The problem was that I needed each land-mass as a set of coordinates in an array. 

Finding the land-masses was easy...getting them into an array was a pain in the neck.

To find each land-mass I simply needed to raster the pixels and when I came across one that triggered land (grey versus blue in the final product but, for this bench test it was an array key that was marked as 1) I ran a path finding algorithm to determine all the pixels in the land mass. Then I would place the results into a multi-dimensional array...."simple".

In an asynchronous language like PHP that would be it. As I looped the array I would run a function to find the land-mass, update the pixel array flagging each pixel as having been found, then subsequent loops would know to discard the found results and move on.

Javascript is synchronous however. The loop would find a section to begin and would parse out the path while simultaneously moving on to the next key in the array. Here it would find another place to start and would begin working from there...Then the program would simultaneously move to , yep, the next key in the array and would start working on it from there.

The result would be a large list of arrays. Some complete and others incomplete...and all of them absolutely useless.

I am, of course, aware that Javascript was synchronous and have dealt with this in the past. Generally I would a complicated list of callbacks or something.

The concept of a "promise" in jQuery for use in Ajax calls have been around for sometime and I use it regularly but, I had not ever used the newly available asynchronous methods now available in Javascript before. 

Interestingly enough, I had just watched a video on asynchronous Javascript a few weeks ago, so it was really just getting myself acquainted with using the new methods.

From a starting point the program looks at each adjoining pixel. The adjoining pixels will start off with a weight of 1, if they are a part of the target set. The program picks a direction and increments the weight of the current position. The next step and subsequent steps are similar. The program looks at all adjoining pixels again and for each direction it counts the weights. The program will move in the direction of the lowest weight that is greater than 0.

When the program has determined that there are no more moves (all pixels are greater than 1) it compares the resulting array to a main array. If the two match then the array is discarded. Ideally this last check will never be necessary. ...

array versus result

The current version is really just a proof of concept. The end result will likely need to be optimized as much as possible as the program will need to be looking through several hundreds or thousands of pixels to find each land-mass. 

I am actually thinking maybe I should send the results to the server to test them using node.js or PHP. This would take the load off the client.

I'll deal with that as it becomes necessary.

The current source for the proof of concept is posted below and the resulting image before and after below that.

And here is a live demo.



var i;
        var LOOP = [];
        var RESULT = [];
        var _I = 0;
        var _L = 0;

        var xy = [
        var yl = xy.length;
        var xl = xy[0].length;
        window.onload = function() {

            'use strict';
            // initialize a Wes Mantooth canvas
            i = $w.canvas.init(document.getElementById('target'));
            // draw the grid
        function run() {
            for(var y=0; y<yl; y++) {
                for(var x=0; x<xl; x++) {
                    if (xy[y][x] == 1) {
            _L = LOOP.length;
            let promise = look(xy,LOOP[_I][0],LOOP[_I][1]);
            promise.then(successCallback, failureCallback);
        function successCallback() {
            if (_I<_L) {
                    let promise = look(xy,LOOP[_I][0],LOOP[_I][1]);
                    promise.then(successCallback, failureCallback);
        function failureCallback(error) {
        async function look(xy,x,y) {
            if (xy[y][x] != 1) {
                console.log('NO NEED TO RUN');
            var RESULTnow = [];
            var obj = {
            obj = move(obj);
            moves = true;
            var j = 0;
            var id = setInterval(function() {
                if(obj.i == 2)RESULTnow.push([obj.x,obj.y]);
                obj = move(obj);

                moves = obj.m;
                if (j > 200) {
                    console.log('MAX LOOPS');
                    moves = false;
                    j = 0;
                if (!moves) {
                    console.log("NO MORE MOVES");
                    var duplicate = false;
                    var rl = RESULT.length;
                    var rnl = RESULTnow.length;
                    for(var j=0; j<rl; j++) {
                        for(var k = 0; k<rnl;k++) {
                            if (RESULTnow[k][0] == RESULT[j][0] && RESULTnow[j][1] == RESULT[k][1]) {
                                duplicate = true;
                    if (!duplicate) {
        function move(obj) {
            var max = 8;
            var moved = false;
            obj.i = obj.xy[obj.y][obj.x];
            var c = obj.xy[obj.y][obj.x] * 10;
            var color = $w.color.rgbToHex(c*2,c*3,200);
            var dirs = [null,null,null,null];
            if (undefined !== obj.xy[obj.y-1] && obj.xy[obj.y-1][obj.x] > 0)dirs[0] = obj.xy[obj.y-1][obj.x];
            if (undefined !== obj.xy[obj.y][obj.x+1] && obj.xy[obj.y][obj.x+1] > 0)dirs[1] = obj.xy[obj.y][obj.x+1];
            if (undefined !== obj.xy[obj.y+1] && obj.xy[obj.y+1][obj.x] > 0)dirs[2] = obj.xy[obj.y+1][obj.x];
            if (undefined !== obj.xy[obj.y][obj.x-1] && obj.xy[obj.y][obj.x-1] > 0)dirs[3] = obj.xy[obj.y][obj.x-1];
            var min = max, dir = 0;
            for(var i = 0; i<4; i++) {
                if (dirs[i] != null)
                    if (dirs[i] < min){
                        min = dirs[i];
                        dir = i;
            if (min < max) {
                switch(dir) {
                    case 0:
                        moved = true;
                    case 1:
                        moved = true;
                    case 2:
                        moved = true;
                    case 3:
                        moved = true;
            if (!moved)obj.m = false;
            return obj;
find shapes in images algorithm