1

I am trying to check the points positions and detect whether they are in a line, then output an object containing the possible lines. Questions:

  • Is this the best way to do it? efficient having four loops?
  • I am also getting duplicates matching points within the double loop, what's the best way to remove those?
  • If I wanted to detect shapes e.g. square (90 degrees angles), equilateral triangle (60 degrees angles) etc, how would I extend it?
  • if I wanted to do advanced detection of patterns in the point data e.g. one point at 90 degrees is 1km, one point at 100 degrees is 1.5km, one point at 110km is 2km etc. The match would be: every 5 degrees the distance increases by +50km. How could I enable that?

Here is a js fiddle of where I got to:

http://jsfiddle.net/kmturley/RAQXf/1/

We know the long and lat co-ordinates of Points 1 - 5. And we want to calculate the red lines between them.

enter image description here

Starting point data:

var points = [
    {
        name: 'Point 1',
        lat: 51.509440,
        long: -0.126985
    },
    {
        name: 'Point 2',
        lat: 51.509453,
        long: -0.126180
    },
    {
        name: 'Point 3',
        lat: 51.510076,
        long: -0.124804
    },
    {
        name: 'Point 4',
        lat: 51.510327,
        long: -0.124133
    },
    {
        name: 'Point 5',
        lat: 51.509440,
        long: -0.124175
    }
];

Here are the functions i'm using:

var utils = {
    distHaversine: function (lon1, lat1, lon2, lat2) { // calculate distance between two points
        var R = 6371; // earth's mean radius in km
        var dLat = this.toRad(lat2 - lat1);
        var dLon = this.toRad(lon2 - lon1);
        lat1 = this.toRad(lat1),
        lat2 = this.toRad(lat2);
        var a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.cos(lat1) * Math.cos(lat2) * Math.sin(dLon / 2) * Math.sin(dLon / 2);
        var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
        var d = R * c;
        return d;
    },
    bearing: function (lon1, lat1, lon2, lat2) { // calculate bearing between two points
        lat1 = this.toRad(lat1);
        lat2 = this.toRad(lat2);
        var dLon = this.toRad(lon2 - lon1);
        var y = Math.sin(dLon) * Math.cos(lat2);
        var x = Math.cos(lat1) * Math.sin(lat2) - Math.sin(lat1) * Math.cos(lat2) * Math.cos(dLon);
        return this.toBrng(Math.atan2(y, x));
    },
    toRad: function (val) { // convert degrees to radians
        return val * Math.PI / 180;
    },
    toDeg: function (val) { // convert radians to degrees (signed)
        return val * 180 / Math.PI;
    },
    toBrng: function (val) { // convert radians to degrees (as bearing: 0...360)
        return (this.toDeg(val) + 360) % 360;
    }
};

And this is as far as I've got:

function calculate(items) {
    var i = 0,
        j = 0,
        accuracy = 2,
        bearings = {};

    // loop through the points and check the distance and bearing of each one
    for (i = 0; i < items.length; i += 1) {
        for (j = 0; j < items.length; j += 1) {
            if (i !== j) {
                var bearing = utils.bearing(items[i].long, items[i].lat, items[j].long, items[j].lat);
                var distance = utils.distHaversine(items[i].long, items[i].lat, items[j].long, items[j].lat);
                var key = Math.round(bearing / accuracy) * accuracy;
                // push both points into the bearing array for the same line
                if (!bearings[key]) { bearings[key] = {}; }
                bearings[key][i] = true;
                bearings[key][j] = true;
                console.log(Math.round(distance * 1000) + 'm', Math.round(bearing) + '°', items[i].name + ' > ' + items[j].name);
            }
        }
    }
    return bearings;
}

function lines(bearings, items) {
    var item = {},
        key = '',
        lines = [];

    // loop though the bearings and create lines
    for (item in bearings) {
        if (utils.size(bearings[item]) > 2) {
            var line = { name: 'Line ' + item + '°', points: [] };
            for (key in bearings[item]) {
                line.points.push(items[parseInt(key)]);
            }
            lines.push(line);
        }
    }
    return lines;
}

var bearings = calculate(points);
var lines = lines(bearings, points);

console.log('--------');
console.log(lines);

Expected output:

