javascript - 从点计算可能的线

Question

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

• 这是最好的方法吗？有四个循环是否高效？
• 我还在双循环中得到重复的匹配点，删除这些点的最佳方法是什么？
• 如果我想检测形状，例如正方形(90 度 Angular )、等边三 Angular 形(60 度 Angular )等，我该如何扩展它？
• 如果我想对点数据中的模式进行高级检测，例如90 度的一点是 1 公里，100 度的一点是 1.5 公里，110 公里的一点是 2 公里，等等。匹配结果是:每 5 度，距离增加 +50 公里。我怎样才能启用它？

这是我到达的地方的 js fiddle :

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 fiddle :

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 相同的最近点，如果没有，他们就不会。所以现在您可以使用空间树，例如 quadtree关于L平面以查看哪些线段共线。

您可以计算向量L(S)使用有据可查的方法查找一条线上到另一​​点的最近点，但这里有一个快速提醒。

肮脏的细节:当你的原点与任何段共线时，事情就会变得糟糕。你必须处理那个案子。我认为处理这种情况的最佳方法是将这些段放在一边，移动原点，然后将算法重新应用于这些段。

此外，您要用于重合的容差会随着距 O 的距离而变化。 .