Найти координаты в таблице друг от друга на заданном расстоянии - PullRequest
Новая
       43

Найти координаты в таблице друг от друга на заданном расстоянии

0 голосов
/ 29 мая 2018

У меня есть похожие данные в таблице MySql.(Приблизительно 500 тыс.) Записей 

    id  latitude    longitude   
------  ----------  ------------
106837  24.7218925  68.2604037  
106838  24.7218947  68.260412   
106839  24.7219007  68.2604083  
106840  24.721902   68.260403   
106841  24.7219149  68.260416   
106842  24.7219169  68.2604118  
106843  24.7219172  68.2604141  
106844  24.7219269  68.2604097  
106845  24.7219299  68.2604039  
106846  24.7219346  68.2603994  
106847  24.7219409  68.2604027  
106848  24.7219434  68.2604129  
106849  24.721956   68.2603941  
106850  24.7219879  68.2603614  
106851  24.7268579  68.2586257  
106852  24.7283047  68.2575022  
106853  24.7283047  68.2575032  
106854  24.7283141  68.2575256  
106855  24.728375   68.2575342  
106856  24.7283862  68.2575007  
106857  24.7284202  68.2575555  
106858  24.7284468  68.257605   
106859  24.7284485  68.2576076  
106860  24.7284639  68.2576095  
106861  24.7284675  68.2576157

Я хочу отфильтровать все те координаты, которые находятся на расстоянии 100 метров друг от друга.друг друга, но я хочу различить только все те, которые по крайней мере далеко друг от друга на расстоянии 100 метров

Схема: 

CREATE TABLE `coordinates` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `region` varchar(191) COLLATE utf8mb4_unicode_ci NOT NULL,
  `area` varchar(191) COLLATE utf8mb4_unicode_ci NOT NULL,
  `territory` varchar(191) COLLATE utf8mb4_unicode_ci NOT NULL,
  `town` varchar(191) COLLATE utf8mb4_unicode_ci NOT NULL,
  `latitude` varchar(191) COLLATE utf8mb4_unicode_ci NOT NULL,
  `longitude` varchar(191) COLLATE utf8mb4_unicode_ci NOT NULL,
  `completed` tinyint(1) NOT NULL DEFAULT '0',
  `created_at` timestamp NULL DEFAULT NULL,
  `updated_at` timestamp NULL DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=533273 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci

Обновление моего вопроса с изображениями и более подробной информацией для понимания.

Изображение для большей ясности: 6 coordinates on map

Как вы видите, у меня есть 6 координат на карте A, B, C, D, E, F, и у меня есть эти координаты в моей таблице, как показано ниже.

enter image description here

Теперь, каким будет запрос для получения только координат A, B, C и D?Я не хочу получать E и F, потому что E уже ближе к D, а F близко к C, или мы можем сказать, что E, F находятся в радиусе 100 метров от других координат.Я надеюсь, вы поймете мою проблему.

Ответы [ 2 ]

0 голосов
/ 01 июня 2018

Алгоритм 1. Кластерный анализ

Насколько я понимаю, вы хотите найти «скопления» точек.Это очень сложная математическая задача.Это выходит за рамки простых операций SQL.

Алгоритм 2. Исчерпывающий

Так что я упросту задачу.Вы начинаете со списка 500K очков.Вы будете удалять точки из списка до тех пор, пока никакие две точки не будут "очень близки друг к другу". 

Foreach point, A, remaining in the list
    Foreach other point, B, in the list
        If A and B are within 100 meters, delete B from the list.

Давайте проанализируем этот простой алгоритм.

Предположим, что конечный результат будет равен 100К.Нам нужно спросить, сколько раз вам нужно выполнить тест «находится рядом с B.»

Первая точка A должна сравниваться с 500K-1 Bs.
Последняя точка A должна будетсравните примерно с 100K Bs.
Таким образом, общее количество сравнений находится где-то между 100K ^ 2 и 500K ^ 2.Это 10 млрд и 250 млрд .Тьфу.Это может занять несколько недель.

Алгоритм 3: "ведра"

  1. Создайте сетку размером 200 на 200 метров.(Простой SQL; 0,5M операций)
  2. Вычислить, в каком сегменте находится каждая точка. Поместите это в столбец, связанный с точкой.
  3. Для каждого сегмента выполните проверки расстояния, чтобы исключить "очень близко"точки.(Вероятно, только несколько миллионов тестов.)

Теперь вы близки к тому, чтобы получить список очищенных пунктов.Но две близкие точки могут быть в соседних сегментах сетки.Это можно исправить, передвинув сетку на 100 метров на восток, затем на юг, затем на запад.То есть, выполните 3 вышеуказанных шага в общей сложности 4 раза.

Расстояние

Между тем, вы действительно хотите делать арифметику с VARCHAR(191)?Вы делаете, если вы хотите использовать ST_Distance_Sphere().Или вы можете переключиться на DOUBLE и использовать простой алгоритм Пифагора.(Я не знаю, что будет быстрее. Но я знаю, что любой из них будет достаточно точным для принятия решения против крошечных 100 метров.

И, пожалуйста, используйте InnoDB.

0 голосов
/ 29 мая 2018

Вы можете получить это, используя предложение where, где разница больше, чем равно 100, используя ST_Distance_Sphere (g1, g2 [, radius]) Функция mysql 

select *
from tbl
where ST_Distance_Sphere(POINT(Latitude,Longitude), POINT(Latitude,Longitude)) >=100
...