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.math3.geometry.partitioning; 18 19 import java.util.HashMap; 20 import java.util.Map; 21 22 import org.apache.commons.math3.exception.MathIllegalArgumentException; 23 import org.apache.commons.math3.exception.util.LocalizedFormats; 24 import org.apache.commons.math3.geometry.Point; 25 import org.apache.commons.math3.geometry.Space; 26 import org.apache.commons.math3.geometry.partitioning.BSPTree.VanishingCutHandler; 27 import org.apache.commons.math3.geometry.partitioning.Region.Location; 28 import org.apache.commons.math3.geometry.partitioning.SubHyperplane.SplitSubHyperplane; 29 30 /** This class is a factory for {@link Region}. 31 32 * @param <S> Type of the space. 33 34 * @since 3.0 35 */ 36 public class RegionFactory<S extends Space> { 37 38 /** Visitor removing internal nodes attributes. */ 39 private final NodesCleaner nodeCleaner; 40 41 /** Simple constructor. 42 */ RegionFactory()43 public RegionFactory() { 44 nodeCleaner = new NodesCleaner(); 45 } 46 47 /** Build a convex region from a collection of bounding hyperplanes. 48 * @param hyperplanes collection of bounding hyperplanes 49 * @return a new convex region, or null if the collection is empty 50 */ buildConvex(final Hyperplane<S> ... hyperplanes)51 public Region<S> buildConvex(final Hyperplane<S> ... hyperplanes) { 52 if ((hyperplanes == null) || (hyperplanes.length == 0)) { 53 return null; 54 } 55 56 // use the first hyperplane to build the right class 57 final Region<S> region = hyperplanes[0].wholeSpace(); 58 59 // chop off parts of the space 60 BSPTree<S> node = region.getTree(false); 61 node.setAttribute(Boolean.TRUE); 62 for (final Hyperplane<S> hyperplane : hyperplanes) { 63 if (node.insertCut(hyperplane)) { 64 node.setAttribute(null); 65 node.getPlus().setAttribute(Boolean.FALSE); 66 node = node.getMinus(); 67 node.setAttribute(Boolean.TRUE); 68 } else { 69 // the hyperplane could not be inserted in the current leaf node 70 // either it is completely outside (which means the input hyperplanes 71 // are wrong), or it is parallel to a previous hyperplane 72 SubHyperplane<S> s = hyperplane.wholeHyperplane(); 73 for (BSPTree<S> tree = node; tree.getParent() != null && s != null; tree = tree.getParent()) { 74 final Hyperplane<S> other = tree.getParent().getCut().getHyperplane(); 75 final SplitSubHyperplane<S> split = s.split(other); 76 switch (split.getSide()) { 77 case HYPER : 78 // the hyperplane is parallel to a previous hyperplane 79 if (!hyperplane.sameOrientationAs(other)) { 80 // this hyperplane is opposite to the other one, 81 // the region is thinner than the tolerance, we consider it empty 82 return getComplement(hyperplanes[0].wholeSpace()); 83 } 84 // the hyperplane is an extension of an already known hyperplane, we just ignore it 85 break; 86 case PLUS : 87 // the hyperplane is outside of the current convex zone, 88 // the input hyperplanes are inconsistent 89 throw new MathIllegalArgumentException(LocalizedFormats.NOT_CONVEX_HYPERPLANES); 90 default : 91 s = split.getMinus(); 92 } 93 } 94 } 95 } 96 97 return region; 98 99 } 100 101 /** Compute the union of two regions. 102 * @param region1 first region (will be unusable after the operation as 103 * parts of it will be reused in the new region) 104 * @param region2 second region (will be unusable after the operation as 105 * parts of it will be reused in the new region) 106 * @return a new region, result of {@code region1 union region2} 107 */ union(final Region<S> region1, final Region<S> region2)108 public Region<S> union(final Region<S> region1, final Region<S> region2) { 109 final BSPTree<S> tree = 110 region1.getTree(false).merge(region2.getTree(false), new UnionMerger()); 111 tree.visit(nodeCleaner); 112 return region1.buildNew(tree); 113 } 114 115 /** Compute the intersection of two regions. 116 * @param region1 first region (will be unusable after the operation as 117 * parts of it will be reused in the new region) 118 * @param region2 second region (will be unusable after the operation as 119 * parts of it will be reused in the new region) 120 * @return a new region, result of {@code region1 intersection region2} 121 */ intersection(final Region<S> region1, final Region<S> region2)122 public Region<S> intersection(final Region<S> region1, final Region<S> region2) { 123 final BSPTree<S> tree = 124 region1.getTree(false).merge(region2.getTree(false), new IntersectionMerger()); 125 tree.visit(nodeCleaner); 126 return region1.buildNew(tree); 127 } 128 129 /** Compute the symmetric difference (exclusive or) of two regions. 130 * @param region1 first region (will be unusable after the operation as 131 * parts of it will be reused in the new region) 132 * @param region2 second region (will be unusable after the operation as 133 * parts of it will be reused in the new region) 134 * @return a new region, result of {@code region1 xor region2} 135 */ xor(final Region<S> region1, final Region<S> region2)136 public Region<S> xor(final Region<S> region1, final Region<S> region2) { 137 final BSPTree<S> tree = 138 region1.getTree(false).merge(region2.getTree(false), new XorMerger()); 139 tree.visit(nodeCleaner); 140 return region1.buildNew(tree); 141 } 142 143 /** Compute the difference of two regions. 144 * @param region1 first region (will be unusable after the operation as 145 * parts of it will be reused in the new region) 146 * @param region2 second region (will be unusable after the operation as 147 * parts of it will be reused in the new region) 148 * @return a new region, result of {@code region1 minus region2} 149 */ difference(final Region<S> region1, final Region<S> region2)150 public Region<S> difference(final Region<S> region1, final Region<S> region2) { 151 final BSPTree<S> tree = 152 region1.getTree(false).merge(region2.getTree(false), new DifferenceMerger(region1, region2)); 153 tree.visit(nodeCleaner); 154 return region1.buildNew(tree); 155 } 156 157 /** Get the complement of the region (exchanged interior/exterior). 158 * @param region region to complement, it will not modified, a new 159 * region independent region will be built 160 * @return a new region, complement of the specified one 161 */ 162 /** Get the complement of the region (exchanged interior/exterior). 163 * @param region region to complement, it will not modified, a new 164 * region independent region will be built 165 * @return a new region, complement of the specified one 166 */ getComplement(final Region<S> region)167 public Region<S> getComplement(final Region<S> region) { 168 return region.buildNew(recurseComplement(region.getTree(false))); 169 } 170 171 /** Recursively build the complement of a BSP tree. 172 * @param node current node of the original tree 173 * @return new tree, complement of the node 174 */ recurseComplement(final BSPTree<S> node)175 private BSPTree<S> recurseComplement(final BSPTree<S> node) { 176 177 // transform the tree, except for boundary attribute splitters 178 final Map<BSPTree<S>, BSPTree<S>> map = new HashMap<BSPTree<S>, BSPTree<S>>(); 179 final BSPTree<S> transformedTree = recurseComplement(node, map); 180 181 // set up the boundary attributes splitters 182 for (final Map.Entry<BSPTree<S>, BSPTree<S>> entry : map.entrySet()) { 183 if (entry.getKey().getCut() != null) { 184 @SuppressWarnings("unchecked") 185 BoundaryAttribute<S> original = (BoundaryAttribute<S>) entry.getKey().getAttribute(); 186 if (original != null) { 187 @SuppressWarnings("unchecked") 188 BoundaryAttribute<S> transformed = (BoundaryAttribute<S>) entry.getValue().getAttribute(); 189 for (final BSPTree<S> splitter : original.getSplitters()) { 190 transformed.getSplitters().add(map.get(splitter)); 191 } 192 } 193 } 194 } 195 196 return transformedTree; 197 198 } 199 200 /** Recursively build the complement of a BSP tree. 201 * @param node current node of the original tree 202 * @param map transformed nodes map 203 * @return new tree, complement of the node 204 */ recurseComplement(final BSPTree<S> node, final Map<BSPTree<S>, BSPTree<S>> map)205 private BSPTree<S> recurseComplement(final BSPTree<S> node, 206 final Map<BSPTree<S>, BSPTree<S>> map) { 207 208 final BSPTree<S> transformedNode; 209 if (node.getCut() == null) { 210 transformedNode = new BSPTree<S>(((Boolean) node.getAttribute()) ? Boolean.FALSE : Boolean.TRUE); 211 } else { 212 213 @SuppressWarnings("unchecked") 214 BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute(); 215 if (attribute != null) { 216 final SubHyperplane<S> plusOutside = 217 (attribute.getPlusInside() == null) ? null : attribute.getPlusInside().copySelf(); 218 final SubHyperplane<S> plusInside = 219 (attribute.getPlusOutside() == null) ? null : attribute.getPlusOutside().copySelf(); 220 // we start with an empty list of splitters, it will be filled in out of recursion 221 attribute = new BoundaryAttribute<S>(plusOutside, plusInside, new NodesSet<S>()); 222 } 223 224 transformedNode = new BSPTree<S>(node.getCut().copySelf(), 225 recurseComplement(node.getPlus(), map), 226 recurseComplement(node.getMinus(), map), 227 attribute); 228 } 229 230 map.put(node, transformedNode); 231 return transformedNode; 232 233 } 234 235 /** BSP tree leaf merger computing union of two regions. */ 236 private class UnionMerger implements BSPTree.LeafMerger<S> { 237 /** {@inheritDoc} */ merge(final BSPTree<S> leaf, final BSPTree<S> tree, final BSPTree<S> parentTree, final boolean isPlusChild, final boolean leafFromInstance)238 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, 239 final BSPTree<S> parentTree, 240 final boolean isPlusChild, final boolean leafFromInstance) { 241 if ((Boolean) leaf.getAttribute()) { 242 // the leaf node represents an inside cell 243 leaf.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); 244 return leaf; 245 } 246 // the leaf node represents an outside cell 247 tree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false)); 248 return tree; 249 } 250 } 251 252 /** BSP tree leaf merger computing intersection of two regions. */ 253 private class IntersectionMerger implements BSPTree.LeafMerger<S> { 254 /** {@inheritDoc} */ merge(final BSPTree<S> leaf, final BSPTree<S> tree, final BSPTree<S> parentTree, final boolean isPlusChild, final boolean leafFromInstance)255 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, 256 final BSPTree<S> parentTree, 257 final boolean isPlusChild, final boolean leafFromInstance) { 258 if ((Boolean) leaf.getAttribute()) { 259 // the leaf node represents an inside cell 260 tree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); 261 return tree; 262 } 263 // the leaf node represents an outside cell 264 leaf.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false)); 265 return leaf; 266 } 267 } 268 269 /** BSP tree leaf merger computing symmetric difference (exclusive or) of two regions. */ 270 private class XorMerger implements BSPTree.LeafMerger<S> { 271 /** {@inheritDoc} */ merge(final BSPTree<S> leaf, final BSPTree<S> tree, final BSPTree<S> parentTree, final boolean isPlusChild, final boolean leafFromInstance)272 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, 273 final BSPTree<S> parentTree, final boolean isPlusChild, 274 final boolean leafFromInstance) { 275 BSPTree<S> t = tree; 276 if ((Boolean) leaf.getAttribute()) { 277 // the leaf node represents an inside cell 278 t = recurseComplement(t); 279 } 280 t.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true)); 281 return t; 282 } 283 } 284 285 /** BSP tree leaf merger computing difference of two regions. */ 286 private class DifferenceMerger implements BSPTree.LeafMerger<S>, VanishingCutHandler<S> { 287 288 /** Region to subtract from. */ 289 private final Region<S> region1; 290 291 /** Region to subtract. */ 292 private final Region<S> region2; 293 294 /** Simple constructor. 295 * @param region1 region to subtract from 296 * @param region2 region to subtract 297 */ DifferenceMerger(final Region<S> region1, final Region<S> region2)298 DifferenceMerger(final Region<S> region1, final Region<S> region2) { 299 this.region1 = region1.copySelf(); 300 this.region2 = region2.copySelf(); 301 } 302 303 /** {@inheritDoc} */ merge(final BSPTree<S> leaf, final BSPTree<S> tree, final BSPTree<S> parentTree, final boolean isPlusChild, final boolean leafFromInstance)304 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, 305 final BSPTree<S> parentTree, final boolean isPlusChild, 306 final boolean leafFromInstance) { 307 if ((Boolean) leaf.getAttribute()) { 308 // the leaf node represents an inside cell 309 final BSPTree<S> argTree = 310 recurseComplement(leafFromInstance ? tree : leaf); 311 argTree.insertInTree(parentTree, isPlusChild, this); 312 return argTree; 313 } 314 // the leaf node represents an outside cell 315 final BSPTree<S> instanceTree = 316 leafFromInstance ? leaf : tree; 317 instanceTree.insertInTree(parentTree, isPlusChild, this); 318 return instanceTree; 319 } 320 321 /** {@inheritDoc} */ fixNode(final BSPTree<S> node)322 public BSPTree<S> fixNode(final BSPTree<S> node) { 323 // get a representative point in the degenerate cell 324 final BSPTree<S> cell = node.pruneAroundConvexCell(Boolean.TRUE, Boolean.FALSE, null); 325 final Region<S> r = region1.buildNew(cell); 326 final Point<S> p = r.getBarycenter(); 327 return new BSPTree<S>(region1.checkPoint(p) == Location.INSIDE && 328 region2.checkPoint(p) == Location.OUTSIDE); 329 } 330 331 } 332 333 /** Visitor removing internal nodes attributes. */ 334 private class NodesCleaner implements BSPTreeVisitor<S> { 335 336 /** {@inheritDoc} */ visitOrder(final BSPTree<S> node)337 public Order visitOrder(final BSPTree<S> node) { 338 return Order.PLUS_SUB_MINUS; 339 } 340 341 /** {@inheritDoc} */ visitInternalNode(final BSPTree<S> node)342 public void visitInternalNode(final BSPTree<S> node) { 343 node.setAttribute(null); 344 } 345 346 /** {@inheritDoc} */ visitLeafNode(final BSPTree<S> node)347 public void visitLeafNode(final BSPTree<S> node) { 348 } 349 350 } 351 352 /** Handler replacing nodes with vanishing cuts with leaf nodes. */ 353 private class VanishingToLeaf implements VanishingCutHandler<S> { 354 355 /** Inside/outside indocator to use for ambiguous nodes. */ 356 private final boolean inside; 357 358 /** Simple constructor. 359 * @param inside inside/outside indicator to use for ambiguous nodes 360 */ VanishingToLeaf(final boolean inside)361 VanishingToLeaf(final boolean inside) { 362 this.inside = inside; 363 } 364 365 /** {@inheritDoc} */ fixNode(final BSPTree<S> node)366 public BSPTree<S> fixNode(final BSPTree<S> node) { 367 if (node.getPlus().getAttribute().equals(node.getMinus().getAttribute())) { 368 // no ambiguity 369 return new BSPTree<S>(node.getPlus().getAttribute()); 370 } else { 371 // ambiguous node 372 return new BSPTree<S>(inside); 373 } 374 } 375 376 } 377 378 } 379