근처 지점을 찾기위한 알고리즘?

StackOverflow https://stackoverflow.com/questions/838344

문제

X, Y 좌표로 수백만 포인트가 주어지면 위치에서 가장 가까운 1000 점을 빠르게 찾기위한 선택 알고리즘은 무엇입니까? 여기에서 "빠르게"는 가정용 컴퓨터에서 약 100ms를 의미합니다.

무자비한 힘은 수백만 개의 곱셈을 한 다음 분류하는 것을 의미합니다. 간단한 Python 앱조차도 1 분 안에이를 수행 할 수 있지만 대화식 응용 프로그램에는 여전히 길다.

포인트의 경계 상자가 알려져 있으므로 공간을 간단한 그리드로 분할 할 수 있습니다. 그러나 포인트는 다소 고르지 않게 분포되어 있으므로 대부분의 그리드 사각형이 비어있을 것이라고 생각합니다. 그러면 갑자기 일부는 포인트의 상당 부분을 포함 할 것입니다.

편집 : 정확할 필요는 없으며 실제로는 매우 부정확 할 수 있습니다. 상위 1000이 실제로 상위 2000 년의 임의의 포인트라면 큰 문제가되지 않을 것입니다.

편집 : 포인트 세트는 거의 변경되지 않습니다.

도움이 되었습니까?

해결책

사용하는 것은 어떻습니까 쿼드 트리?

면적을 사각형으로 나누고, 면적이 낮은 점의 점수가 낮고, 직사각형이 크고, 면적이 점수의 밀도가 높은 경우 사각형이 작습니다. 사각형이 충분히 작거나 충분한 지점이 거의 없을 때까지 각 사각형을 4 개의 하위 사각형으로 재귀 적으로 세분화합니다.

그런 다음 위치 근처의 직사각형의 지점을보고 1000 점을 찾을 때까지 바깥쪽으로 이동할 수 있습니다.

이를위한 코드는 다소 복잡해 질 수 있으므로 간단한 그리드를 먼저 시도하고 충분히 빠른지 확인해야 할 수도 있습니다.

다른 팁

쿼드 트리는 좋지만 BSP 나무 O (로그 N) 시간으로 실행되도록 보장됩니다. 쿼드 트리는 유한 한 경계 볼륨이 필요하다고 생각하며, 많은 포인트가 비교적 작은 공간을 점유 할 때와 같이 쿼드 트리가 비참하게 실패하는 일부 퇴화 케이스가 있습니다.

즉, 쿼드 트리는 구현하기가 더 쉽고 대부분의 일반적인 상황에서 매우 효과적입니다. UPS가 라우팅 알고리즘에 사용하는 것입니다. 왜냐하면 단점은 실제로 도시가 관심있는 지역에 퍼지는 경향이 있기 때문에 실제로 중요한 문제를 일으키지 않기 때문입니다.

쿼드 트리 또는 rtree와 같은 구조를 사용하려고합니다. 이것들은 다차원 인덱스 구조입니다.

키는 좋은 "공간 충전 곡선"을 사용하는 것입니다. 이는 점의 가까이를 정의하는 데 도움이됩니다. 간단한 공간 충전 곡선은 Zorder이지만 Hilbert 곡선과 같은 것에 더 관심이 있습니다.

http://en.wikipedia.org/wiki/space_filling_curve

나는이 물건의 사전 포장 된 구현을 모른다. 나는 최근에 나 자신의 rtree를 2 차원으로 구현하여 대량 로딩 및 검색 만 제공 한 경계 상자를 통해서만)를 지원했습니다.

여기서 한 가지 단점은 포인트가 유한 지역에 포함되어야한다는 것입니다. 유한하지 않은 공간에 맞는 공간 충전 곡선이 있다는 것을 알고 있지만, 나는 그들에 대해 아무것도 모른다.

쿼드 트리 및 BSP 트리 제안 외에도 찾아야합니다. 가장 가까운 이웃 검색. 알고리즘 선택은 기본 데이터 세트에 얼마나 자주 추가하는지를 기반으로합니다. 자주 추가하고 제거하는 경우 트리 솔루션이 우수합니다. 데이터가 더 정적 인 경우 가장 가까운 이웃 검색 및 Voronoi 다이어그램이 훨씬 빠르고 확장 될 수 있습니다.

포인트 세트가 거의 변경되지 않으면 Voronoi 다이어그램 사용을 고려할 수도 있습니다. 그것이 그것이 찾는 데 도움이 될지 잘 모르겠습니다 첫 번째 더 빨리 포인트하지만 다음 999 포인트를 훨씬 쉽게 찾을 수 있어야합니다.

포인트가 데이터베이스 또는 검색 가능한 색인 위치에 있다고 가정합니까? 그렇다면 매우 빠릅니다. 주어진 지점에서 x 및 y 축에 범위를 갖고 해당 범위 내의 모든 위치를 얻을 수 있습니다 (즉, 왼쪽 상단의 상단을 지정하여 대부분의 코너 x (a)와 y (b)와 가장 오른쪽 모서리 x (c) 및 y 하단을 지정합니다. (디)).

그런 다음 y> = b 및 y <= d 및 x> = a 및 x <= c 인 포인트의 쿼리를 수행하십시오. X 및 Y 좌표에 인덱스가 eperatly에 있다고 가정하면 빠르게됩니다. (원점이 왼쪽 상단에서 0,0이라고 가정합니다).

그런 다음 결과 세트 내의 포인트 수가> = 1000이 될 때 까지이 범위를 늘리거나 결과를 늘릴 수 있습니다. 일부 시험 실행을 통해 표준 편차 및 기타 통계 번호를 제시 할 수 있어야합니다. 시작할 직사각형의 크기를 결정하는 데 도움이됩니다. 귀하의 프로그램은 또한 결과에 따라이를 위해 자체적으로 조정할 수 있습니다.

거친 데이터가 있으면 각 지점과 소스 지점 사이의 거리를 해결하기 위해 매우 간단한 수학을 설정합니다.

나는 당신이 Google 에서이 게시물을 찾아서 정말 빠른 결과를 원한다면 가장 빠른 결과가 아니라고 알고 있습니다. Coord가 가까운 위치를 찾고 거리별로 반환합니다.

나는 그것이 누군가를 돕기를 바랍니다 :)

CREATE PROCEDURE [dbo].[getstores] @lat float,  @lng float AS
DECLARE @radius float, @DegToRad float
SET @DegToRad = 57.29577951
SET @radius = 25000
SELECT TOP 10
    name
    ,sto_lat
    ,sto_lng
    ,postcode
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance
FROM store
WHERE (sto_lat >= @lat - (@radius/111))
And (sto_lat <= @lat + (@radius/111))
AND (sto_lng >= @lng - (@radius/111))
AND (sto_lng <= @lng + (@radius/111))
AND (
     ISNUMERIC(sto_lat) = 1
    AND
    ISNUMERIC(sto_lat) = 1
)
ORDER BY distance

참고 : 나는 이것이 이미 최상의 솔루션이 아니라고 언급했습니다. 이 질문 나처럼 Google에서 이것을 찾은 사람을 위해

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top