공간 파티션

기하학에서 공간 분할은 공간(일반적으로 유클리드 공간)을 두 개 이상의 분리된 부분 집합으로 나누는 과정이다.즉, 공간 파티셔닝은 공간을 겹치지 않는 영역으로 분할합니다.그러면 공간의 모든 점이 정확히 하나의 영역에 있음을 식별할 수 있습니다.

개요

공간 분할 시스템은 종종 계층형입니다. 즉, 공간(또는 공간의 영역)이 여러 영역으로 분할된 후 동일한 공간 분할 시스템이 생성된 각 영역에 재귀적으로 적용됩니다.영역은 공간 분할 트리라고 하는 트리로 구성될 수 있습니다.

대부분의 공간 분할 시스템은 평면(또는 고차원에서는 하이퍼플레인)을 사용하여 공간을 분할합니다.평면의 한쪽 점이 하나의 영역을 형성하고 다른 한쪽 점이 다른 영역을 형성합니다.평면상의 정확한 점은 일반적으로 한쪽 또는 다른 쪽에 임의로 할당됩니다.이러한 방법으로 평면을 사용하여 공간을 재귀적으로 분할하면 공간 분할의 가장 일반적인 형식 중 하나인 BSP 트리가 생성됩니다.

사용하다

컴퓨터 그래픽스

공간 파티셔닝은 특히 컴퓨터 그래픽에서 중요합니다. 특히 가상 장면에서 객체를 구성하는 데 자주 사용됩니다.일반적인 장면에는 수백만 개의 폴리곤이 포함될 수 있습니다.각각으로 광선/폴리곤 교차 테스트를 수행하는 것은 계산 비용이 매우 많이 드는 작업입니다.

공간을 분할하는 데이터 구조(예를 들어 k-d 트리 또는 BSP 트리)에 객체를 저장하면 특정 종류의 지오메트리 쿼리를 쉽고 빠르게 실행할 수 있습니다.예를 들어, 공간을 분할하면 1차 광선당 몇 개로 교차 테스트 횟수를 줄일 수 있어 시간이 복잡해집니다.폴리곤의 ^[1][2][3]수에 대한 ty.

공간 파티셔닝은 스캔라인 알고리즘에서도 자주 사용되며, 카메라의 시야에서 폴리곤을 제거하여 파이프라인에서 처리되는 폴리곤의 수를 제한합니다.충돌 검출에도 용도가 있습니다.공간 파티셔닝을 사용하면 2개의 오브젝트가 서로 가까운지 여부를 판별하는 것이 훨씬 빠릅니다.

집적회로 설계 시

집적회로 설계에서 중요한 단계는 설계 규칙 체크입니다.이 단계를 통해 완성된 설계를 확실하게 제작할 수 있습니다.검사에는 폭과 간격 및 기타 지오메트리 패턴을 지정하는 규칙이 포함됩니다.현대의 디자인은 와이어와 트랜지스터를 나타내는 수십억 개의 폴리곤을 가질 수 있다.효율적인 검사는 지오메트리 쿼리에 크게 의존합니다.예를 들어 어떤 폴리곤도 다른 폴리곤과 n나노미터 이상 떨어져 있어야 한다는 규칙을 지정할 수 있습니다.이것은 폴리곤을 모든 면에서 n/2만큼 확대하여 지오메트리 쿼리로 변환하고 교차하는 모든 폴리곤을 찾기 위해 쿼리합니다.

확률 및 통계 학습 이론에서

공간 분할의 성분 수는 확률 이론의 일부 결과에서 중심 역할을 합니다.자세한 내용은 성장 함수를 참조하십시오.

지리학 및 지리학 분야

지리적 공간 현실이 수문학적 기준, 행정적 기준, 수학적 기준 등으로 구분되는 많은 연구와 응용이 있다.

Cartography 및 GIS - Geographic Information System의 맥락에서 는 파티션의 셀을 표준 코드로 식별하기 위해 사용됩니다.예를 들어, 수로 분지와 하위 분지를 식별하는 HUC 코드, 국가 및 그 세분류를 식별하는 ISO 3166-2 코드 또는 사분원 또는 위치를 식별하는 임의의 DGG - 개별 글로벌 그리드.

