Как группировать близлежащую широту и долготу и назначать имя/номер этой группе в SQL Server?

Question

У меня есть таблица с ID, LATITUDE, LONGITUDE, COUNTRY_CD и я пытаюсь группы (кластеры) ID вместе в пределах 40 метров и присвоить имя/номер в эту группу. Ex. есть 7 ID снизу, записи находятся на расстоянии до 40 метров и вам нужно назначить имя/номер.

Мой стол имеет 100 K записей широты, долготы по всему миру и будет более 100 кластеров из страны, и я не знаю, сколько кластеров будет в каждой стране.

Я прекрасно разбираюсь в цепях близлежащих точек. Ex, ID1 и ID3 оба «близки» к ID6 (но не друг другу).

create table #temp 
(
    ID varchar(10), 
    LATITUDE [decimal](11, 8), 
    LONGITUDE [decimal](11, 8), 
    COUNTRY_CD [char](2) 
) 

insert into #temp select 'ID1', 10.81583689, 78.61898689, 'IN' 
insert into #temp select 'ID2', 10.81513789, 78.61898789, 'IN' 
insert into #temp select 'ID3', 10.81514889, 78.61894889, 'IN' 
insert into #temp select 'ID4', 10.81523989, 78.61898989, 'IN' 
insert into #temp select 'ID5', 10.81521089, 78.61891089, 'IN' 
insert into #temp select 'ID6', 10.81551189, 78.61891189, 'IN' 
insert into #temp select 'ID7', 10.81551189, 78.61791189, 'IN' 
insert into #temp select 'ID8', 10.81561189, 78.61792189, 'IN' 
insert into #temp select 'ID9', 10.81571189, 78.61793189, 'IN' 

select      
    t1.ID, t2.ID, 
    t1.LATITUDE, 
    t1.LONGITUDE, 
    t1.COUNTRY_CD, 
    --calculate the distance in meters 
    cast(6378137.0 * sqrt(power((radians(t1.LATITUDE) - radians(t2.LATITUDE)), 2) 
     + power((radians(t1.LONGITUDE) - radians(t2.LONGITUDE)) * cos(radians(t1.LATITUDE)), 2)) as integer) as MAPPING_DISTANCE, 
    (row_number() over (partition by t1.ID order by 
       --rank the distance in meters 
       cast(6378137.0*sqrt(power((radians(t1.LATITUDE)-radians(t2.LATITUDE)),2) 
       + power((radians(t1.LONGITUDE)-radians(t2.LONGITUDE))*cos(radians(t1.LATITUDE)),2)) as integer) asc 
      )) as DISTANCE_RANK 
from 
    (select 
     ID, LATITUDE, LONGITUDE, COUNTRY_CD 
    from 
     #temp) t1 
--join the above list of ID to get near by ID 
inner join 
    (select 
      ID, LATITUDE, LONGITUDE, COUNTRY_CD 
     from 
      #temp) t2 on t1.COUNTRY_CD = t2.COUNTRY_CD 
        --this brings ID available in 75 meters radius 
        and (t2.LATITUDE between (t1.LATITUDE - 0.00056) and (t1.LATITUDE + 0.00056)) 
        and (t2.LONGITUDE between (t1.LONGITUDE - 0.00076) and (t1.LONGITUDE + 0.00076))  
        --distance between t1 co-ordinates and t2 co-ordinates in meters 
        and (cast(6378137.0*sqrt(power((radians(t1.LATITUDE)-radians(t2.LATITUDE)),2) + power((radians(t1.LONGITUDE)-radians(t2.LONGITUDE))*cos(radians(t1.LATITUDE)),2)) as integer)) <= 40 --limit to 40 meters 
        and t1.ID != t2.ID  --exclude the same ID 

выше запрос приносит идентификатор, которые находятся в пределах 40 метров, но я не знаю, как фильтровать ID те находятся в кластере ?. Ex, 'Cluster_1'?

см этого изображения 2 clusters from above 9 ID

Обратите внимание, что я не буду давать какой-либо конкретную координату в качестве входных данных, но запрос должен автоматически выбрать идентификатор в пределах расстояния от доступных координат в таблице.

Мой ожидаемый результат, как показано ниже,

ID LATITUDE LONGITUDE COUNTRY_CD CLUSTER_NAME 
ID1 10.81583689 78.61898689 IN Cluster_1 
ID2 10.81513789 78.61898789 IN Cluster_1 
ID3 10.81514889 78.61894889 IN Cluster_1 
ID4 10.81523989 78.61898989 IN Cluster_1 
ID5 10.81521089 78.61891089 IN Cluster_1 
ID6 10.81551189 78.61891189 IN Cluster_1 
ID7 10.81551189 78.61791189 IN Cluster_2 
ID8 10.81561189 78.61792189 IN Cluster_2 
ID9 10.81571189 78.61793189 IN Cluster_2 

Любые предложения, как идентификатор фильтра, которые находятся в кластере? Если будет любой другой простой способ сделать это, было бы здорово!

Answer 1

Сначала давайте создадим вычисленный столбец geography, который сохранит координаты местоположения. Мы будем использовать эту колонку, чтобы SQL Server вычислять расстояния для нас:

ALTER TABLE #temp 
ADD Point_Geolocation AS geography::STPointFromText('POINT(' + CAST(LONGITUDE AS VARCHAR(100))+ ' ' + CAST(LATITUDE AS VARCHAR(100)) +')', 4326) PERSISTED 

Во-вторых, давайте создадим таблицу всех близлежащих мест:

IF OBJECT_ID('tempdb..#Nearby_Points') IS NOT NULL DROP TABLE #Nearby_Points 
CREATE TABLE #Nearby_Points (
     ID_1 VARCHAR(10) NOT NULL, 
     ID_2 VARCHAR(10) NOT NULL, 
     PRIMARY KEY (ID_1, ID_2) 
) 

INSERT INTO #Nearby_Points 
(
    ID_1, 
    ID_2 
) 
SELECT t1.ID AS p1_ID 
     ,t2.ID AS p2_ID 
FROM #temp t1 
    INNER JOIN #temp t2 
     ON t1.ID < t2.ID 
WHERE t1.Point_Geolocation.STDistance(t2.Point_Geolocation) < 40 -- Specify distance criteria here 

-- SELECT * FROM #Nearby_Points 

Примечание: с 100k + координаты, мы глядя на приблизительно 5 миллиардов вычислений: (100,000^2)/2. Вышеприведенный запрос может занять некоторое время.

В-третьих, давайте создадим таблицу для хранения наш список кластеров:

IF OBJECT_ID('tempdb..#Clusters') IS NOT NULL DROP TABLE #Clusters 
CREATE TABLE #Clusters(
    Cluster_ID INT NOT NULL, 
    Point_ID VARCHAR(10) NOT NULL, 
    PRIMARY KEY(Cluster_ID, Point_ID) 
); 

