HOME

TheInfoList



OR:

In
geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
, space partitioning is the process of dividing an entire
space Space is a three-dimensional continuum containing positions and directions. In classical physics, physical space is often conceived in three linear dimensions. Modern physicists usually consider it, with time, to be part of a boundless ...
(usually a
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
) into two or more disjoint
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
s (see also
partition of a set In mathematics, a partition of a set is a grouping of its elements into Empty set, non-empty subsets, in such a way that every element is included in exactly one subset. Every equivalence relation on a Set (mathematics), set defines a partitio ...
). 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.


Overview

Space-partitioning systems are often
hierarchical A hierarchy (from Greek: , from , 'president of sacred rites') is an arrangement of items (objects, names, values, categories, etc.) that are represented as being "above", "below", or "at the same level as" one another. Hierarchy is an importan ...
, 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 In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
, called a space-partitioning tree. Most space-partitioning systems use planes (or, in higher dimensions,
hyperplane In geometry, a hyperplane is a generalization of a two-dimensional plane in three-dimensional space to mathematical spaces of arbitrary dimension. Like a plane in space, a hyperplane is a flat hypersurface, a subspace whose dimension is ...
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 a BSP tree, one of the most common forms of space partitioning.


Uses


In computer graphics

Space partitioning is particularly important in
computer graphics Computer graphics deals with generating images and art with the aid of computers. Computer graphics is a core technology in digital photography, film, video games, digital art, cell phone and computer displays, and many specialized applications. ...
, especially heavily used in ray tracing, where it is frequently used to organize the objects in a virtual scene. A typical scene may contain millions of polygons. Performing a ray/polygon intersection test with each would be a very computationally expensive task. Storing objects in a space-partitioning
data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
( ''k''-d tree or BSP tree for example) makes it easy and fast to perform certain kinds of geometry queries—for example in determining whether a ray intersects an object, space partitioning can reduce the number of intersection test to just a few per primary ray, yielding a logarithmic
time complexity In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
with respect to the number of polygons. Space partitioning is also often used in scanline algorithms to eliminate the polygons out of the camera's viewing frustum, limiting the number of polygons processed by the pipeline. There is also a usage in
collision detection Collision detection is the computational problem of detecting an intersection of two or more objects in virtual space. More precisely, it deals with the questions of ''if'', ''when'' and ''where'' two or more objects intersect. Collision detect ...
: determining whether two objects are close to each other can be much faster using space partitioning.


In integrated circuit design

In
integrated circuit design Integrated circuit design, semiconductor design, chip design or IC design, is a sub-field of electronics engineering, encompassing the particular Boolean logic, logic and circuit design techniques required to design integrated circuits (ICs). A ...
, an important step is
design rule check In electronic design automation, a design rule is a geometric constraint imposed on circuit board, semiconductor device, and integrated circuit (IC) designers to ensure their designs function properly, reliably, and can be produced with acceptabl ...
. 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/2'' at all sides and query to find all intersecting polygons.


In probability and statistical learning theory

The number of components in a space partition plays a central role in some results in probability theory. See Growth function for more details.


In Geography and GIS

There are many studies and applications where Geographical Spatial Reality is partitioned by hydrological criteria, administrative criteria, mathematical criteria or many others. In the context of
Cartography Cartography (; from , 'papyrus, sheet of paper, map'; and , 'write') is the study and practice of making and using maps. Combining science, aesthetics and technique, cartography builds on the premise that reality (or an imagined reality) can ...
and GIS - Geographic Information System, is common to identify cells of the partition by standard codes. For example the for HUC code identifying hydrographical basins and sub-basins,
ISO 3166-2 ISO 3166-2 is part of the ISO 3166 standard published by the International Organization for Standardization (ISO), and defines codes for identifying the principal subdivisions (e.g., provinces or states) of all countries coded in ISO 3166-1. Th ...
codes identifying countries and its subdivisions, or arbitrary DGGs - discrete global grids identifying quadrants or locations.


Data structures

Common space-partitioning systems include: * BSP trees *
Quadtree A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four ...
s *
Octree An octree is a tree data structure in which each internal node has exactly eight child node, children. Octrees are most often used to partition a three-dimensional space by recursive subdivision, recursively subdividing it into eight Octant (geo ...
s * ''k''-d trees * Bins


Number of components

Suppose the n-dimensional
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
is partitioned by r
hyperplane In geometry, a hyperplane is a generalization of a two-dimensional plane in three-dimensional space to mathematical spaces of arbitrary dimension. Like a plane in space, a hyperplane is a flat hypersurface, a subspace whose dimension is ...
s that are (n-1)-dimensional. What is the number of components in the partition? The largest number of components is attained when the hyperplanes are in
general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that a ...
, i.e, no two are parallel and no three have the same intersection. Denote this maximum number of components by Comp(n,r). Then, the following recurrence relation holds: See also detailed discussions and explanations o
the case n=2
an
the general case
See also .
::Comp(n,r) = Comp(n, r-1) + Comp(n-1,r-1) ::Comp(0,r) = 1 - when there are no dimensions, there is a single point. ::Comp(n,0) = 1 - when there are no hyperplanes, all the space is a single component. And its solution is: ::Comp(n,r) = \sum_^n if r\geq n ::Comp(n,r) = 2^r if r\leq n ::::(consider e.g. r perpendicular hyperplanes; each additional hyperplane divides each existing component to 2). which is upper-bounded as: ::Comp(n,r) \leq r^n+1


See also

*
Binary space partitioning In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a representa ...
* Discrete global grid * Polygon partition *
Tessellation A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety ...


References

{{Reflist Computer graphics Geometric algorithms