001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.math3.geometry.partitioning; 018 019import java.util.HashMap; 020import java.util.Map; 021 022import org.apache.commons.math3.exception.MathIllegalArgumentException; 023import org.apache.commons.math3.exception.util.LocalizedFormats; 024import org.apache.commons.math3.geometry.Point; 025import org.apache.commons.math3.geometry.Space; 026import org.apache.commons.math3.geometry.partitioning.BSPTree.VanishingCutHandler; 027import org.apache.commons.math3.geometry.partitioning.Region.Location; 028import org.apache.commons.math3.geometry.partitioning.SubHyperplane.SplitSubHyperplane; 029 030/** This class is a factory for {@link Region}. 031 032 * @param <S> Type of the space. 033 034 * @since 3.0 035 */ 036public class RegionFactory<S extends Space> { 037 038 /** Visitor removing internal nodes attributes. */ 039 private final NodesCleaner nodeCleaner; 040 041 /** Simple constructor. 042 */ 043 public RegionFactory() { 044 nodeCleaner = new NodesCleaner(); 045 } 046 047 /** Build a convex region from a collection of bounding hyperplanes. 048 * @param hyperplanes collection of bounding hyperplanes 049 * @return a new convex region, or null if the collection is empty 050 */ 051 public Region<S> buildConvex(final Hyperplane<S> ... hyperplanes) { 052 if ((hyperplanes == null) || (hyperplanes.length == 0)) { 053 return null; 054 } 055 056 // use the first hyperplane to build the right class 057 final Region<S> region = hyperplanes[0].wholeSpace(); 058 059 // chop off parts of the space 060 BSPTree<S> node = region.getTree(false); 061 node.setAttribute(Boolean.TRUE); 062 for (final Hyperplane<S> hyperplane : hyperplanes) { 063 if (node.insertCut(hyperplane)) { 064 node.setAttribute(null); 065 node.getPlus().setAttribute(Boolean.FALSE); 066 node = node.getMinus(); 067 node.setAttribute(Boolean.TRUE); 068 } else { 069 // the hyperplane could not be inserted in the current leaf node 070 // either it is completely outside (which means the input hyperplanes 071 // are wrong), or it is parallel to a previous hyperplane 072 SubHyperplane<S> s = hyperplane.wholeHyperplane(); 073 for (BSPTree<S> tree = node; tree.getParent() != null && s != null; tree = tree.getParent()) { 074 final Hyperplane<S> other = tree.getParent().getCut().getHyperplane(); 075 final SplitSubHyperplane<S> split = s.split(other); 076 switch (split.getSide()) { 077 case HYPER : 078 // the hyperplane is parallel to a previous hyperplane 079 if (!hyperplane.sameOrientationAs(other)) { 080 // this hyperplane is opposite to the other one, 081 // the region is thinner than the tolerance, we consider it empty 082 return getComplement(hyperplanes[0].wholeSpace()); 083 } 084 // the hyperplane is an extension of an already known hyperplane, we just ignore it 085 break; 086 case PLUS : 087 // the hyperplane is outside of the current convex zone, 088 // the input hyperplanes are inconsistent 089 throw new MathIllegalArgumentException(LocalizedFormats.NOT_CONVEX_HYPERPLANES); 090 default : 091 s = split.getMinus(); 092 } 093 } 094 } 095 } 096 097 return region; 098 099 } 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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} */ 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} */ 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} */ 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 */ 298 DifferenceMerger(final Region<S> region1, final Region<S> region2) { 299 this.region1 = region1.copySelf(); 300 this.region2 = region2.copySelf(); 301 } 302 303 /** {@inheritDoc} */ 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} */ 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} */ 337 public Order visitOrder(final BSPTree<S> node) { 338 return Order.PLUS_SUB_MINUS; 339 } 340 341 /** {@inheritDoc} */ 342 public void visitInternalNode(final BSPTree<S> node) { 343 node.setAttribute(null); 344 } 345 346 /** {@inheritDoc} */ 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 */ 361 VanishingToLeaf(final boolean inside) { 362 this.inside = inside; 363 } 364 365 /** {@inheritDoc} */ 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}