如何组合彼此“接近”的纬度/经度点？ [英] How to group latitude/longitude points that are 'close' to each other?

问题描述

我有一个用户提交的纬度/经度点数据库，我试图将关闭点组合在一起。 关闭是相对的，但现在它似乎〜500英尺。

I have a database of user submitted latitude/longitude points and am trying to group 'close' points together. 'Close' is relative, but for now it seems to ~500 feet.

起初，它似乎我可以只是分组具有相同的纬度/经度的行前三个小数位（大致为300x300的框，了解它随着你离开赤道而改变）。

At first it seemed I could just group by rows that have the same latitude/longitude for the first 3 decimal places (roughly a 300x300 box, understanding that it changes as you move away from the equator).

然而，这种方法似乎相当缺乏。 接近度不能与每个小数位代表的距离有显着差异。它不考虑两个位置可能在第三（或任何）小数位中具有不同的数字，但仍在该位置代表的距离内（ 33.1239 和 33.1240 ）。

However, that method seems to be quite lacking. 'Closeness' can't be significantly different than the distance each decimal place represents. It doesn't take into account that two locations may have different digits in the 3rd (or any) decimal place, but still be within the distance that place represents (33.1239 and 33.1240).

我也仔细考虑了点A和点C都是到点B（但不是彼此） - 他们应该分组在一起吗？如果是这样，当点D接近点C（而没有其他点）时会发生什么 - 应该将它分组。当然，我必须确定所需的行为，但是如何实现呢？

I've also mulled over the situation where Point A, and Point C are both 'close' to Point B (but not each other) - should they be grouped together? If so, what happens when Point D is 'close' to point C (and no other points) - should it be grouped as well. Certainly I have to determine the desired behavior, but how would either be implemented?

任何人都可以指出我正确的方向，如何做到这一点，可以使用哪些不同的方法/方法？

我觉得有点像我缺少一些显而易见的东西。

I feel a bit like I'm missing something obvious.

目前数据是一个MySQL数据库，由PHP应用程序使用;然而，如果他们是完成这个的一个关键部分，我对其他存储方法。这里。

Currently the data is an a MySQL database, use by a PHP application; however, I'm open to other storage methods if they're a key part in accomplishing this. here.

推荐答案

有多种方法可以确定两点之间的距离，但是在二维图上绘制点可能需要欧氏距离。如果（x1，y1）代表你的第一个点，而（x2，y2）代表你的第二个点， / p>

There are a number of ways of determining the distance between two points, but for plotting points on a 2-D graph you probably want the Euclidean distance. If (x1, y1) represents your first point and (x2, y2) represents your second, the distance is

d = sqrt( (x2-x1)^2 + (y2-y1)^2 )

对于分组，你可能想使用某种2-D平均值来确定接近的事情是如何相互关联的。例如，如果您有三个点，（x1，y1），（x2，y2），（x3，y3），您可以通过简单的平均来找到这三个点的中心：

Regarding grouping, you may want to use some sort of 2-D mean to determine how "close" things are to each other. For example, if you have three points, (x1, y1), (x2, y2), (x3, y3), you can find the center of these three points by simple averaging:

x(mean) = (x1+x2+x3)/3
y(mean) = (y1+y2+y3)/3

然后你可以看到每个中心的距离，以确定它是否应该是集群的一部分。

You can then see how close each is to the center to determine whether it should be part of the "cluster".

有许多方法可以定义集群，所有这些方法都使用聚类算法。我现在在急忙，没有时间总结，但检查了链接和算法，并希望其他人将能够提供更多的细节。祝你好运！

There are a number of ways one can define clusters, all of which use some variant of a clustering algorithm. I'm in a rush now and don't have time to summarize, but check out the link and the algorithms, and hopefully other people will be able to provide more detail. Good luck!

这篇关于如何组合彼此“接近”的纬度/经度点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！