从点计算可能的线

问题描述

我正在检查点位置并检测它们是否在一行中，然后输出包含可能行的对象。问题：

• 这是最好的方法吗？有效的有四个循环？


• 我也在双循环内获得重复的匹配点，什么是最好的方法来删除这些？


• 如果我想要检测形状，例如正方形（90度角），等边三角形（60度角）等等，如果我想要对点数据中的模式进行高级检测，我将如何扩展它？ 90度的一点是1公里，100度的一点是1.5公里，110公里的一点是2公里等等。匹配是：每5度距离增加+ 50公里。

这里有一个js小提琴，里面有我的介绍：

解决方案

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

在点之间没有任何其他关系的情况下（例如知道他们所在的街道），您必须首先考虑线对之间的所有线段点。对于 n 点有 Binomial [n，2] 段，所以如果您可以将启发式添加到避免考虑其中的一些细分。

我们有这些线段，我们可以将每个线段与特定的向量 L（S）在飞机上（我们称之为 L 飞机）。两条线段 S1 和 S2 将是共线的当且仅当 L（S1）= = L（S2）。

L（S）被定义为向量从一些固定的原点 O 到从 S 延伸的（无限）行上的最近点。如果两条线段位于同一条线上，那么它们将共享相同的最近点到 O ，如果不是，它们将不会。因此，现在您可以在上使用空间树，例如。 L 飞机查看哪些线段是共线的。

你可以用下面的公式计算矢量 L（S）这是一个很好的文档记录方法，可以找到一条线上的最近点到另一个点，但这里提供了一个快速提示。

肮脏的细节：当你的出处与任何细分市场共线时，事情就会变糟。你必须处理这种情况。我认为处理这种情况的最好方法是将这些细分放在一边，移动原点，然后将算法重新应用到这些细分。

另外，您希望用于巧合的容差与 O 的距离。

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/

解决方案

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.

这篇关于从点计算可能的线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！