겹치지 않는 직사각형의 적중 테스트 알고리즘

Question

둘러싸는 직사각형을 덮는 겹치지 않는 직사각형 모음이 있습니다.마우스 클릭을 포함하는 직사각형을 찾는 가장 좋은 방법은 무엇입니까?

확실한 대답은 직사각형의 배열을 갖고 이를 순서대로 검색하여 검색을 O(n)으로 만드는 것입니다.알고리즘이 O(n), 즉 O(log n) 또는 O(sqrt(n))보다 작도록 위치별로 정렬할 수 있는 방법이 있습니까?

Answer 1

쿼드 또는 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();
  }

분명히 이 방법은 직사각형이 자주 변경되지 않고 비트맵을 위한 메모리를 확보할 수 있는 경우에만 잘 작동합니다.

Answer 2

간격 트리를 만듭니다.간격 트리를 쿼리합니다.MIT 언론의 '알고리즘'을 참조하세요.

간격 트리는 레드-블랙 트리로 가장 잘 구현됩니다.

일반적으로 위치를 변경하는 것보다 더 많이 클릭할 경우에만 직사각형을 정렬하는 것이 좋습니다.

다른 축에 대한 인덱스를 별도로 구축했다는 점을 명심해야 합니다.예를 들어 X와 Y의 간격이 겹치는지 확인해야 합니다.한 가지 확실한 최적화는 X 간격 중 하나에서만 겹치는 부분만 확인한 다음 Y에서 겹치는 부분을 즉시 확인하는 것입니다.

또한 대부분의 주식 또는 '클래스북' 간격 트리는 단일 간격만 확인하고 단일 간격만 반환합니다(그러나 "비겹침"이라고 말씀하셨죠?).

Answer 3

그것들을 한 곳에 밀어 넣으세요 쿼드트리.

Answer 4

사용 BSP 직사각형을 저장하는 트리.