사각형 내부의 빠른 검색을 위해 2D 포인트 저장

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

문제

나는 많은 2D 포인트가 있고 특정 사각형에있는 것을 빨리 얻고 싶습니다. ''라고합시다. 어떤 점과 'x'는 't'가 't'와 'b'가 바닥 오른쪽 지점과 같은 사각형 내부에서 찾고 싶은 점입니다.

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

나는 STD :: 세트의 끝 부분과 하단을 정렬하는 정렬 functor로 세트를 시도했습니다. 먼저 x 값으로 정렬하면 다음 점이 발견됩니다.

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

이것은 실제로 사각형 내부에 있는지 여부를 찾은 각 지점을 확인해야한다는 것을 의미합니다. 정말 좋지 않습니다.

이것을하는 더 좋은 방법은 무엇입니까?

내 언어는 C ++ (Windows)이며 STL과 부스트를 사용할 수 있습니다.

업데이트

지금까지 답을 읽은 후, 나는 내 문제의 모든 매개 변수를 설명하지 않았다는 것을 알았습니다. 고정 된 사각형이 하나는 없습니다. 런타임에 사용자가 사각형을 설정할 수 있습니다. 이는 포인트 세트를이 업데이트 전에 Artelius가 제안한 모든 포인트를 통해 선형 검색보다 더 효율적이라는 점을 정렬하는 것을 의미합니다. 그래도 나는 여전히 시도해 볼 것입니다! 사용자가 사각형을 설정할 것으로 기대하지 않습니다 매우 잦은. 따라서 구현 노력과 관련하여 그것은 나에게 좋은 솔루션이 될 수 있습니다.

도움이 되었습니까?

해결책

쿼드 또는 r- 트리를 사용하여 포인트를 공간 색인에 저장할 수 있습니다. 그런 다음 사각형이 주어지면 트리의 모든 노드를 겹치는 모든 노드를 찾을 수 있으므로이 서브 세트의 각 지점을 비교하여 사각형에 속하는지 확인해야합니다.

본질적으로, 공간 트리는 검색 공간을 정리하는 데 도움이됩니다.

범위에서 포인트를 분할하는 것과 같은 더 간단한 솔루션을 사용할 수 있습니다. X가 하나의 범위로 0,10, 11,20은 다른 곳으로 말하십시오. 검색 공간을 가지게 할 수있는 모든 솔루션이 도움이됩니다.

다른 팁

참조하십시오 이 질문. Stony Brook 알고리즘 저장소 C ++에서 KDTrees의 일부 구현이 있지만 STL이나 부스트의 일부는 아닙니다.

배열을 정렬하면 O (N통나무N) 시각. 간단히 각 점을 개별적으로 확인하면 (정렬없이) O (정렬없이)N) 시각.

Ergo, 그냥지나 가서 각 지점을 확인하는 것은 더 빠르게 정렬보다. 그리고 쿼드 트리를 만드는 것보다 빠릅니다.

편집 : 확인할 직사각형이 많으면 다른 이야기입니다. 그러나 작고 고정 된 수의 직사각형 만 확인하면 "명백한"방법으로 만하십시오!

쿼드 트리를 사용하면 3 가지 유형의 Qtree 노드가 있습니다.

  1. 노드는 대상 사각형 외부에 있습니다 : 무시하십시오
  2. 노드는 대상 사각형 안에 있습니다 : 노드 내부에 모든 점을 포함
  3. 노드는 부분적으로 사각형 외부에 있습니다. 노드 내부의 점에서 경계 확인을 수행합니다.

Yuval F의 링크에 따라 나는 발견했다 범위 검색, 그것은 당신이 찾고있는 정확한 종류 인 것 같습니다. 나는 거기에서 몇 가지 링크를 따랐다 cgal, 오픈 소스 C ++ 라이브러리. 여기.

정렬 함수는 지점 내부에 대한 지점을 확인하고 사각형 외부의 모든 지점 전에 사각형 내부의 모든 지점을 정렬 할 수 있습니다. 각각의 존재 수를 추적하거나 전체 세트에서 이진 검색을 사용하여 조회 시간에 컷오프 지점을 찾아야합니다.

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