2D 공간에서 직사각형 찾기

2D 공간에서 다양한 크기의 직사각형 세트가 있습니다. 직사각형 수는 10에서 100 000까지 동적으로 변경 될 수 있으며 위치는 물론 크기가 자주 업데이트됩니다.2D 공간에서 직사각형 찾기

주어진 점 (x, y)에서 사각형을 찾으려면 어떤 공간 구조를 사용 하시겠습니까? 검색 작업도 매우 자주 수행된다고 가정합니다 (예 : 마우스 이동시). 다양한 공간 인덱싱 알고리즘 비교에 대한 참조를 제공하거나 여기에서 검색/빌드/업데이트 성능을 비교할 수 있다면 멋지 겠죠.

출처

2012-05-21 CuriousG

주어진 점을 포함하는 모든 사각형을 찾는 것과 같은 것을 원하십니까? 직사각형이 임의의 양만큼 회전되었거나 축이 x 및 y와 평행합니까? –

그들의 축은 parellel에서 Ox, Oy입니다. 누락되어 죄송합니다. 모든 직사각형을 찾는 것이 좋을지라도 점을 포함하는 사각형을 찾는 것만으로도 충분합니다. 다양한 [색인] (http://en.wikipedia.org/wiki/Spatial_index#Spatial_index)에 대해 알고 있지만 필자와 함께 일한 적이 없으므로 특정 상황을 기준으로 선택해야하는 전문가 의견이 더 궁금합니다. ... – CuriousG

나는 R-Tree을 제안합니다. 주로 사각형 (또는 N 차원 축 정렬 큐브) 용으로 설계되었습니다.

출처

2012-05-21 07:00:50

쿼드 트리 (http://en.wikipedia.org/wiki/Quadtree)를 사용하십시오.

직사각형의 시작과 끝에서 가능한 모든 X 값과 Y 값을 결정하십시오. 그런 다음이 값에 따라 쿼드 트리를 만듭니다. quadtree의 각 잎에 어떤 사각형이 잎의 좌표 범위와 겹치는 지 저장하십시오. 겹치는 사각형을 찾는 것은 좌표가 들어있는 잎을 찾는 것입니다.

출처

2012-05-21 06:56:46 Patrick

2D 공간에서 직사각형 찾기

답변

관련 문제