POSTGIS, 테이블 내 가장 가까운 포인트 찾기, 성공적

N개의 포인트가 포함된 테이블이 있고, 각 포인트별 가장 가까운 포인트를 매칭시키고 싶었음

스택오버플로우에는 고정된 1개의 포인트에서 다른 포인트 셋의 거리를 구하는 것이 주된 정보여서 한동안 헤맸는데,

왜 Arc나 Q에서는 흔하게 있는 최근린분석을 왜 기본 함수로 안갖고 있는 것이 의문이긴 함

TRIAL #1

처음으로 작성한 코드는 아무 생각없이 작성했더니 distance matrix를 만드는 코드를 만들게 되어버림

SELECT ST_Distance(a.[shape], b.[shape]))

  FROM [table] a, [table] b

  ORDER BY st_distance

아무 생각없이 짠 코드는 N^2의 시간을 요구하고 LIMIT을 걸어서 보면 절대론 해선 안되겠다는 생각을 하게 됨

TRIAL #2

굳이 distance matrix를 만들 필요가 없으므로 한가지 꼼수를 생각해봤는데,

해당 포인트들을 하나의 멀티 포인트로 변환한다음에 매번 거리 계산을 할 때 자기 자신을 빼고 거리를 재는 방식

결과는 성공적으로 나오긴 하는데 어떤 포인트와 정확히 매칭이 되는지는 모르고 거리만 return함

또한 인덱싱이 되지 않고, 2N의 시간이 걸려 포인트가 많아질수록 연산량이 대폭 증가

WITH point_set 

  AS(SELECT ST_Multi(ST_Union([shape])) 

      FROM [table]

SELECT a.[id], ST_Distance(a.[shape], ST_Difference(b.st_multi, a.[shape]))

  FROM [table] a, point_set b

  ORDER BY st_distance

  

TRIAL #3

KNN을 이용한 거리를 재면 인덱싱이 된다고 해서 이 방법으로 시도

<-> 을 LIMIT 1을 걸어서 최근값 1개만 받아내고, 자기자신을 제외하기 위해 id가 서로 다른 <> 값들을 받아냄

인덱싱이 되어있기 때문에 LIMIT 1로 상당히 빠르게 값을 return 하고,

그 결과를 CROSS JOIN 해서 각 포인트들이 서로 매칭되는 것을 알 수 있음 

SELECT a.mid, a.name_dp, closest_pt.mid, closest_pt.dist

  FROM [table] a

  CROSS JOIN LATERAL

    (SELECT mid, name_dp,

      a.[shape] <-> b.[shape] as dist

      FROM [table] b

      WHERE a.[id] <> b.[id]

      ORDER BY a.[shape] <-> b.[shape]

     LIMIT 1) AS closest_pt

  ORDER BY closest_pt.dist

APPLICATION 

위의 방식을 이용해서 내가 원하는 데이터에 적용해봄

내가 다룰 데이터는 만개 단위의 포인트이므로, 분석을 하고자 하는 지역을 적당한 크기로 자르고 싶었음

따라서 해당하는 좌표값을 찾은 뒤에 적당한 반경을 설정하고 그 영역에 속하는 포인트들 중 

특정 칼럼에 원하는 값을 지닌 포인트들만 골라서 다시 테이블로 만들어 분석함

WITH sampling_table

  AS(SELECT * 

      FROM [table]

      WHERE [column] IN ([target value])

      AND ST_DWithin(

        [shape], 

        ST_SetSRID(ST_MakePoint([X], [Y]), [EPSG]), [radius]))

SELECT a.[id], closest_pt.[id], closest_pt.dist

  FROM sampling_table a

  CROSS JOIN LATERAL

    (SELECT [id],

      a.[shape] <-> b.[shape] as dist

      FROM sampling_table b

      WHERE a.[id] <> b.[id]

      ORDER BY a.[shape] <-> b.[shape]

     LIMIT 1) AS closest_pt

  ORDER BY closest_pt.dist

기존에 10분이 넘게 걸리던 작업이 1분 내로 값이 나옴

기쁨