var lines = [
    {
        name: 'Line 1',
        points: [
            {
                name: 'Point 1',
                lat: 51.509440,
                long: -0.126985
            },
            {
                name: 'Point 2',
                lat: 51.509453,
                long: -0.126180
            },
            {
                name: 'Point 5',
                lat: 51.509440,
                long: -0.124175
            }
        ]
    },
    {
        name: 'Line 2',
        points: [
            {
                name: 'Point 2',
                lat: 51.509453,
                long: -0.126180
            },
            {
                name: 'Point 3',
                lat: 51.510076,
                long: -0.124804
            },
            {
                name: 'Point 4',
                lat: 51.510327,
                long: -0.124133
            }
        ]
    }
];

Here is a js fiddle of where I got to:

http://jsfiddle.net/kmturley/RAQXf/1/

Kim T
  • 5,770
  • 1
  • 52
  • 79

2 Answers2

0

I prefer to answer this in a language independent way, as it makes the answer more useful to programmers encountering the same problem use a different language.

In the absence of any other relationship between the points (e.g. knowing the streets they're on), you must start by considering all line segments between pairs of points. There are Binomial[n, 2] segments for n points, so it would be good if you could add heuristics to avoid considering some of these segments.

One we have those line segments, we can associate each line segment with a particular vector L(S) on a plane (let's call this the L plane). Two line segments S1 and S2 will be collinear if and only if L(S1) == L(S2).

L(S) is defined as the vector from some fixed origin point O to the nearest point on the (infinite) line extending from S. If two segments are on the same line, then they'll share the same nearest point to O, and if not, they won't. So now you can use a spatial tree such as a quadtree on the L plane to see which segments are collinear.

enter image description here

You can compute the vector L(S) using the well-documented method of finding the nearest point on a line to another point, but here's a quick reminder.

enter image description here

Dirty details: Things go bad when your origin is collinear with any segment. You'll have to handle that case. I think the best way to deal with this case is to put those segments aside, move the origin, and then re-apply the algorithm to just those segments.

Also, the tolerance that you'll want to use for coincidence scales with the distance from O.

Codie CodeMonkey
  • 7,669
  • 2
  • 29
  • 45
  • Ok seems a lot more complicated that I first thought. Are you able to give an example with a few points to help me understand? – Kim T Feb 01 '14 at 11:59
  • This answer gave me some useful javascript implementation ideas http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment – Kim T Feb 04 '14 at 11:34
  • And this one is useful for long lat line sections http://stackoverflow.com/questions/20231258/minimum-distance-between-a-point-and-a-line-in-latitude-longitude – Kim T Feb 04 '14 at 12:04
  • Kim, Glad it was helpful, do you still need an example? I don't code JS, but I suppose I could generate all the segments for my test data, apply `L`, to the quadtree and harvest the results, but I suspect you're already beyond that. – Codie CodeMonkey Feb 04 '14 at 16:33
  • This is my code so far: http://jsfiddle.net/kmturley/cfg2D/2/ to match the points on this image http://i.stack.imgur.com/4nU6j.png – Kim T Feb 04 '14 at 19:43
  • Ok I think there is an issue over long distances compared to google earth. Have created a separate question for it here: http://stackoverflow.com/questions/21563254/distance-from-long-lat-line-segment-wrong-over-long-distances – Kim T Feb 04 '14 at 21:19
  • Aha! So you want lines on a sphere. Maybe surprisingly, the answer is almost the same since every "line" is actually a great circle of the sphere. The great circle is on a plane passing through the center, each with a unique normal (except for direction). An octtree on the plane normals tells you co-circular segments. – Codie CodeMonkey Feb 05 '14 at 15:02
  • I suppose since the earth isn't precisely a sphere and because the distances are large there might be some tweaking you need to do, but perhaps you can adjust. – Codie CodeMonkey Feb 05 '14 at 15:07
0

So i've managed to solve the problem by using this script:

http://www.movable-type.co.uk/scripts/latlon.js

And then the following code:

var p1 = new LatLon(item1.lat, items1.long);
var p2 = new LatLon(item2.lat, items2.long);
var p3 = new LatLon(item3.lat, items3.long);
var distance = Math.abs(Math.asin(Math.sin(p1.distanceTo(p3) / R) * Math.sin(p1.bearingTo(p3).toRad() - p1.bearingTo(p2).toRad())) * R);

I had one major issue: the bearing was in degrees, but needed to be in Radians!

p1.bearingTo(p3).toRad() - p1.bearingTo(p2).toRad()

You can see a working version here (using multiple points to find lines between them):

http://jsfiddle.net/kmturley/Cq2DV/1/

Kim T
  • 5,770
  • 1
  • 52
  • 79