1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 public abstract class AbstractPartitionedRegionBuilder<
63 P extends Point<P>,
64 N extends AbstractRegionNode<P, N>> {
65
66
67 private static final Comparator<BSPTree.Node<?, ?>> DEEPEST_FIRST_ORDER =
68 (a, b) -> Integer.compare(b.depth(), a.depth());
69
70
71 private final AbstractRegionBSPTree<P, N> tree;
72
73
74 private final SubtreeInitializer<N> subtreeInit;
75
76
77 private boolean insertingPartitions = true;
78
79
80 private final Set<N> partitionNodes = new HashSet<>();
81
82
83
84
85
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
97
98
99 protected AbstractRegionBSPTree<P, N> buildInternal() {
100
101 tree.condense();
102
103
104
105 if (propagateRegionInterior()) {
106
107 tree.condense();
108 }
109
110 return tree;
111 }
112
113
114
115
116
117 protected void insertPartitionInternal(final HyperplaneConvexSubset<P> partition) {
118 ensureInsertingPartitions();
119
120 tree.insert(partition, RegionCutRule.INHERIT);
121 }
122
123
124
125
126 protected void insertBoundaryInternal(final HyperplaneConvexSubset<P> boundary) {
127 if (insertingPartitions) {
128
129
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
144
145
146
147
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
159
160
161
162
163
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
176
177
178
179
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
209
210
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
224
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
240
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
252
253
254
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
271
272
273
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
292
293
294
295 private boolean isPartitionNode(final N node) {
296 return partitionNodes.contains(node);
297 }
298
299
300
301
302 private void ensureInsertingPartitions() {
303 if (!insertingPartitions) {
304 throw new IllegalStateException("Cannot insert partitions after boundaries have been inserted");
305 }
306 }
307 }