나는 둘러싸는 직사각형을 덮는 겹치지 않는 사각형의 모음을 가지고 있습니다. 마우스 클릭에 대해 포함하는 사각형을 찾는 가장 좋은 방법은 무엇입니까?겹치지 않는 사각형에서 히트 테스트 알고리즘
명백한 대답은 직사각형의 배열을 가지며 순서대로 검색하여 검색 O (n)을 만드는 것입니다. 알고리즘을 O (n)보다 적게, 즉 O (log n) 또는 O (sqrt (n))와 같이 위치별로 정렬하는 방법이 있습니까?
쿼드 또는 kd 트리로 사각형을 구성 할 수 있습니다. 그건 당신에게 O (log n)를줍니다. 그것은 주류 방법입니다.
이 문제에 대한 또 다른 흥미로운 데이터 구조는 R- 트리입니다. 많은 직사각형을 다룰 필요가 있다면 매우 효율적입니다.
http://en.wikipedia.org/wiki/R-tree
, 그리고, O는 단순히 "아니오 직사각형"에 대한 플레이스 홀더를 채우고 히트 직사각형을 화면과 같은 크기의 비트 맵을 생성하는 (1)에있어서 존재 인덱스를 그 비트 맵에 추가합니다.
int id = bitmap_getpixel (mouse.x, mouse.y)
if (id != -1)
{
hit_rectange (id);
}
else
{
no_hit();
}
은 분명히 그 방법은 비트 맵에 대한 메모리를 마련 할 수있는 경우 사각형이 자주 변경하지 않는 경우에 잘 작동합니다 같이 조회는 간단해진다.
quadtree에 입력하십시오.
"영역 quadtree는 영역을 분해하여 공간 차원의 공간을 나타냅니다 4 등분 사분원, 부 승제, [...]. 사각형이 똑같은 사분면으로 분해 가능하지만 불규칙한 크기로 분해되지 않는 경우는 어떻게됩니까? 예 : 8x9 = [8x3,6x7,2x4,2x2] – hughdbrown
나뭇잎에 데이터를 저장하지 말고 데이터를 상위에 저장하십시오. 각 사각형을 완전히 포함하는 가장 작은 가지에 저장하십시오. 또는 겹치는 각 잎에 각 사각형에 대한 참조를 저장하거나 [느슨한 쿼드 트리] (http://tinyurl.com/3w5x27)를 사용하십시오. – moonshadow
BSP 트리를 사용하여 사각형을 저장하십시오.
간격 트리를 만듭니다. 간격 트리를 질의하십시오. MIT 프레스에서 '알고리즘'에 문의하십시오.
간격 트리는 빨강 - 검정 트리로 구현하는 것이 가장 좋습니다.
직사각형을 정렬하려면 더 많이 누른 다음 위치를 변경해야하는 경우에만 정렬하는 것이 좋습니다.
축마다 별도로 인덱스를 빌드해야한다는 것을 명심해야합니다. 예를 들어, X와 Y에서 간격을 겹쳐서 표시해야하는지 확인해야합니다. 하나의 확실한 최적화는 X 간격에서 겹침을 확인한 다음 Y에서 겹침을 즉시 확인하는 것입니다.
또한 대부분의 주식 또는 '클래스 북 'Interval Trees는 하나의 간격 만 확인하고 하나의 간격 만 반환합니다 (그러나 "겹치지 않는"라고 말했습니까?)
kd-tree와 R-tree는 내가 상상할 수있는 것과 가장 비슷합니다. 비트 맵 솔루션은 무차별 적이며 분명히 정확하지만 나무 해결책을 생각합니다. – hughdbrown
나는 인터벌 트리 아이디어도 좋아한다. 직사각형이 겹치지 않아 가장 간단한 방법 일 수 있습니다. –