Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

데이터 구조의 영역 쿼드트리

<시간/>

영역 쿼드트리는 특정 하위 영역에 해당하는 데이터로 구성된 각 리프 노드와 함께 영역을 4개의 동일한 사분면, 하위 사분면 등으로 분할하여 2차원 공간 분할을 나타내는 데 유용합니다. 트리의 각 노드는 정확히 4개의 자식과 연결되거나 자식이 없음(리프 노드)과 연결됩니다. 이 분해 전략을 따르는 쿼드트리의 높이는(즉, 더 세분화해야 하는 하위 사분면에 흥미로운 데이터가 있을 때까지 하위 사분면을 세분화) 분할되는 공간에서 관심 영역의 공간 분포에 민감하고 의존합니다. 영역 쿼드트리는 트라이 유형으로 표시됩니다.

깊이가 n인 영역 쿼드트리는 각 픽셀 값이 0 또는 1인 2n × 2n 픽셀로 구성된 이미지를 나타내기 위해 구현될 수 있습니다. 루트 노드는 전체 이미지 영역을 나타내는 데 유용합니다. 영역의 픽셀이 완전히 0도 1도 아닌 경우 세분화됩니다. 이 응용 프로그램에서 각 리프 노드는 모두 0 또는 모두 1인 픽셀 블록을 나타내는 데 유용합니다. 이미지를 저장하기 위해 이러한 트리를 구현하면 공간 측면에서 잠재적인 절약 효과를 볼 수 있습니다. 이러한 이미지에는 전체에 걸쳐 동일한 색상 값을 갖는 상당한 크기의 많은 영역이 있는 경우가 많습니다. 이미지의 모든 픽셀에 대한 큰 2차원 배열을 저장하는 대신 쿼드트리는 동일한 정보를 캡처할 수 있으며 그렇지 않으면 필요한 픽셀 해상도 크기의 셀보다 훨씬 더 큰 분할 수준을 잠재적으로 캡처할 수 있습니다. 픽셀과 이미지 크기는 나무 해상도와 전체 크기를 묶을 수 있습니다.

영역 쿼드트리는 데이터 필드의 가변 해상도 표현으로 구현될 수도 있습니다. 예를 들어, 한 영역의 온도는 쿼드트리로 저장될 수 있으며, 각 리프 노드는 그것이 나타내는 하위 영역 전체의 평균 온도를 저장합니다.

지역 쿼드트리가 포인트 데이터 세트(예:도시 세트의 위도 및 경도)를 나타내기 위해 구현된 경우 각 리프에 최대 단일 포인트가 포함되지 않을 때까지 지역이 세분화됩니다.