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.Space;
29
30 /** Cut sub-hyperplanes characterization with respect to inside/outside cells.
31 * @see BoundaryBuilder
32 * @param <S> Type of the space.
33 */
34 class Characterization<S extends Space> {
35
36 /** Part of the cut sub-hyperplane that touch outside cells. */
37 private SubHyperplane<S> outsideTouching;
38
39 /** Part of the cut sub-hyperplane that touch inside cells. */
40 private SubHyperplane<S> insideTouching;
41
42 /** Nodes that were used to split the outside touching part. */
43 private final NodesSet<S> outsideSplitters;
44
45 /** Nodes that were used to split the inside touching part. */
46 private final NodesSet<S> insideSplitters;
47
48 /** Simple constructor.
49 * <p>Characterization consists in splitting the specified
50 * sub-hyperplane into several parts lying in inside and outside
51 * cells of the tree. The principle is to compute characterization
52 * twice for each cut sub-hyperplane in the tree, once on the plus
53 * node and once on the minus node. The parts that have the same flag
54 * (inside/inside or outside/outside) do not belong to the boundary
55 * while parts that have different flags (inside/outside or
56 * outside/inside) do belong to the boundary.</p>
57 * @param node current BSP tree node
58 * @param sub sub-hyperplane to characterize
59 */
60 Characterization(final BSPTree<S> node, final SubHyperplane<S> sub) {
61 outsideTouching = null;
62 insideTouching = null;
63 outsideSplitters = new NodesSet<>();
64 insideSplitters = new NodesSet<>();
65 characterize(node, sub, new ArrayList<>());
66 }
67
68 /** Filter the parts of an hyperplane belonging to the boundary.
69 * <p>The filtering consist in splitting the specified
70 * sub-hyperplane into several parts lying in inside and outside
71 * cells of the tree. The principle is to call this method twice for
72 * each cut sub-hyperplane in the tree, once on the plus node and
73 * once on the minus node. The parts that have the same flag
74 * (inside/inside or outside/outside) do not belong to the boundary
75 * while parts that have different flags (inside/outside or
76 * outside/inside) do belong to the boundary.</p>
77 * @param node current BSP tree node
78 * @param sub sub-hyperplane to characterize
79 * @param splitters nodes that did split the current one
80 */
81 private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub,
82 final List<BSPTree<S>> splitters) {
83 if (node.getCut() == null) {
84 // we have reached a leaf node
85 final boolean inside = (Boolean) node.getAttribute();
86 if (inside) {
87 addInsideTouching(sub, splitters);
88 } else {
89 addOutsideTouching(sub, splitters);
90 }
91 } else {
92 final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
93 final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
94 switch (split.getSide()) {
95 case PLUS:
96 characterize(node.getPlus(), sub, splitters);
97 break;
98 case MINUS:
99 characterize(node.getMinus(), sub, splitters);
100 break;
101 case BOTH:
102 splitters.add(node);
103 characterize(node.getPlus(), split.getPlus(), splitters);
104 characterize(node.getMinus(), split.getMinus(), splitters);
105 splitters.remove(splitters.size() - 1);
106 break;
107 default:
108 // this should not happen
109 throw MathRuntimeException.createInternalError();
110 }
111 }
112 }
113
114 /** Add a part of the cut sub-hyperplane known to touch an outside cell.
115 * @param sub part of the cut sub-hyperplane known to touch an outside cell
116 * @param splitters sub-hyperplanes that did split the current one
117 */
118 private void addOutsideTouching(final SubHyperplane<S> sub,
119 final List<BSPTree<S>> splitters) {
120 if (outsideTouching == null) {
121 outsideTouching = sub;
122 } else {
123 outsideTouching = outsideTouching.reunite(sub);
124 }
125 outsideSplitters.addAll(splitters);
126 }
127
128 /** Add a part of the cut sub-hyperplane known to touch an inside cell.
129 * @param sub part of the cut sub-hyperplane known to touch an inside cell
130 * @param splitters sub-hyperplanes that did split the current one
131 */
132 private void addInsideTouching(final SubHyperplane<S> sub,
133 final List<BSPTree<S>> splitters) {
134 if (insideTouching == null) {
135 insideTouching = sub;
136 } else {
137 insideTouching = insideTouching.reunite(sub);
138 }
139 insideSplitters.addAll(splitters);
140 }
141
142 /** Check if the cut sub-hyperplane touches outside cells.
143 * @return true if the cut sub-hyperplane touches outside cells
144 */
145 public boolean touchOutside() {
146 return outsideTouching != null && !outsideTouching.isEmpty();
147 }
148
149 /** Get all the parts of the cut sub-hyperplane known to touch outside cells.
150 * @return parts of the cut sub-hyperplane known to touch outside cells
151 * (may be null or empty)
152 */
153 public SubHyperplane<S> outsideTouching() {
154 return outsideTouching;
155 }
156
157 /** Get the nodes that were used to split the outside touching part.
158 * <p>
159 * Splitting nodes are internal nodes (i.e. they have a non-null
160 * cut sub-hyperplane).
161 * </p>
162 * @return nodes that were used to split the outside touching part
163 */
164 public NodesSet<S> getOutsideSplitters() {
165 return outsideSplitters;
166 }
167
168 /** Check if the cut sub-hyperplane touches inside cells.
169 * @return true if the cut sub-hyperplane touches inside cells
170 */
171 public boolean touchInside() {
172 return insideTouching != null && !insideTouching.isEmpty();
173 }
174
175 /** Get all the parts of the cut sub-hyperplane known to touch inside cells.
176 * @return parts of the cut sub-hyperplane known to touch inside cells
177 * (may be null or empty)
178 */
179 public SubHyperplane<S> insideTouching() {
180 return insideTouching;
181 }
182
183 /** Get the nodes that were used to split the inside touching part.
184 * <p>
185 * Splitting nodes are internal nodes (i.e. they have a non-null
186 * cut sub-hyperplane).
187 * </p>
188 * @return nodes that were used to split the inside touching part
189 */
190 public NodesSet<S> getInsideSplitters() {
191 return insideSplitters;
192 }
193
194 }