-- This index may improve performance a little 
CREATE NONCLUSTERED INDEX IX_Point_ID ON #Clusters(Point_ID); 

Наконец, следующий код:

1. создать новый кластер для первой точки, которая уже не в a кластер.
2. повторно повторяет сканирование таблицы кластеров и добавляет дополнительные точки к существующим кластерам, пока каждый кластер не содержит все точки, которые должны принадлежать ему.
3. Перейдите к шагу 1. выше и повторите, пока не будут созданы новые кластеры.

DECLARE @Rowcount INT 

INSERT INTO #Clusters 
(
    Cluster_ID, 
    Point_ID 
) 
SELECT COALESCE((SELECT MAX(Cluster_ID) FROM #Clusters),0) + 1 
     ,MIN(np.ID_1) 
FROM #Nearby_Points np 
WHERE np.ID_1 NOT IN (SELECT Point_ID FROM #Clusters) 
HAVING MIN(np.ID_1) IS NOT NULL 

SET @Rowcount = @@ROWCOUNT 

WHILE @Rowcount > 0 
BEGIN 

    WHILE @Rowcount > 0 
    BEGIN 

      INSERT INTO #Clusters 
      (
       Cluster_ID, 
       Point_ID 
      ) 
      SELECT Cluster_ID 
        ,Point_ID 
      FROM (
        SELECT np.ID_2 AS Point_ID 
          ,c.Cluster_ID 
        FROM #Nearby_Points np 
         INNER JOIN #Clusters c 
          ON np.ID_1 = c.Point_ID 

        UNION 

        SELECT np.ID_1 
          ,c.Cluster_ID 
        FROM #Nearby_Points np 
         INNER JOIN #Clusters c 
          ON np.ID_2 = c.Point_ID 
      ) vals 
      WHERE NOT EXISTS (
        SELECT 1 
        FROM #Clusters 
        WHERE Cluster_ID = vals.Cluster_ID 
        AND Point_ID = vals.Point_ID 
      ) 

      SET @Rowcount = @@ROWCOUNT 
    END 


    INSERT INTO #Clusters 
    (
     Cluster_ID, 
     Point_ID 
    ) 
    SELECT COALESCE((SELECT MAX(Cluster_ID) FROM #Clusters),0) + 1 
      ,MIN(np.ID_1) 
    FROM #Nearby_Points np 
    WHERE np.ID_1 NOT IN (SELECT Point_ID FROM #Clusters) 
    HAVING MIN(np.ID_1) IS NOT NULL 

    SET @Rowcount = @@ROWCOUNT 
END 

И вуаля:

SELECT * 
FROM #Clusters c 



|Cluster_ID | Point_ID| 
|-----------|---------| 
|   1 | ID1  | 
|   1 | ID2  | 
|   1 | ID3  | 
|   1 | ID4  | 
|   1 | ID5  | 
|   1 | ID6  | 
|   2 | ID7  | 
|   2 | ID8  | 
|   2 | ID9  |