diff options
Diffstat (limited to 'commons-math3-3.6.1/docs/apidocs/org/apache/commons/math3/geometry/partitioning/package-summary.html')
-rw-r--r-- | commons-math3-3.6.1/docs/apidocs/org/apache/commons/math3/geometry/partitioning/package-summary.html | 369 |
1 files changed, 369 insertions, 0 deletions
diff --git a/commons-math3-3.6.1/docs/apidocs/org/apache/commons/math3/geometry/partitioning/package-summary.html b/commons-math3-3.6.1/docs/apidocs/org/apache/commons/math3/geometry/partitioning/package-summary.html new file mode 100644 index 0000000..d64f1b0 --- /dev/null +++ b/commons-math3-3.6.1/docs/apidocs/org/apache/commons/math3/geometry/partitioning/package-summary.html @@ -0,0 +1,369 @@ +<!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.6.1 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.6.1 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/BSPTree.VanishingCutHandler.html" title="interface in org.apache.commons.math3.geometry.partitioning">BSPTree.VanishingCutHandler</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 handles the corner cases when an internal node cut sub-hyperplane vanishes.</div> +</td> +</tr> +<tr class="altColor"> +<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="rowColor"> +<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="altColor"> +<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="rowColor"> +<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="altColor"> +<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="rowColor"> +<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/NodesSet.html" title="class in org.apache.commons.math3.geometry.partitioning">NodesSet</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">Set of <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/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="rowColor"> +<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–2016 <a href="http://www.apache.org/">The Apache Software Foundation</a>. All rights reserved.</small></p> +</body> +</html> |