| <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> |
| <!-- NewPage --> |
| <html lang="en"> |
| <head> |
| <meta http-equiv="Content-Type" content="text/html" charset="UTF-8"> |
| <title>org.apache.commons.math3.geometry.partitioning (Apache Commons Math 3.3 API)</title> |
| <link rel="stylesheet" type="text/css" href="../../../../../../stylesheet.css" title="Style"> |
| </head> |
| <body> |
| <script type="text/javascript"><!-- |
| if (location.href.indexOf('is-external=true') == -1) { |
| parent.document.title="org.apache.commons.math3.geometry.partitioning (Apache Commons Math 3.3 API)"; |
| } |
| //--> |
| </script> |
| <noscript> |
| <div>JavaScript is disabled on your browser.</div> |
| </noscript> |
| <!-- ========= START OF TOP NAVBAR ======= --> |
| <div class="topNav"><a name="navbar_top"> |
| <!-- --> |
| </a><a href="#skip-navbar_top" title="Skip navigation links"></a><a name="navbar_top_firstrow"> |
| <!-- --> |
| </a> |
| <ul class="navList" title="Navigation"> |
| <li><a href="../../../../../../overview-summary.html">Overview</a></li> |
| <li class="navBarCell1Rev">Package</li> |
| <li>Class</li> |
| <li><a href="package-use.html">Use</a></li> |
| <li><a href="package-tree.html">Tree</a></li> |
| <li><a href="../../../../../../deprecated-list.html">Deprecated</a></li> |
| <li><a href="../../../../../../index-all.html">Index</a></li> |
| <li><a href="../../../../../../help-doc.html">Help</a></li> |
| </ul> |
| <div class="aboutLanguage"><em><script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script></em></div> |
| </div> |
| <div class="subNav"> |
| <ul class="navList"> |
| <li><a href="../../../../../../org/apache/commons/math3/geometry/hull/package-summary.html">Prev Package</a></li> |
| <li><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/utilities/package-summary.html">Next Package</a></li> |
| </ul> |
| <ul class="navList"> |
| <li><a href="../../../../../../index.html?org/apache/commons/math3/geometry/partitioning/package-summary.html" target="_top">Frames</a></li> |
| <li><a href="package-summary.html" target="_top">No Frames</a></li> |
| </ul> |
| <ul class="navList" id="allclasses_navbar_top"> |
| <li><a href="../../../../../../allclasses-noframe.html">All Classes</a></li> |
| </ul> |
| <div> |
| <script type="text/javascript"><!-- |
| allClassesLink = document.getElementById("allclasses_navbar_top"); |
| if(window==top) { |
| allClassesLink.style.display = "block"; |
| } |
| else { |
| allClassesLink.style.display = "none"; |
| } |
| //--> |
| </script> |
| </div> |
| <a name="skip-navbar_top"> |
| <!-- --> |
| </a></div> |
| <!-- ========= END OF TOP NAVBAR ========= --> |
| <div class="header"> |
| <h1 title="Package" class="title">Package org.apache.commons.math3.geometry.partitioning</h1> |
| <div class="docSummary"> |
| <div class="block">This package provides classes to implement Binary Space Partition trees.</div> |
| </div> |
| <p>See: <a href="#package_description">Description</a></p> |
| </div> |
| <div class="contentContainer"> |
| <ul class="blockList"> |
| <li class="blockList"> |
| <table class="packageSummary" border="0" cellpadding="3" cellspacing="0" summary="Interface Summary table, listing interfaces, and an explanation"> |
| <caption><span>Interface Summary</span><span class="tabEnd"> </span></caption> |
| <tr> |
| <th class="colFirst" scope="col">Interface</th> |
| <th class="colLast" scope="col">Description</th> |
| </tr> |
| <tbody> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/BSPTree.LeafMerger.html" title="interface in org.apache.commons.math3.geometry.partitioning">BSPTree.LeafMerger</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This interface gather the merging operations between a BSP tree |
| leaf and another BSP tree.</div> |
| </td> |
| </tr> |
| <tr class="rowColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/BSPTreeVisitor.html" title="interface in org.apache.commons.math3.geometry.partitioning">BSPTreeVisitor</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This interface is used to visit <a href="../../../../../../org/apache/commons/math3/geometry/partitioning/BSPTree.html" title="class in org.apache.commons.math3.geometry.partitioning"><code>BSP tree</code></a> nodes.</div> |
| </td> |
| </tr> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/Embedding.html" title="interface in org.apache.commons.math3.geometry.partitioning">Embedding</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>,T extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This interface defines mappers between a space and one of its sub-spaces.</div> |
| </td> |
| </tr> |
| <tr class="rowColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/Hyperplane.html" title="interface in org.apache.commons.math3.geometry.partitioning">Hyperplane</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This interface represents an hyperplane of a space.</div> |
| </td> |
| </tr> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/Region.html" title="interface in org.apache.commons.math3.geometry.partitioning">Region</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This interface represents a region of a space as a partition.</div> |
| </td> |
| </tr> |
| <tr class="rowColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/SubHyperplane.html" title="interface in org.apache.commons.math3.geometry.partitioning">SubHyperplane</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This interface represents the remaining parts of an hyperplane after |
| other parts have been chopped off.</div> |
| </td> |
| </tr> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/Transform.html" title="interface in org.apache.commons.math3.geometry.partitioning">Transform</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>,T extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This interface represents an inversible affine transform in a space.</div> |
| </td> |
| </tr> |
| </tbody> |
| </table> |
| </li> |
| <li class="blockList"> |
| <table class="packageSummary" border="0" cellpadding="3" cellspacing="0" summary="Class Summary table, listing classes, and an explanation"> |
| <caption><span>Class Summary</span><span class="tabEnd"> </span></caption> |
| <tr> |
| <th class="colFirst" scope="col">Class</th> |
| <th class="colLast" scope="col">Description</th> |
| </tr> |
| <tbody> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/AbstractRegion.html" title="class in org.apache.commons.math3.geometry.partitioning">AbstractRegion</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>,T extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">Abstract class for all regions, independently of geometry type or dimension.</div> |
| </td> |
| </tr> |
| <tr class="rowColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/AbstractSubHyperplane.html" title="class in org.apache.commons.math3.geometry.partitioning">AbstractSubHyperplane</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>,T extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This class implements the dimension-independent parts of <a href="../../../../../../org/apache/commons/math3/geometry/partitioning/SubHyperplane.html" title="interface in org.apache.commons.math3.geometry.partitioning"><code>SubHyperplane</code></a>.</div> |
| </td> |
| </tr> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/BoundaryAttribute.html" title="class in org.apache.commons.math3.geometry.partitioning">BoundaryAttribute</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">Class holding boundary attributes.</div> |
| </td> |
| </tr> |
| <tr class="rowColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/BoundaryProjection.html" title="class in org.apache.commons.math3.geometry.partitioning">BoundaryProjection</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">Class holding the result of point projection on region boundary.</div> |
| </td> |
| </tr> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/BSPTree.html" title="class in org.apache.commons.math3.geometry.partitioning">BSPTree</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This class represent a Binary Space Partition tree.</div> |
| </td> |
| </tr> |
| <tr class="rowColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/RegionFactory.html" title="class in org.apache.commons.math3.geometry.partitioning">RegionFactory</a><S extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">This class is a factory for <a href="../../../../../../org/apache/commons/math3/geometry/partitioning/Region.html" title="interface in org.apache.commons.math3.geometry.partitioning"><code>Region</code></a>.</div> |
| </td> |
| </tr> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/SubHyperplane.SplitSubHyperplane.html" title="class in org.apache.commons.math3.geometry.partitioning">SubHyperplane.SplitSubHyperplane</a><U extends <a href="../../../../../../org/apache/commons/math3/geometry/Space.html" title="interface in org.apache.commons.math3.geometry">Space</a>></td> |
| <td class="colLast"> |
| <div class="block">Class holding the results of the <a href="../../../../../../org/apache/commons/math3/geometry/partitioning/SubHyperplane.html#split(org.apache.commons.math3.geometry.partitioning.Hyperplane)"><code>split</code></a> method.</div> |
| </td> |
| </tr> |
| </tbody> |
| </table> |
| </li> |
| <li class="blockList"> |
| <table class="packageSummary" border="0" cellpadding="3" cellspacing="0" summary="Enum Summary table, listing enums, and an explanation"> |
| <caption><span>Enum Summary</span><span class="tabEnd"> </span></caption> |
| <tr> |
| <th class="colFirst" scope="col">Enum</th> |
| <th class="colLast" scope="col">Description</th> |
| </tr> |
| <tbody> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/BSPTreeVisitor.Order.html" title="enum in org.apache.commons.math3.geometry.partitioning">BSPTreeVisitor.Order</a></td> |
| <td class="colLast"> |
| <div class="block">Enumerate for visit order with respect to plus sub-tree, minus sub-tree and cut sub-hyperplane.</div> |
| </td> |
| </tr> |
| <tr class="rowColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/Region.Location.html" title="enum in org.apache.commons.math3.geometry.partitioning">Region.Location</a></td> |
| <td class="colLast"> |
| <div class="block">Enumerate for the location of a point with respect to the region.</div> |
| </td> |
| </tr> |
| <tr class="altColor"> |
| <td class="colFirst"><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/Side.html" title="enum in org.apache.commons.math3.geometry.partitioning">Side</a></td> |
| <td class="colLast"> |
| <div class="block">Enumerate representing the location of an element with respect to an |
| <a href="../../../../../../org/apache/commons/math3/geometry/partitioning/Hyperplane.html" title="interface in org.apache.commons.math3.geometry.partitioning"><code>hyperplane</code></a> of a space.</div> |
| </td> |
| </tr> |
| </tbody> |
| </table> |
| </li> |
| </ul> |
| <a name="package_description"> |
| <!-- --> |
| </a> |
| <h2 title="Package org.apache.commons.math3.geometry.partitioning Description">Package org.apache.commons.math3.geometry.partitioning Description</h2> |
| <div class="block">This package provides classes to implement Binary Space Partition trees. |
| |
| <p> |
| <a href="../../../../../../org/apache/commons/math3/geometry/partitioning/BSPTree.html" title="class in org.apache.commons.math3.geometry.partitioning"><code>BSP trees</code></a> |
| are an efficient way to represent parts of space and in particular |
| polytopes (line segments in 1D, polygons in 2D and polyhedrons in 3D) |
| and to operate on them. The main principle is to recursively subdivide |
| the space using simple hyperplanes (points in 1D, lines in 2D, planes |
| in 3D). |
| </p> |
| |
| <p> |
| We start with a tree composed of a single node without any cut |
| hyperplane: it represents the complete space, which is a convex |
| part. If we add a cut hyperplane to this node, this represents a |
| partition with the hyperplane at the node level and two half spaces at |
| each side of the cut hyperplane. These half-spaces are represented by |
| two child nodes without any cut hyperplanes associated, the plus child |
| which represents the half space on the plus side of the cut hyperplane |
| and the minus child on the other side. Continuing the subdivisions, we |
| end up with a tree having internal nodes that are associated with a |
| cut hyperplane and leaf nodes without any hyperplane which correspond |
| to convex parts. |
| </p> |
| |
| <p> |
| When BSP trees are used to represent polytopes, the convex parts are |
| known to be completely inside or outside the polytope as long as there |
| is no facet in the part (which is obviously the case if the cut |
| hyperplanes have been chosen as the underlying hyperplanes of the |
| facets (this is called an autopartition) and if the subdivision |
| process has been continued until all facets have been processed. It is |
| important to note that the polytope is <em>not</em> defined by a |
| single part, but by several convex ones. This is the property that |
| allows BSP-trees to represent non-convex polytopes despites all parts |
| are convex. The <a href="../../../../../../org/apache/commons/math3/geometry/partitioning/Region.html" title="interface in org.apache.commons.math3.geometry.partitioning"><code>Region</code></a> class is |
| devoted to this representation, it is build on top of the <a href="../../../../../../org/apache/commons/math3/geometry/partitioning/BSPTree.html" title="class in org.apache.commons.math3.geometry.partitioning"><code>BSPTree</code></a> class using |
| boolean objects as the leaf nodes attributes to represent the |
| inside/outside property of each leaf part, and also adds various |
| methods dealing with boundaries (i.e. the separation between the |
| inside and the outside parts). |
| </p> |
| |
| <p> |
| Rather than simply associating the internal nodes with an hyperplane, |
| we consider <em>sub-hyperplanes</em> which correspond to the part of |
| the hyperplane that is inside the convex part defined by all the |
| parent nodes (this implies that the sub-hyperplane at root node is in |
| fact a complete hyperplane, because there is no parent to bound |
| it). Since the parts are convex, the sub-hyperplanes are convex, in |
| 3D the convex parts are convex polyhedrons, and the sub-hyperplanes |
| are convex polygons that cut these polyhedrons in two |
| sub-polyhedrons. Using this definition, a BSP tree completely |
| partitions the space. Each point either belongs to one of the |
| sub-hyperplanes in an internal node or belongs to one of the leaf |
| convex parts. |
| </p> |
| |
| <p> |
| In order to determine where a point is, it is sufficient to check its |
| position with respect to the root cut hyperplane, to select the |
| corresponding child tree and to repeat the procedure recursively, |
| until either the point appears to be exactly on one of the hyperplanes |
| in the middle of the tree or to be in one of the leaf parts. For |
| this operation, it is sufficient to consider the complete hyperplanes, |
| there is no need to check the points with the boundary of the |
| sub-hyperplanes, because this check has in fact already been realized |
| by the recursive descent in the tree. This is very easy to do and very |
| efficient, especially if the tree is well balanced (the cost is |
| <code>O(log(n))</code> where <code>n</code> is the number of facets) |
| or if the first tree levels close to the root discriminate large parts |
| of the total space. |
| </p> |
| |
| <p> |
| One of the main sources for the development of this package was Bruce |
| Naylor, John Amanatides and William Thibault paper <a |
| href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging |
| BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90, |
| Computer Graphics 24(4), August 1990, pp 115-124, published by the |
| Association for Computing Machinery (ACM). The same paper can also be |
| found <a |
| href="http://www.cs.utexas.edu/users/fussell/courses/cs384g/bsp_treemerge.pdf">here</a>. |
| </p> |
| |
| <p> |
| Note that the interfaces defined in this package are <em>not</em> intended to |
| be implemented by Apache Commons Math users, they are only intended to be |
| implemented within the library itself. New methods may be added even for |
| minor versions, which breaks compatibility for external implementations. |
| </p></div> |
| </div> |
| <!-- ======= START OF BOTTOM NAVBAR ====== --> |
| <div class="bottomNav"><a name="navbar_bottom"> |
| <!-- --> |
| </a><a href="#skip-navbar_bottom" title="Skip navigation links"></a><a name="navbar_bottom_firstrow"> |
| <!-- --> |
| </a> |
| <ul class="navList" title="Navigation"> |
| <li><a href="../../../../../../overview-summary.html">Overview</a></li> |
| <li class="navBarCell1Rev">Package</li> |
| <li>Class</li> |
| <li><a href="package-use.html">Use</a></li> |
| <li><a href="package-tree.html">Tree</a></li> |
| <li><a href="../../../../../../deprecated-list.html">Deprecated</a></li> |
| <li><a href="../../../../../../index-all.html">Index</a></li> |
| <li><a href="../../../../../../help-doc.html">Help</a></li> |
| </ul> |
| <div class="aboutLanguage"><em><script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script></em></div> |
| </div> |
| <div class="subNav"> |
| <ul class="navList"> |
| <li><a href="../../../../../../org/apache/commons/math3/geometry/hull/package-summary.html">Prev Package</a></li> |
| <li><a href="../../../../../../org/apache/commons/math3/geometry/partitioning/utilities/package-summary.html">Next Package</a></li> |
| </ul> |
| <ul class="navList"> |
| <li><a href="../../../../../../index.html?org/apache/commons/math3/geometry/partitioning/package-summary.html" target="_top">Frames</a></li> |
| <li><a href="package-summary.html" target="_top">No Frames</a></li> |
| </ul> |
| <ul class="navList" id="allclasses_navbar_bottom"> |
| <li><a href="../../../../../../allclasses-noframe.html">All Classes</a></li> |
| </ul> |
| <div> |
| <script type="text/javascript"><!-- |
| allClassesLink = document.getElementById("allclasses_navbar_bottom"); |
| if(window==top) { |
| allClassesLink.style.display = "block"; |
| } |
| else { |
| allClassesLink.style.display = "none"; |
| } |
| //--> |
| </script> |
| </div> |
| <a name="skip-navbar_bottom"> |
| <!-- --> |
| </a></div> |
| <!-- ======== END OF BOTTOM NAVBAR ======= --> |
| <p class="legalCopy"><small>Copyright © 2003–2014 <a href="http://www.apache.org/">The Apache Software Foundation</a>. All rights reserved.</small></p> |
| </body> |
| </html> |
