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 * http://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 package org.apache.commons.geometry.core.partitioning.bsp;
18
19 import java.util.ArrayList;
20 import java.util.Comparator;
21 import java.util.HashSet;
22 import java.util.List;
23 import java.util.Set;
24 import java.util.function.BiConsumer;
25
26 import org.apache.commons.geometry.core.Point;
27 import org.apache.commons.geometry.core.RegionLocation;
28 import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
29 import org.apache.commons.geometry.core.partitioning.Split;
30 import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree.SubtreeInitializer;
31 import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree.AbstractRegionNode;
32
33 /** Class encapsulating logic for building regions by inserting boundaries into a BSP
34 * tree containing structural cuts, i.e. cuts where both sides of the cut have the same region
35 * location. This technique only produces accurate results when the inserted boundaries define
36 * the entire surface of the region. However, for valid input boundaries, significant performance
37 * improvements can be achieved due to the reduced height of the tree, especially where large
38 * numbers of boundaries are involved and/or the defined region is convex.
39 *
40 * <h2>Implementation Notes</h2>
41 *
42 * <p>This class constructs regions in two phases: (1) <em>partition insertion</em> and (2) <em>boundary insertion</em>.
43 * Instances begin in the <em>partition insertion</em> phase. Here, partitions can be inserted into the empty tree
44 * using the standard BSP insertion logic. The {@link RegionCutRule#INHERIT INHERIT} cut rule is used so that the
45 * represented region remains empty even as partitions are inserted.
46 * </p>
47 *
48 * <p>The instance moves into the <em>boundary insertion</em> phase when the caller inserts the first region boundary.
49 * Attempting to insert a partition after this point results in an {@code IllegalStateException}. This ensures that
50 * partitioning cuts are always located higher up the tree than boundary cuts.</p>
51 *
52 * <p>After all boundaries are inserted, the tree undergoes final processing to ensure that the region is consistent
53 * and that unnecessary nodes are removed.</p>
54 *
55 * <p>This class does not expose any public methods so that subclasses can present their own
56 * public API, tailored to the specific types being worked with. In particular, most subclasses
57 * will want to restrict the tree types used with the algorithm, which is difficult to implement
58 * cleanly at this level.</p>
59 * @param <P> Point implementation type
60 * @param <N> BSP tree node implementation type
61 */
62 public abstract class AbstractPartitionedRegionBuilder<
63 P extends Point<P>,
64 N extends AbstractRegionNode<P, N>> {
65
66 /** Comparator for sorting nodes with the deepest nodes first. */
67 private static final Comparator<BSPTree.Node<?, ?>> DEEPEST_FIRST_ORDER =
68 (a, b) -> Integer.compare(b.depth(), a.depth());
69
70 /** Tree being constructed. */
71 private final AbstractRegionBSPTree<P, N> tree;
72
73 /** Subtree initializer for inserted boundaries. */
74 private final SubtreeInitializer<N> subtreeInit;
75
76 /** Flag indicating whether or not partitions may still be inserted into the tree. */
77 private boolean insertingPartitions = true;
78
79 /** Set of all internal nodes used as partitioning nodes. */
80 private final Set<N> partitionNodes = new HashSet<>();
81
82 /** Construct a new instance that builds a partitioned region in the given tree. The tree must
83 * be empty.
84 * @param tree tree to build the region in; must be empty
85 * @throws IllegalArgumentException if the tree is not empty
86 */
87 protected AbstractPartitionedRegionBuilder(final AbstractRegionBSPTree<P, N> tree) {
88 if (!tree.isEmpty()) {
89 throw new IllegalArgumentException("Tree must be empty");
90 }
91
92 this.tree = tree;
93 this.subtreeInit = tree.getSubtreeInitializer(RegionCutRule.MINUS_INSIDE);
94 }
95
96 /** Internal method to build and return the tree representing the final partitioned region.
97 * @return the partitioned region
98 */
99 protected AbstractRegionBSPTree<P, N> buildInternal() {
100 // condense to combine homogenous leaf nodes
101 tree.condense();
102
103 // propagate region interiors to partitioned nodes that have not received
104 // a boundary
105 if (propagateRegionInterior()) {
106 // condense again since some leaf nodes changed
107 tree.condense();
108 }
109
110 return tree;
111 }
112
113 /** Internal method to insert a partition into the tree.
114 * @param partition partition to insert
115 * @throws IllegalStateException if a boundary has previously been inserted
116 */
117 protected void insertPartitionInternal(final HyperplaneConvexSubset<P> partition) {
118 ensureInsertingPartitions();
119
120 tree.insert(partition, RegionCutRule.INHERIT);
121 }
122
123 /** Internal method to insert a region boundary into the tree.
124 * @param boundary boundary to insert
125 */
126 protected void insertBoundaryInternal(final HyperplaneConvexSubset<P> boundary) {
127 if (insertingPartitions) {
128 // switch to inserting boundaries; place all current internal nodes into
129 // a set for easy identification
130 for (final N node : tree.nodes()) {
131 if (node.isInternal()) {
132 partitionNodes.add(node);
133 }
134 }
135
136 insertingPartitions = false;
137 }
138
139 insertBoundaryRecursive(tree.getRoot(), boundary, boundary.getHyperplane().span(),
140 (leaf, cut) -> tree.setNodeCut(leaf, cut, subtreeInit));
141 }
142
143 /** Insert a region boundary into the tree.
144 * @param node node to insert into
145 * @param insert the hyperplane convex subset to insert
146 * @param trimmed version of the hyperplane convex subset filling the entire space of {@code node}
147 * @param leafFn function to apply to leaf nodes
148 */
149 private void insertBoundaryRecursive(final N node, final HyperplaneConvexSubset<P> insert,
150 final HyperplaneConvexSubset<P> trimmed, final BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) {
151 if (node.isLeaf()) {
152 leafFn.accept(node, trimmed);
153 } else {
154 insertBoundaryRecursiveInternalNode(node, insert, trimmed, leafFn);
155 }
156 }
157
158 /** Recursive boundary insertion method for internal nodes.
159 * @param node node to insert into
160 * @param insert the hyperplane convex subset to insert
161 * @param trimmed version of the hyperplane convex subset filling the entire space of {@code node}
162 * @param leafFn function to apply to leaf nodes
163 * @see #insertBoundaryRecursive(AbstractRegionNode, HyperplaneConvexSubset, HyperplaneConvexSubset, BiConsumer)
164 */
165 private void insertBoundaryRecursiveInternalNode(final N node, final HyperplaneConvexSubset<P> insert,
166 final HyperplaneConvexSubset<P> trimmed, final BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) {
167
168 final Split<? extends HyperplaneConvexSubset<P>> insertSplit =
169 insert.split(node.getCutHyperplane());
170
171 final HyperplaneConvexSubset<P> minus = insertSplit.getMinus();
172 final HyperplaneConvexSubset<P> plus = insertSplit.getPlus();
173
174 if (minus == null && plus == null && isPartitionNode(node)) {
175 // the inserted boundary lies directly on a partition; proceed down the tree with the
176 // rest of the insertion algorithm but instead of cutting the final leaf nodes, just
177 // set the location
178
179 // remove this node from the set of partition nodes since this is now a boundary cut
180 partitionNodes.remove(node);
181
182 final boolean sameOrientation = node.getCutHyperplane().similarOrientation(insert.getHyperplane());
183 final N insertMinus = sameOrientation ? node.getMinus() : node.getPlus();
184 final N insertPlus = sameOrientation ? node.getPlus() : node.getMinus();
185
186 insertBoundaryRecursive(insertMinus, insert, trimmed,
187 (leaf, cut) -> leaf.setLocation(RegionLocation.INSIDE));
188
189 insertBoundaryRecursive(insertPlus, insert, trimmed,
190 (leaf, cut) -> leaf.setLocation(RegionLocation.OUTSIDE));
191
192 } else if (minus != null || plus != null) {
193 final Split<? extends HyperplaneConvexSubset<P>> trimmedSplit =
194 trimmed.split(node.getCutHyperplane());
195
196 final HyperplaneConvexSubset<P> trimmedMinus = trimmedSplit.getMinus();
197 final HyperplaneConvexSubset<P> trimmedPlus = trimmedSplit.getPlus();
198
199 if (minus != null) {
200 insertBoundaryRecursive(node.getMinus(), minus, trimmedMinus, leafFn);
201 }
202 if (plus != null) {
203 insertBoundaryRecursive(node.getPlus(), plus, trimmedPlus, leafFn);
204 }
205 }
206 }
207
208 /** Propagate the region interior to partitioned leaf nodes that have not had a boundary
209 * inserted.
210 * @return true if any nodes were changed
211 */
212 private boolean propagateRegionInterior() {
213 final List<N> outsidePartitionedLeaves = getOutsidePartitionedLeaves();
214 outsidePartitionedLeaves.sort(DEEPEST_FIRST_ORDER);
215
216 int changeCount = 0;
217
218 N parent;
219 N sibling;
220 for (final N leaf : outsidePartitionedLeaves) {
221 parent = leaf.getParent();
222
223 // check if the parent cut touches the inside anywhere on the side opposite of
224 // this leaf; if so, then this node should also be inside
225 sibling = leaf.isMinus() ?
226 parent.getPlus() :
227 parent.getMinus();
228
229 if (touchesInside(parent.getCut(), sibling)) {
230 leaf.setLocation(RegionLocation.INSIDE);
231
232 ++changeCount;
233 }
234 }
235
236 return changeCount > 0;
237 }
238
239 /** Return a list containing all outside leaf nodes that have a parent marked as a partition node.
240 * @return a list containing all outside leaf nodes that have a parent marked as a partition node
241 */
242 private List<N> getOutsidePartitionedLeaves() {
243 final List<N> result = new ArrayList<>();
244
245 final N root = tree.getRoot();
246 collectOutsidePartitionedLeavesRecursive(root, false, result);
247
248 return result;
249 }
250
251 /** Recursively collect all outside leaf nodes that have a parent marked as a partition node.
252 * @param node root of the subtree to collect nodes from
253 * @param parentIsPartitionNode true if the parent of {@code node} is a partition node
254 * @param result list of accumulated results
255 */
256 private void collectOutsidePartitionedLeavesRecursive(final N node, final boolean parentIsPartitionNode,
257 final List<N> result) {
258 if (node != null) {
259 if (parentIsPartitionNode && node.isOutside()) {
260 result.add(node);
261 }
262
263 final boolean partitionNode = isPartitionNode(node);
264
265 collectOutsidePartitionedLeavesRecursive(node.getMinus(), partitionNode, result);
266 collectOutsidePartitionedLeavesRecursive(node.getPlus(), partitionNode, result);
267 }
268 }
269
270 /** Return true if {@code sub} touches an inside leaf node anywhere in the subtree rooted at {@code node}.
271 * @param sub convex subset to check
272 * @param node root node of the subtree to test against
273 * @return true if {@code sub} touches an inside leaf node anywhere in the subtree rooted at {@code node}
274 */
275 private boolean touchesInside(final HyperplaneConvexSubset<P> sub, final N node) {
276 if (sub != null) {
277 if (node.isLeaf()) {
278 return node.isInside();
279 } else {
280 final Split<? extends HyperplaneConvexSubset<P>> split = sub.split(node.getCutHyperplane());
281
282 return touchesInside(split.getMinus(), node.getMinus()) ||
283 touchesInside(split.getPlus(), node.getPlus());
284
285 }
286 }
287
288 return false;
289 }
290
291 /** Return true if the given node is marked as a partition node.
292 * @param node node to check
293 * @return true if the given node is marked as a partition node
294 */
295 private boolean isPartitionNode(final N node) {
296 return partitionNodes.contains(node);
297 }
298
299 /** Throw an exception if the instance is no longer accepting partitions.
300 * @throws IllegalStateException if the instance is no longer accepting partitions
301 */
302 private void ensureInsertingPartitions() {
303 if (!insertingPartitions) {
304 throw new IllegalStateException("Cannot insert partitions after boundaries have been inserted");
305 }
306 }
307 }