Rompartisjonering

Rompartisjonering er en prosess der et geometrisk rom, vanligvis et euklidsk rom, deles inn i to eller flere disjunkte delmengder. Resultatet er en mengde regioner som ikke overlapper hverandre, utenom muligens på randen (området rundt hver region). Rompartisjonering brukes for å dele opp et rom, eller et geometrisk objekt, i mindre rom; oftest med enklere geometriske egenskaper. Delvis gjør dette at man får en finere inndeling, man representerer objekter med flere enheter, og delvis gjør dette at man lettere kan utføre matematiske beregninger på hvert objekt.

Dersom hver region er triangulær, det vil i to dimensjoner en trekant, i tre dimensjoner en polyeder eller generelt en simpleks, kalles denne prosessen for triangulering. Triangulering danner grunnlaget for flere geometri-baserte algoritmer, som endelige elementer-metoden og overflaterepresentasjon. Mer generelt, for alle typer regioner, brukes dette for blant annet punktlokasjon og raytracing.

Teknikker

Rekursiv inndeling

Generering av et okttre: Rommet som partisjoneres til venstre, og trerepresentasjonen til høyre

Rompartisjon utføres ofte hierarkisk, eller rekursivt: Man deler inn rommet i to eller flere større regioner, og bruker deretter samme algoritme på hver av disse regionene for å få en finere inndeling. En slik partisjon kan organiseres i et tre, der roten tilsvarer hele rommet, alle interne noder unionen av rommet gitt ved sine barn og alle løvnoder en region som ikke overlapper med regionen gitt ved noen andre løvnoder.

For å dele opp hver region bruker man ofte binær rompartisjonering: For hvert nivå bruker man en linje, plan eller, i høyere dimensjoner, et hyperplan, for å dele regionen i to. Hver delmengde defineres ut fra hvilke punkter som faller på hvilen side av det gitte hyperplanet, og hver region vil tilsvare en konveks mengde.

En slik rekursiv inndeling er blant annet grunnlaget for datastrukturer som kd-trær, quadtrær og okttrær, dersom disse representerer et geometrisk rom. Hver av disse deler genereres ut fra rekursiv oppdeling av det opprinnelige rommet, og operasjoner utført på strukturen tar utgangspunkt i den samme strukturen.