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 org.hipparchus.geometry.Point;
25 import org.hipparchus.geometry.Space;
26
27 /** Visitor building boundary shell tree.
28 * <p>
29 * The boundary shell is represented as {@link BoundaryAttribute boundary attributes}
30 * at each internal node.
31 * </p>
32 * @param <S> Type of the space.
33 * @param <P> Type of the points in space.
34 * @param <H> Type of the hyperplane.
35 * @param <I> Type of the sub-hyperplane.
36 */
37 class BoundaryBuilder<S extends Space, P extends Point<S, P>, H extends Hyperplane<S, P, H, I>, I extends SubHyperplane<S, P, H, I>>
38 implements BSPTreeVisitor<S, P, H, I> {
39
40 /** {@inheritDoc} */
41 @Override
42 public Order visitOrder(BSPTree<S, P, H, I> node) {
43 return Order.PLUS_MINUS_SUB;
44 }
45
46 /** {@inheritDoc} */
47 @Override
48 public void visitInternalNode(BSPTree<S, P, H, I> node) {
49
50 I plusOutside = null;
51 I plusInside = null;
52 NodesSet<S, P, H, I> splitters = null;
53
54 // characterize the cut sub-hyperplane,
55 // first with respect to the plus sub-tree
56 final Characterization<S, P, H, I> plusChar = new Characterization<>(node.getPlus(), node.getCut().copySelf());
57
58 if (plusChar.touchOutside()) {
59 // plusChar.outsideTouching() corresponds to a subset of the cut sub-hyperplane
60 // known to have outside cells on its plus side, we want to check if parts
61 // of this subset do have inside cells on their minus side
62 final Characterization<S, P, H, I> minusChar = new Characterization<>(node.getMinus(), plusChar.outsideTouching());
63 if (minusChar.touchInside()) {
64 // this part belongs to the boundary,
65 // it has the outside on its plus side and the inside on its minus side
66 plusOutside = minusChar.insideTouching();
67 splitters = new NodesSet<>();
68 splitters.addAll(minusChar.getInsideSplitters());
69 splitters.addAll(plusChar.getOutsideSplitters());
70 }
71 }
72
73 if (plusChar.touchInside()) {
74 // plusChar.insideTouching() corresponds to a subset of the cut sub-hyperplane
75 // known to have inside cells on its plus side, we want to check if parts
76 // of this subset do have outside cells on their minus side
77 final Characterization<S, P, H, I> minusChar = new Characterization<>(node.getMinus(), plusChar.insideTouching());
78 if (minusChar.touchOutside()) {
79 // this part belongs to the boundary,
80 // it has the inside on its plus side and the outside on its minus side
81 plusInside = minusChar.outsideTouching();
82 if (splitters == null) {
83 splitters = new NodesSet<>();
84 }
85 splitters.addAll(minusChar.getOutsideSplitters());
86 splitters.addAll(plusChar.getInsideSplitters());
87 }
88 }
89
90 if (splitters != null) {
91 // the parent nodes are natural splitters for boundary sub-hyperplanes
92 for (BSPTree<S, P, H, I> up = node.getParent(); up != null; up = up.getParent()) {
93 splitters.add(up);
94 }
95 }
96
97 // set the boundary attribute at non-leaf nodes
98 node.setAttribute(new BoundaryAttribute<>(plusOutside, plusInside, splitters));
99
100 }
101
102 /** {@inheritDoc} */
103 @Override
104 public void visitLeafNode(BSPTree<S, P, H, I> node) {
105 }
106
107 }