- Space partitioning
In
mathematics , space partitioning is the process of dividing aspace (usually aEuclidean space ) into two or moredisjoint subset s (see alsopartition of a set ). In other words, space partitioning divides a space into non-overlapping regions. Any point in the space can then be identified to lie in exactly one of the regions.Space-partitioning systems are often hierarchical, meaning that a space (or a region of space) is divided into several regions, and then the same space-partitioning system is recursively applied to each of the regions thus created. The regions can be organized into a tree, called a space-partitioning tree.
Most space-partitioning systems use planes (or, in higher dimensions,
hyperplane s) to divide space: points on one side of the plane form one region, and points on the other side form another. Points exactly on the plane are usually arbitrarily assigned to one or the other side. Recursively partitioning space using planes in this way produces aBSP tree , one of the most common forms of space partitioning.Space partitioning is particularly important in
computer graphics , where it is frequently used to organize the objects in a virtual scene. Storing objects in a space-partitioningdata structure makes it easy and fast to perform certain kinds of geometry queries — for example, determining whether two objects are close to each other incollision detection , or determining whether a ray intersects an object inray tracing .In
integrated circuit design , an important step isdesign rule check . This step ensures that the completed design is manufacturable. The check involves rules that specify widths and spacings and other geometry patterns. A modern design can have billions of polygons that represent wires and transistors. Efficient checking relies heavily on geometry query. For example, a rule may specify that any polygon must be at least "n" nanometers from any other polygon. This is converted into a geometry query by enlarging a polygon by "n" at all sides and query to find all intersecting polygons.Common space partitioning systems include:
*BSP tree s
*Quadtree s
*Octree s
* "k"d-trees
* Bins
*R-tree sSpatial Patitioning Examples:
Wikimedia Foundation. 2010.
