Calculate possible lines from points

Question

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.

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/

Answer 1

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/

Answer 2

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.

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.

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.