1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.geometry.partitioning;
23
24 import java.util.ArrayList;
25 import java.util.List;
26
27 import org.hipparchus.exception.MathRuntimeException;
28 import org.hipparchus.geometry.Geometry;
29 import org.hipparchus.geometry.Point;
30 import org.hipparchus.geometry.Space;
31 import org.hipparchus.util.FastMath;
32
33 /** This class represent a Binary Space Partition tree.
34
35 * <p>BSP trees are an efficient way to represent space partitions and
36 * to associate attributes with each cell. Each node in a BSP tree
37 * represents a convex region which is partitioned in two convex
38 * sub-regions at each side of a cut hyperplane. The root tree
39 * contains the complete space.</p>
40
41 * <p>The main use of such partitions is to use a boolean attribute to
42 * define an inside/outside property, hence representing arbitrary
43 * polytopes (line segments in 1D, polygons in 2D and polyhedrons in
44 * 3D) and to operate on them.</p>
45
46 * <p>Another example would be to represent Voronoi tesselations, the
47 * attribute of each cell holding the defining point of the cell.</p>
48
49 * <p>The application-defined attributes are shared among copied
50 * instances and propagated to split parts. These attributes are not
51 * used by the BSP-tree algorithms themselves, so the application can
52 * use them for any purpose. Since the tree visiting method holds
53 * internal and leaf nodes differently, it is possible to use
54 * different classes for internal nodes attributes and leaf nodes
55 * attributes. This should be used with care, though, because if the
56 * tree is modified in any way after attributes have been set, some
57 * internal nodes may become leaf nodes and some leaf nodes may become
58 * internal nodes.</p>
59
60 * <p>One of the main sources for the development of this package was
61 * Bruce Naylor, John Amanatides and William Thibault paper <a
62 * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
63 * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90,
64 * Computer Graphics 24(4), August 1990, pp 115-124, published by the
65 * Association for Computing Machinery (ACM).</p>
66
67 * @param <S> Type of the space.
68 * @param <P> Type of the points in space.
69 * @param <H> Type of the hyperplane.
70 * @param <I> Type of the sub-hyperplane.
71
72 */
73 public class BSPTree<S extends Space,
74 P extends Point<S, P>,
75 H extends Hyperplane<S, P, H, I>,
76 I extends SubHyperplane<S, P, H, I>> {
77
78 /** Cut sub-hyperplane. */
79 private I cut;
80
81 /** Tree at the plus side of the cut hyperplane. */
82 private BSPTree<S, P, H, I> plus;
83
84 /** Tree at the minus side of the cut hyperplane. */
85 private BSPTree<S, P, H, I> minus;
86
87 /** Parent tree. */
88 private BSPTree<S, P, H, I> parent;
89
90 /** Application-defined attribute. */
91 private Object attribute;
92
93 /** Build a tree having only one root cell representing the whole space.
94 */
95 public BSPTree() {
96 cut = null;
97 plus = null;
98 minus = null;
99 parent = null;
100 attribute = null;
101 }
102
103 /** Build a tree having only one root cell representing the whole space.
104 * @param attribute attribute of the tree (may be null)
105 */
106 public BSPTree(final Object attribute) {
107 cut = null;
108 plus = null;
109 minus = null;
110 parent = null;
111 this.attribute = attribute;
112 }
113
114 /** Build a BSPTree from its underlying elements.
115 * <p>This method does <em>not</em> perform any verification on
116 * consistency of its arguments, it should therefore be used only
117 * when then caller knows what it is doing.</p>
118 * <p>This method is mainly useful to build trees
119 * bottom-up. Building trees top-down is realized with the help of
120 * method {@link #insertCut insertCut}.</p>
121 * @param cut cut sub-hyperplane for the tree
122 * @param plus plus side sub-tree
123 * @param minus minus side sub-tree
124 * @param attribute attribute associated with the node (may be null)
125 * @see #insertCut
126 */
127 public BSPTree(final I cut, final BSPTree<S, P, H, I> plus, final BSPTree<S, P, H, I> minus,
128 final Object attribute) {
129 this.cut = cut;
130 this.plus = plus;
131 this.minus = minus;
132 this.parent = null;
133 this.attribute = attribute;
134 plus.parent = this;
135 minus.parent = this;
136 }
137
138 /** Insert a cut sub-hyperplane in a node.
139 * <p>The sub-tree starting at this node will be completely
140 * overwritten. The new cut sub-hyperplane will be built from the
141 * intersection of the provided hyperplane with the cell. If the
142 * hyperplane does intersect the cell, the cell will have two
143 * children cells with {@code null} attributes on each side of
144 * the inserted cut sub-hyperplane. If the hyperplane does not
145 * intersect the cell then <em>no</em> cut hyperplane will be
146 * inserted and the cell will be changed to a leaf cell. The
147 * attribute of the node is never changed.</p>
148 * <p>This method is mainly useful when called on leaf nodes
149 * (i.e. nodes for which {@link #getCut getCut} returns
150 * {@code null}), in this case it provides a way to build a
151 * tree top-down (whereas the {@link #BSPTree(SubHyperplane,
152 * BSPTree, BSPTree, Object) 4 arguments constructor} is devoted to
153 * build trees bottom-up).</p>
154 * @param hyperplane hyperplane to insert, it will be chopped in
155 * order to fit in the cell defined by the parent nodes of the
156 * instance
157 * @return true if a cut sub-hyperplane has been inserted (i.e. if
158 * the cell now has two leaf child nodes)
159 * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
160 */
161 public boolean insertCut(final H hyperplane) {
162
163 if (cut != null) {
164 plus.parent = null;
165 minus.parent = null;
166 }
167
168 final I chopped = fitToCell(hyperplane.wholeHyperplane(), null);
169 if (chopped == null || chopped.isEmpty()) {
170 cut = null;
171 plus = null;
172 minus = null;
173 return false;
174 }
175
176 cut = chopped;
177 plus = new BSPTree<>();
178 plus.parent = this;
179 minus = new BSPTree<>();
180 minus.parent = this;
181 return true;
182
183 }
184
185 /** Copy the instance.
186 * <p>The instance created is completely independent of the original
187 * one. A deep copy is used, none of the underlying objects are
188 * shared (except for the nodes attributes and immutable
189 * objects).</p>
190 * @return a new tree, copy of the instance
191 */
192 public BSPTree<S, P, H, I> copySelf() {
193
194 if (cut == null) {
195 return new BSPTree<>(attribute);
196 }
197
198 return new BSPTree<>(cut.copySelf(), plus.copySelf(), minus.copySelf(), attribute);
199
200 }
201
202 /** Get the cut sub-hyperplane.
203 * @return cut sub-hyperplane, null if this is a leaf tree
204 */
205 public I getCut() {
206 return cut;
207 }
208
209 /** Get the tree on the plus side of the cut hyperplane.
210 * @return tree on the plus side of the cut hyperplane, null if this
211 * is a leaf tree
212 */
213 public BSPTree<S, P, H, I> getPlus() {
214 return plus;
215 }
216
217 /** Get the tree on the minus side of the cut hyperplane.
218 * @return tree on the minus side of the cut hyperplane, null if this
219 * is a leaf tree
220 */
221 public BSPTree<S, P, H, I> getMinus() {
222 return minus;
223 }
224
225 /** Get the parent node.
226 * @return parent node, null if the node has no parents
227 */
228 public BSPTree<S, P, H, I> getParent() {
229 return parent;
230 }
231
232 /** Associate an attribute with the instance.
233 * @param attribute attribute to associate with the node
234 * @see #getAttribute
235 */
236 public void setAttribute(final Object attribute) {
237 this.attribute = attribute;
238 }
239
240 /** Get the attribute associated with the instance.
241 * @return attribute associated with the node or null if no
242 * attribute has been explicitly set using the {@link #setAttribute
243 * setAttribute} method
244 * @see #setAttribute
245 */
246 public Object getAttribute() {
247 return attribute;
248 }
249
250 /** Visit the BSP tree nodes.
251 * @param visitor object visiting the tree nodes
252 */
253 public void visit(final BSPTreeVisitor<S, P, H, I> visitor) {
254 if (cut == null) {
255 visitor.visitLeafNode(this);
256 } else {
257 switch (visitor.visitOrder(this)) {
258 case PLUS_MINUS_SUB:
259 plus.visit(visitor);
260 minus.visit(visitor);
261 visitor.visitInternalNode(this);
262 break;
263 case PLUS_SUB_MINUS:
264 plus.visit(visitor);
265 visitor.visitInternalNode(this);
266 minus.visit(visitor);
267 break;
268 case MINUS_PLUS_SUB:
269 minus.visit(visitor);
270 plus.visit(visitor);
271 visitor.visitInternalNode(this);
272 break;
273 case MINUS_SUB_PLUS:
274 minus.visit(visitor);
275 visitor.visitInternalNode(this);
276 plus.visit(visitor);
277 break;
278 case SUB_PLUS_MINUS:
279 visitor.visitInternalNode(this);
280 plus.visit(visitor);
281 minus.visit(visitor);
282 break;
283 case SUB_MINUS_PLUS:
284 visitor.visitInternalNode(this);
285 minus.visit(visitor);
286 plus.visit(visitor);
287 break;
288 default:
289 throw MathRuntimeException.createInternalError();
290 }
291
292 }
293 }
294
295 /** Fit a sub-hyperplane inside the cell defined by the instance.
296 * <p>Fitting is done by chopping off the parts of the
297 * sub-hyperplane that lie outside the cell using the
298 * cut-hyperplanes of the parent nodes of the instance.</p>
299 * @param sub sub-hyperplane to fit
300 * @param ignored tree node to ignore (null if all nodes should be considered)
301 * @return a new sub-hyperplane, guaranteed to have no part outside
302 * of the instance cell
303 */
304 private I fitToCell(final I sub, final BSPTree<S, P, H, I> ignored) {
305 I s = sub;
306 for (BSPTree<S, P, H, I> tree = this; tree.parent != null && s != null; tree = tree.parent) {
307 if (tree.parent != ignored) {
308 if (tree == tree.parent.plus) {
309 s = s.split(tree.parent.cut.getHyperplane()).getPlus();
310 }
311 else {
312 s = s.split(tree.parent.cut.getHyperplane()).getMinus();
313 }
314 }
315 }
316 return s;
317 }
318
319 /** Get a point that is interior to the cell.
320 * @param defaultPoint default point to return if tree is empty
321 * @return point that is interior to the cell
322 * @since 4.0
323 */
324 public InteriorPoint<S, P> getInteriorPoint(final P defaultPoint) {
325
326 // find edges/facets interior points
327 final List<P> edgePoints = new ArrayList<>();
328 for (BSPTree<S, P, H, I> n = parent; n != null; n = n.getParent()) {
329 final I fit = fitToCell(n.getCut().getHyperplane().wholeHyperplane(), n);
330 if (fit != null) {
331 final P p = fit.getInteriorPoint();
332 if (p != null) {
333 edgePoints.add(p);
334 }
335 }
336 }
337
338 if (edgePoints.isEmpty()) {
339 // there are no edges/facets interior points at all!
340 // we are in a cell representing the whole space
341 return new InteriorPoint<>(defaultPoint, Double.POSITIVE_INFINITY);
342 } else {
343 // compute barycenter of edges/facets interior point
344 final P barycenter = Geometry.barycenter(edgePoints);
345
346 // compute distance to the closest edge/facet
347 double min = Double.POSITIVE_INFINITY;
348 for (BSPTree<S, P, H, I> n = parent; n != null; n = n.getParent()) {
349 min = FastMath.min(min, FastMath.abs(n.getCut().getHyperplane().getOffset(barycenter)));
350 }
351
352 return new InteriorPoint<>(barycenter, min);
353 }
354
355 }
356
357 /** Get the cell to which a point belongs.
358 * <p>If the returned cell is a leaf node the points belongs to the
359 * interior of the node, if the cell is an internal node the points
360 * belongs to the node cut sub-hyperplane.</p>
361 * @param point point to check
362 * @param tolerance tolerance below which points close to a cut hyperplane
363 * are considered to belong to the hyperplane itself
364 * @return the tree cell to which the point belongs
365 */
366 public BSPTree<S, P, H, I> getCell(final P point, final double tolerance) {
367
368 if (cut == null) {
369 return this;
370 }
371
372 // position of the point with respect to the cut hyperplane
373 final double offset = cut.getHyperplane().getOffset(point);
374
375 if (FastMath.abs(offset) < tolerance) {
376 return this;
377 } else if (offset <= 0) {
378 // point is on the minus side of the cut hyperplane
379 return minus.getCell(point, tolerance);
380 } else {
381 // point is on the plus side of the cut hyperplane
382 return plus.getCell(point, tolerance);
383 }
384
385 }
386
387 /** Perform condensation on a tree.
388 * <p>The condensation operation is not recursive, it must be called
389 * explicitly from leaves to root.</p>
390 */
391 private void condense() {
392 if ((cut != null) && (plus.cut == null) && (minus.cut == null) &&
393 (((plus.attribute == null) && (minus.attribute == null)) ||
394 ((plus.attribute != null) && plus.attribute.equals(minus.attribute)))) {
395 attribute = (plus.attribute == null) ? minus.attribute : plus.attribute;
396 cut = null;
397 plus = null;
398 minus = null;
399 }
400 }
401
402 /** Merge a BSP tree with the instance.
403 * <p>All trees are modified (parts of them are reused in the new
404 * tree), it is the responsibility of the caller to ensure a copy
405 * has been done before if any of the former tree should be
406 * preserved, <em>no</em> such copy is done here!</p>
407 * <p>The algorithm used here is directly derived from the one
408 * described in the Naylor, Amanatides and Thibault paper (section
409 * III, Binary Partitioning of a BSP Tree).</p>
410 * @param tree other tree to merge with the instance (will be
411 * <em>unusable</em> after the operation, as well as the
412 * instance itself)
413 * @param leafMerger object implementing the final merging phase
414 * (this is where the semantic of the operation occurs, generally
415 * depending on the attribute of the leaf node)
416 * @return a new tree, result of <code>instance <op>
417 * tree</code>, this value can be ignored if parentTree is not null
418 * since all connections have already been established
419 */
420 public BSPTree<S, P, H, I> merge(final BSPTree<S, P, H, I> tree, final LeafMerger<S, P, H, I> leafMerger) {
421 final BSPTree<S, P, H, I> merged = merge(tree, leafMerger, null, false);
422 merged.fixCuts();
423 return merged;
424 }
425
426 /** Merge a BSP tree with the instance.
427 * @param tree other tree to merge with the instance (will be
428 * <em>unusable</em> after the operation, as well as the
429 * instance itself)
430 * @param leafMerger object implementing the final merging phase
431 * (this is where the semantic of the operation occurs, generally
432 * depending on the attribute of the leaf node)
433 * @param parentTree parent tree to connect to (may be null)
434 * @param isPlusChild if true and if parentTree is not null, the
435 * resulting tree should be the plus child of its parent, ignored if
436 * parentTree is null
437 * @return a new tree, result of <code>instance <op>
438 * tree</code>, this value can be ignored if parentTree is not null
439 * since all connections have already been established
440 */
441 private BSPTree<S, P, H, I> merge(final BSPTree<S, P, H, I> tree, final LeafMerger<S, P, H, I> leafMerger,
442 final BSPTree<S, P, H, I> parentTree, final boolean isPlusChild) {
443 if (cut == null) {
444 // cell/tree operation
445 return leafMerger.merge(this, tree, parentTree, isPlusChild, true);
446 } else if (tree.cut == null) {
447 // tree/cell operation
448 return leafMerger.merge(tree, this, parentTree, isPlusChild, false);
449 } else {
450 // tree/tree operation
451 final BSPTree<S, P, H, I> merged = tree.split(cut);
452 if (parentTree != null) {
453 merged.parent = parentTree;
454 if (isPlusChild) {
455 parentTree.plus = merged;
456 } else {
457 parentTree.minus = merged;
458 }
459 }
460
461 // merging phase
462 plus.merge(merged.plus, leafMerger, merged, true);
463 minus.merge(merged.minus, leafMerger, merged, false);
464 merged.condense();
465 if (merged.cut != null) {
466 merged.cut = merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane(), null);
467 }
468
469 return merged;
470
471 }
472 }
473
474 /** Fix cut sub-hyperplanes.
475 * <p>
476 * In some cases, cut sub-hyperplanes boundaries in a tree may be inconsistent.
477 * One cause can be merge operations, where some cuts are inherited from one of
478 * the merged tree, because the trees returned by {@link #split(SubHyperplane)}
479 * are not upward-consistent. Another cause can be trees built bottom-up.
480 * </p>
481 * <p>
482 * This method recomputes the sub-hyperplanes once the full tree has been built
483 * </p>
484 */
485 private void fixCuts() {
486 if (cut != null) {
487 final I fit = fitToCell(cut.getHyperplane().wholeHyperplane(), null);
488 if (fit == null) {
489 // cut sub-hyperplane vanished
490 cut = cut.getHyperplane().emptyHyperplane();
491 } else {
492 cut = fit;
493 }
494 plus.fixCuts();
495 minus.fixCuts();
496 }
497 }
498
499 /** This interface gather the merging operations between a BSP tree
500 * leaf and another BSP tree.
501 * <p>As explained in Bruce Naylor, John Amanatides and William
502 * Thibault paper <a
503 * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
504 * BSP Trees Yields Polyhedral Set Operations</a>,
505 * the operations on {@link BSPTree BSP trees} can be expressed as a
506 * generic recursive merging operation where only the final part,
507 * when one of the operand is a leaf, is specific to the real
508 * operation semantics. For example, a tree representing a region
509 * using a boolean attribute to identify inside cells and outside
510 * cells would use four different objects to implement the final
511 * merging phase of the four set operations union, intersection,
512 * difference and symmetric difference (exclusive or).</p>
513 * @param <S> Type of the space.
514 * @param <P> Type of the points in space.
515 * @param <H> Type of the hyperplane.
516 * @param <I> Type of the sub-hyperplane.
517 */
518 public interface LeafMerger<S extends Space,
519 P extends Point<S, P>,
520 H extends Hyperplane<S, P, H, I>,
521 I extends SubHyperplane<S, P, H, I>> {
522
523 /** Merge a leaf node and a tree node.
524 * <p>This method is called at the end of a recursive merging
525 * resulting from a {@code tree1.merge(tree2, leafMerger)}
526 * call, when one of the sub-trees involved is a leaf (i.e. when
527 * its cut-hyperplane is null). This is the only place where the
528 * precise semantics of the operation are required. For all upper
529 * level nodes in the tree, the merging operation is only a
530 * generic partitioning algorithm.</p>
531 * <p>Since the final operation may be non-commutative, it is
532 * important to know if the leaf node comes from the instance tree
533 * ({@code tree1}) or the argument tree
534 * ({@code tree2}). The third argument of the method is
535 * devoted to this. It can be ignored for commutative
536 * operations.</p>
537 * <p>The {@link BSPTree#insertInTree BSPTree.insertInTree} method
538 * may be useful to implement this method.</p>
539 * @param leaf leaf node (its cut hyperplane is guaranteed to be
540 * null)
541 * @param tree tree node (its cut hyperplane may be null or not)
542 * @param parentTree parent tree to connect to (may be null)
543 * @param isPlusChild if true and if parentTree is not null, the
544 * resulting tree should be the plus child of its parent, ignored if
545 * parentTree is null
546 * @param leafFromInstance if true, the leaf node comes from the
547 * instance tree ({@code tree1}) and the tree node comes from
548 * the argument tree ({@code tree2})
549 * @return the BSP tree resulting from the merging (may be one of
550 * the arguments)
551 */
552 BSPTree<S, P, H, I> merge(BSPTree<S, P, H, I> leaf, BSPTree<S, P, H, I> tree,
553 BSPTree<S, P, H, I> parentTree, boolean isPlusChild, boolean leafFromInstance);
554
555 }
556
557 /** This interface handles the corner cases when an internal node cut sub-hyperplane vanishes.
558 * <p>
559 * Such cases happens for example when a cut sub-hyperplane is inserted into
560 * another tree (during a merge operation), and is split in several parts,
561 * some of which becomes smaller than the tolerance. The corresponding node
562 * as then no cut sub-hyperplane anymore, but does have children. This interface
563 * specifies how to handle this situation.
564 * setting
565 * </p>
566 * @param <S> Type of the space.
567 * @param <P> Type of the points in space.
568 * @param <H> Type of the hyperplane.
569 * @param <I> Type of the sub-hyperplane.
570 */
571 public interface VanishingCutHandler<S extends Space,
572 P extends Point<S, P>,
573 H extends Hyperplane<S, P, H, I>,
574 I extends SubHyperplane<S, P, H, I>> {
575
576 /** Fix a node with both vanished cut and children.
577 * @param node node to fix
578 * @return fixed node
579 */
580 BSPTree<S, P, H, I> fixNode(BSPTree<S, P, H, I> node);
581
582 }
583
584 /** Split a BSP tree by an external sub-hyperplane.
585 * <p>Split a tree in two halves, on each side of the
586 * sub-hyperplane. The instance is not modified.</p>
587 * <p>The tree returned is not upward-consistent: despite all of its
588 * sub-trees cut sub-hyperplanes (including its own cut
589 * sub-hyperplane) are bounded to the current cell, it is <em>not</em>
590 * attached to any parent tree yet. This tree is intended to be
591 * later inserted into a higher level tree.</p>
592 * <p>The algorithm used here is the one given in Naylor, Amanatides
593 * and Thibault paper (section III, Binary Partitioning of a BSP
594 * Tree).</p>
595 * @param sub partitioning sub-hyperplane, must be already clipped
596 * to the convex region represented by the instance, will be used as
597 * the cut sub-hyperplane of the returned tree
598 * @return a tree having the specified sub-hyperplane as its cut
599 * sub-hyperplane, the two parts of the split instance as its two
600 * sub-trees and a null parent
601 */
602 public BSPTree<S, P, H, I> split(final I sub) {
603
604 if (cut == null) {
605 return new BSPTree<>(sub, copySelf(), new BSPTree<>(attribute), null);
606 }
607
608 final H cHyperplane = cut.getHyperplane();
609 final H sHyperplane = sub.getHyperplane();
610 final SubHyperplane.SplitSubHyperplane<S, P, H, I> subParts = sub.split(cHyperplane);
611 switch (subParts.getSide()) {
612 case PLUS :
613 { // the partitioning sub-hyperplane is entirely in the plus sub-tree
614 final BSPTree<S, P, H, I> split = plus.split(sub);
615 if (cut.split(sHyperplane).getSide() == Side.PLUS) {
616 split.plus = new BSPTree<>(cut.copySelf(), split.plus, minus.copySelf(), attribute);
617 split.plus.condense();
618 split.plus.parent = split;
619 } else {
620 split.minus = new BSPTree<>(cut.copySelf(), split.minus, minus.copySelf(), attribute);
621 split.minus.condense();
622 split.minus.parent = split;
623 }
624 return split;
625 }
626 case MINUS :
627 { // the partitioning sub-hyperplane is entirely in the minus sub-tree
628 final BSPTree<S, P, H, I> split = minus.split(sub);
629 if (cut.split(sHyperplane).getSide() == Side.PLUS) {
630 split.plus = new BSPTree<>(cut.copySelf(), plus.copySelf(), split.plus, attribute);
631 split.plus.condense();
632 split.plus.parent = split;
633 } else {
634 split.minus = new BSPTree<>(cut.copySelf(), plus.copySelf(), split.minus, attribute);
635 split.minus.condense();
636 split.minus.parent = split;
637 }
638 return split;
639 }
640 case BOTH :
641 {
642 final SubHyperplane.SplitSubHyperplane<S, P, H, I> cutParts = cut.split(sHyperplane);
643 final BSPTree<S, P, H, I> split = new BSPTree<>(sub,
644 plus.split(subParts.getPlus()),
645 minus.split(subParts.getMinus()),
646 null);
647 final BSPTree<S, P, H, I> tmp = split.plus.minus;
648 split.plus.minus = split.minus.plus;
649 split.plus.minus.parent = split.plus;
650 split.minus.plus = tmp;
651 split.minus.plus.parent = split.minus;
652 if (cutParts.getPlus() == null) {
653 split.plus.cut = cut.getHyperplane().emptyHyperplane();
654 } else {
655 split.plus.cut = cutParts.getPlus();
656 }
657 if (cutParts.getMinus() == null) {
658 split.minus.cut = cut.getHyperplane().emptyHyperplane();
659 } else {
660 split.minus.cut = cutParts.getMinus();
661 }
662 split.plus.condense();
663 split.minus.condense();
664 return split;
665
666 }
667 default :
668 return cHyperplane.sameOrientationAs(sHyperplane) ?
669 new BSPTree<>(sub, plus.copySelf(), minus.copySelf(), attribute) :
670 new BSPTree<>(sub, minus.copySelf(), plus.copySelf(), attribute);
671 }
672
673 }
674
675 /** Insert the instance into another tree.
676 * <p>The instance itself is modified so its former parent should
677 * not be used anymore.</p>
678 * @param parentTree parent tree to connect to (may be null)
679 * @param isPlusChild if true and if parentTree is not null, the
680 * resulting tree should be the plus child of its parent, ignored if
681 * parentTree is null
682 * @param vanishingHandler handler to use for handling very rare corner
683 * cases of vanishing cut sub-hyperplanes in internal nodes during merging
684 * @see LeafMerger
685 */
686 public void insertInTree(final BSPTree<S, P, H, I> parentTree, final boolean isPlusChild,
687 final VanishingCutHandler<S, P, H, I> vanishingHandler) {
688
689 // set up parent/child links
690 parent = parentTree;
691 if (parentTree != null) {
692 if (isPlusChild) {
693 parentTree.plus = this;
694 } else {
695 parentTree.minus = this;
696 }
697 }
698
699 // make sure the inserted tree lies in the cell defined by its parent nodes
700 if (cut != null) {
701
702 // explore the parent nodes from here towards tree root
703 for (BSPTree<S, P, H, I> tree = this; tree.parent != null; tree = tree.parent) {
704
705 // this is an hyperplane of some parent node
706 final H hyperplane = tree.parent.cut.getHyperplane();
707
708 // chop off the parts of the inserted tree that extend
709 // on the wrong side of this parent hyperplane
710 if (tree == tree.parent.plus) {
711 cut = cut.split(hyperplane).getPlus();
712 fixVanishingCut(vanishingHandler);
713 if (cut == null) {
714 break;
715 }
716 plus.chopOffMinus(hyperplane, vanishingHandler);
717 minus.chopOffMinus(hyperplane, vanishingHandler);
718 } else {
719 cut = cut.split(hyperplane).getMinus();
720 fixVanishingCut(vanishingHandler);
721 if (cut == null) {
722 break;
723 }
724 plus.chopOffPlus(hyperplane, vanishingHandler);
725 minus.chopOffPlus(hyperplane, vanishingHandler);
726 }
727 }
728
729 // since we may have drop some parts of the inserted tree,
730 // perform a condensation pass to keep the tree structure simple
731 condense();
732
733 }
734
735 }
736
737 /** Prune a tree around a cell.
738 * <p>
739 * This method can be used to extract a convex cell from a tree.
740 * The original cell may either be a leaf node or an internal node.
741 * If it is an internal node, it's subtree will be ignored (i.e. the
742 * extracted cell will be a leaf node in all cases). The original
743 * tree to which the original cell belongs is not touched at all,
744 * a new independent tree will be built.
745 * </p>
746 * @param cellAttribute attribute to set for the leaf node
747 * corresponding to the initial instance cell
748 * @param otherLeafsAttributes attribute to set for the other leaf
749 * nodes
750 * @param internalAttributes attribute to set for the internal nodes
751 * @return a new tree (the original tree is left untouched) containing
752 * a single branch with the cell as a leaf node, and other leaf nodes
753 * as the remnants of the pruned branches
754 */
755 public BSPTree<S, P, H, I> pruneAroundConvexCell(final Object cellAttribute,
756 final Object otherLeafsAttributes,
757 final Object internalAttributes) {
758
759 // build the current cell leaf
760 BSPTree<S, P, H, I> tree = new BSPTree<>(cellAttribute);
761
762 // build the pruned tree bottom-up
763 for (BSPTree<S, P, H, I> current = this; current.parent != null; current = current.parent) {
764 final I parentCut = current.parent.cut.copySelf();
765 final BSPTree<S, P, H, I> sibling = new BSPTree<>(otherLeafsAttributes);
766 if (current == current.parent.plus) {
767 tree = new BSPTree<>(parentCut, tree, sibling, internalAttributes);
768 } else {
769 tree = new BSPTree<>(parentCut, sibling, tree, internalAttributes);
770 }
771 }
772
773 // fix the cuts so the pruned tree is consistent
774 tree.fixCuts();
775
776 return tree;
777
778 }
779
780 /** Chop off parts of the tree.
781 * <p>The instance is modified in place, all the parts that are on
782 * the minus side of the chopping hyperplane are discarded, only the
783 * parts on the plus side remain.</p>
784 * @param hyperplane chopping hyperplane
785 * @param vanishingHandler handler to use for handling very rare corner
786 * cases of vanishing cut sub-hyperplanes in internal nodes during merging
787 */
788 private void chopOffMinus(final H hyperplane, final VanishingCutHandler<S, P, H, I> vanishingHandler) {
789 if (cut != null) {
790
791 cut = cut.split(hyperplane).getPlus();
792 plus.chopOffMinus(hyperplane, vanishingHandler);
793 minus.chopOffMinus(hyperplane, vanishingHandler);
794
795 fixVanishingCut(vanishingHandler);
796
797 }
798 }
799
800 /** Chop off parts of the tree.
801 * <p>The instance is modified in place, all the parts that are on
802 * the plus side of the chopping hyperplane are discarded, only the
803 * parts on the minus side remain.</p>
804 * @param hyperplane chopping hyperplane
805 * @param vanishingHandler handler to use for handling very rare corner
806 * cases of vanishing cut sub-hyperplanes in internal nodes during merging
807 */
808 private void chopOffPlus(final H hyperplane, final VanishingCutHandler<S, P, H, I> vanishingHandler) {
809 if (cut != null) {
810
811 cut = cut.split(hyperplane).getMinus();
812 plus.chopOffPlus(hyperplane, vanishingHandler);
813 minus.chopOffPlus(hyperplane, vanishingHandler);
814
815 fixVanishingCut(vanishingHandler);
816
817 }
818 }
819
820 /** Fix vanishing cut.
821 * @param vanishingHandler handler to use for handling very rare corner
822 */
823 private void fixVanishingCut(final VanishingCutHandler<S, P, H, I> vanishingHandler) {
824 if (cut == null) {
825 // the cut sub-hyperplane has vanished
826 final BSPTree<S, P, H, I> fixed = vanishingHandler.fixNode(this);
827 cut = fixed.cut;
828 plus = fixed.plus;
829 minus = fixed.minus;
830 attribute = fixed.attribute;
831 }
832 }
833
834 /** Container for cell interior points.
835 * @param <S> Type of the space.
836 * @param <P> Type of the points in space.
837 * @since 4.0
838 */
839 public static final class InteriorPoint <S extends Space, P extends Point<S, P>> {
840
841 /** Point. */
842 private final P point;
843
844 /** Distance to the closest edge/facet. */
845 private final double distance;
846
847 /** Simple constructor.
848 * @param point point
849 * @param distance d
850 */
851 InteriorPoint(final P point, final double distance) {
852 this.point = point;
853 this.distance = distance;
854 }
855
856 /** Get the interior point.
857 * @return interior point
858 */
859 public P getPoint() {
860 return point;
861 }
862
863 /** Get the distance to the closest edge/facet.
864 * @return distance to the closest edge/facet.
865 */
866 public double getDistance() {
867 return distance;
868 }
869
870 }
871
872 }