1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
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>
|
