从计算可能的点线(Calculate possible lines from points)

我试图检查点的位置，并检测它们是否在一条线上，然后输出包含可能的线的对象。问题：

这是做的最好的方法是什么？高效的具有四个循环？
我也越来越重复的双回路内的匹配点，什么是去除那些最好的方法是什么？
如果我想检测的形状，例如正方形（90度角），等边三角形（60度角）等，我将如何延伸呢？
如果我想要做的在点数据，例如一个点图案先进的检测在90度是1公里，在100度的一个点是1.5公里，在110公里一个点为2km等匹配将是：每5度的距离的增加通过+50公里。我怎么能实现呢？

这是在那里我得到了一个js小提琴：

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

我们知道，1点的长和纬度坐标 - 5.我们要计算它们之间的红线。

起点数据：

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
    }
];

下面是我使用的功能：

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;
    }
};

这是据我已经得到了：

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);

预期输出：

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
            }
        ]
    }
];

这是在那里我得到了一个js小提琴：

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

Answer 1:

我喜欢在一个独立于语言的方式来回答这个问题，因为它使答案程序员遇到相同的问题，使用不同的语言更有用。

在没有点之间的任何其他关系（例如知道他们是在街上），您必须考虑对点之间的所有线段开始。有Binomial[n, 2]为段n点，所以这将是很好，如果你可以添加启发式避免考虑一些这些段。

一个我们有那些线段，我们可以用一个特定的向量中的每个线段关联L(S)在一个平面上（让我们称此为L平面）。两个线段S1和S2将是共线的，当且仅当L(S1) == L(S2)

L(S)被定义为从某一固定原点的矢量O对从延伸的（无限）线的最近点S 。如果两个段是在同一行，那么他们将共享相同的最近点到O ，如果没有，他们不会。所以，现在你可以使用一个空间树，如四叉树的L飞机上看到哪些段共线。

你可以计算矢量L(S)使用发现一行到另一点的最近点的良好记录的方法，但这里有一个快速的提醒。

肮脏的细节：事情变坏时，你的出身是共线的任何部分。你必须处理这种情况。我认为，应对这种情况下，最好的办法是把这些片段放在一边，移动原点，算法然后重新申请只是那些片段。

同样，你要使用符合公差从距离尺度O 。

Answer 2:

所以我一直设法通过使用该脚本来解决这个问题：

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

然后将下面的代码：

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);

我有一个重大问题：轴承是度，但要以弧度需要！

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

你可以在这里看到一个工作版本（使用多个点，发现它们之间的连线）：

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

文章来源: Calculate possible lines from points