데이터 구조

일반적인 공간 파티셔닝 시스템은 다음과 같습니다.

• BSP 트리
• 사각형
• 옥트리
• k-d 나무
• 휴지통
• R-tree

컴포넌트 수

n차원 유클리드 공간이 (${\displaystyle n}$-${\displaystyle 1}$)$$\$displaystyle (n-1)}$차원인${\displaystyle }$r$\displaystyle$ r$\$초평면으로 $분할$된다고 가정합니다.파티션의 컴포넌트 수는 몇 개입니까?하이퍼플레인이 일반적인 위치에 있을 때 가장 많은 수의 구성요소가 확보됩니다. 즉, 두 개는 평행하고 세 개는 같은 교점을 가지지 않습니다.이 최대 컴포넌트 수를 ${\displaystyle C}$ ${\displaystyle o}$ m${\displaystyle }$p (${\displaystyle n}$ ,${\displaystyle r}$) { $displaystyle$ Comp $( n$ ,$r$ )$$}로 나타냅니다.그러면 다음과 같은 반복 관계가 유지됩니다.

${\displaystyle Comp(n,r)=Comp(n,r-1)+Comp(n-1,r-1)}$

${\displaystyle C}$ ${\displaystyle o}$ m${\displaystyle \mathrm{p}}$ ( 0${\displaystyle }$,${\displaystyle r}$ ) ${\displaystyle =}$ ( \ $displaystyle Comp ( 0$ , r ) $$$= 1$) - 치수가 없는 경우 단일 포인트가 있습니다.

${\displaystyle C}$ ${\displaystyle o}$ m${\displaystyle }$p (${\displaystyle n}$ ,${\displaystyle 0}$ ) $=$ {\$displaystyle Comp(n$,0)=$$$1}$ - 하이퍼플레인이 없는 경우 모든 공간은 단일 구성 요소입니다.

그 솔루션은 다음과 같습니다.

${\displaystyle C}$ ${\displaystyle o}$ m${\displaystyle }$p (${\displaystyle n}$ ,${\displaystyle r}$ ) ${\displaystyle =}$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{k}}}$ ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{0}}}$ ( ${\displaystyle r\genfrac{}{}{0ex}{}{k}{}}$) { $displaystyle$ Comp $( n$ , r ) = \ $sum$_ { k$$=$0$}^{$n}$ {r$$\$choose$ k$$}(${\displaystyle \mathrm{r<img\; alt="\{\backslash displaystyle\; Comp(n,r)=\backslash sum\; \_\{k=0\}^\{n\}\{r\; \backslash choose\; k\}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/8bea7742e7cf1f3d58c02ccb5fb643d3c2ca6e73"\; style="vertical-align:\; -3.171ex;\; width:22.863ex;\; height:7.009ex;">}}$ \ $displaystyle$r \ $geq$ n$$） ${\displaystyle 。}$

${\displaystyle C}$ ${\displaystyle o}$ m${\displaystyle }$p (${\displaystyle n}$ ,${\displaystyle r}$ ) ${\displaystyle =}$ ${\displaystyle {\mathrm{}}^{}}$ ( r \ $display style$ Comp $( n$ , r ) =$2^$ {$r$ } ( $r{\displaystyle }$ ${\displaystyle \le }$ \ $display style$r \ $leq$n ）

($예{\displaystyle }$:$$r \ $displaystyle$r \ displaystyle r \ icular$$ hyperpl하이퍼플레인, 추가 하이퍼플레인 각각은 기존 컴포넌트를 2로 분할합니다).

이는 다음과 같이 대문자로 표시됩니다.

$\displaystyle Comp(n,r)\leq r^{n}+1}$

「 」를 참조해 주세요.

• 바이너리 공간
• 개별 글로벌 그리드
• 폴리곤 파티션
• 테셀레이션

레퍼런스