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