점의 밀도가 가장 높은 지역을 계산할 수있는 효율적인 알고리즘

Question

점을 위도와 경도로 나타내는 지리적지도가 있다고 가정 해 보겠습니다. 이지도에는 여러 점이 있으며 언제든지 점을 \ 삭제 \ 이동시킬 수 있습니다.

내가 필요한 것은 지역에서 가장 높은 점수를 포함하는 영역, 즉 가장 높은 밀도의 영역을 포함하는 "가장 인기있는 부분"을 얻는 것입니다.

필자는 효율적인 데이터 구조와 변경시 가장 인기있는 부분을 다시 계산하는 알고리즘이 필요합니다. 포인트의 수가 매우 높아질 수 있으므로 계산상의 복잡성과 메모리 복잡성은 최소화되어야합니다.

가장 인기있는 지역의 목록을 내림차순으로 파악하고 유지하고 싶습니다. 가장 인구가 많은 지역부터 인구 밀도가 낮은 지역을 먼저 알고 싶습니다. 크기가 제한된 목록 (예 : 가장 인기있는 100 개 항목)은 괜찮습니다.

물론 하나의 고립 된 점에서 100 % 밀도를 방지하기 위해 최소 면적 (상수로 정의 됨)이 있습니다.

여기서 "영역"의 정의는 점을 포함하는지도상의 인식 가능한 영역입니다. 전체지도가 될 수 있지만, 알고리즘은 물론 핫 스폿으로 보지 말아야합니다 =)

감사합니다! 설명이 필요하면 ...

Answer 1

에서 작동하도록처럼

보인다.

한 가지 일반적인 방법은 '커널 스무딩'입니다. 각 데이터 포인트에 디스크가 있다고 상상해보십시오. 이 영역에서 부드럽게 움직이는 커널은 각 지점에서 겹치는 디스크의 수입니다. 그것은 고정 된 반경의 균일 한 커널을 사용하는 커널 스무딩입니다.

균일 한 커널을 사용할 필요가 없으며 항상 같은 크기 여야합니다. 이제는 "적응 형 대역폭 커널 스무딩"입니다.

그 이유는 유한 한 커널 (무한하지만 Gaussian (aka Normal) 커널을 사용할 수 있지만 연구 영역에 잘릴 수 있음)이있는 경우 특히 쉽게 업데이트 할 수있는 그리드를 제공합니다. 포인트를 추가하거나 제거 할 때마다 밀도에 대한 커널의 기여를 추가하거나 제거합니다.

그래서 문제의 절반 정도입니다. 이제 밀도의 격자가 있습니다. 그런 다음 클러스터링 알고리즘을 사용하여이를 분할하고 어떤 기준에 따라 별도의 피크를 찾을 수 있습니다. a) '피크'를 정의하고 b) 인접 피크와 구분하여 정의합니다. 다른 사람은 이미 클러스터링 알고리즘을 제안했습니다. 통계 패키지 인 "R"에서 클러스터링 기능을 사용하여이 작업을 수행했습니다 (10 년 전). 속도는하지만 강한 점 ... 아니다 당신은 내가도 도움이 될 수 알고리즘 지식 영역이 무엇인지 모르기 때문에, 나는 주로 조사하고 있습니다

Answer 2

사용되는 알고리즘 유형은 점의 분포에 따라 달라집니다. 그룹 분할을 '영역'으로 묶는 것이 훨씬 어려울 수 있습니다. 처음 시작할 때 뭔가가 필요할 것 같으므로 Convex Hulls과 calculating the area of an abritray 2D polygon 및 how to determine if a point is in a polygon을 읽어 보시기 바랍니다.

Answer 3

이것은 설명문으로는 너무 길지만 여기에 "놀고"흥미로운 것을 생각해 낼 수있는 방법에 대한 아이디어가 있습니다. 하지만 한 가지는 확실합니다. 다음은 매우 매우이 될 수 있습니다.

일부 개별 문제로 쉽게 변환 할 수 있습니까? 먼저 모든 좌표를 큰지도에 "정렬"합니다 (각 사각형의 크기를 정의하고 모든 항목 맵을 그러한 점 중 하나로 지정합니다). 그런 다음이 같은 끝낼 것 :

0000000000000000000000000000 
00XX000000000000000000X00000 
00X00000000000000X0000000000 
0000000000000000000000000000 
0000000000000000000000000000 
000000X00000000X000000000000 
0000000000000000000000000000 
000000000000X000000000X00000 
00000000000000000000000X0000 
0000000000000000000000000000 

그런 다음 각 항목을 계산하는 것과 인접 이웃의 숫자입니다 :

0000000000000000000000000000 
0033000000000000000001000000 
0030000000000000010000000000 
0000000000000000000000000000 
0000000000000000000000000000 
0000001000001001000000000000 
0000000000000000000000000000 
0000000000001010000000200000 
0000000000000000000000020000 
0000000000000100000000000000 

그런 다음 당신이 말하는, 당신의 사각형의 크기를 증대 할 수 2로, 따라서지도를 분할 :

09001001000000 
00000000000000 
00100001100000 
00000110002000 
00000002000000 
00000100000000 

를 (지도는 정확하지, 내가 생각하고있는 무슨의 아이디어를 제공하기 위해 돌출 것입니다)

그러면 인접한 이웃 등을 다시 계산합니다.

내게 이렇게하면 "해상도"에 따라 핫스팟을 찾을 수 있습니다. 가장 큰 숫자를 찾아 내면 "핫스팟"이됩니다.

때문에이 경우 :

0000X00000 
0000XX0000 
0000000000 
0000000000 
0Y0Y000000 
0000000000 
0Y0Y000000 

중 하나를 'X'(서로 세 가지 흥미로운 점 닫기) 또는 'Y'서로 가까이 (포 포인츠 가장 인기있는 자리가 될,하지만 그들이있어 수 'X'보다 더 가깝지 않음).

속도가 필요하다고 말했기 때문에이 문제를 개별 문제로 바꾸고 그래프를 배열로 나타낼 것입니다. 그러면 변수 "영역"크기를 허용 할 것입니다. 재미있는 문제는 당신이 통계적으로 '2 차원 밀도 추정'로 알려져하고있다가 (그래서 당신이 보는 곳을 알고) :