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 */ 017 package org.apache.commons.math3.geometry.partitioning; 018 019 import org.apache.commons.math3.geometry.Space; 020 021 /** This class is a factory for {@link Region}. 022 023 * @param <S> Type of the space. 024 025 * @version $Id: RegionFactory.java 1416643 2012-12-03 19:37:14Z tn $ 026 * @since 3.0 027 */ 028 public class RegionFactory<S extends Space> { 029 030 /** Visitor removing internal nodes attributes. */ 031 private final NodesCleaner nodeCleaner; 032 033 /** Simple constructor. 034 */ 035 public RegionFactory() { 036 nodeCleaner = new NodesCleaner(); 037 } 038 039 /** Build a convex region from a collection of bounding hyperplanes. 040 * @param hyperplanes collection of bounding hyperplanes 041 * @return a new convex region, or null if the collection is empty 042 */ 043 public Region<S> buildConvex(final Hyperplane<S> ... hyperplanes) { 044 if ((hyperplanes == null) || (hyperplanes.length == 0)) { 045 return null; 046 } 047 048 // use the first hyperplane to build the right class 049 final Region<S> region = hyperplanes[0].wholeSpace(); 050 051 // chop off parts of the space 052 BSPTree<S> node = region.getTree(false); 053 node.setAttribute(Boolean.TRUE); 054 for (final Hyperplane<S> hyperplane : hyperplanes) { 055 if (node.insertCut(hyperplane)) { 056 node.setAttribute(null); 057 node.getPlus().setAttribute(Boolean.FALSE); 058 node = node.getMinus(); 059 node.setAttribute(Boolean.TRUE); 060 } 061 } 062 063 return region; 064 065 } 066 067 /** Compute the union of two regions. 068 * @param region1 first region (will be unusable after the operation as 069 * parts of it will be reused in the new region) 070 * @param region2 second region (will be unusable after the operation as 071 * parts of it will be reused in the new region) 072 * @return a new region, result of {@code region1 union region2} 073 */ 074 public Region<S> union(final Region<S> region1, final Region<S> region2) { 075 final BSPTree<S> tree = 076 region1.getTree(false).merge(region2.getTree(false), new UnionMerger()); 077 tree.visit(nodeCleaner); 078 return region1.buildNew(tree); 079 } 080 081 /** Compute the intersection of two regions. 082 * @param region1 first region (will be unusable after the operation as 083 * parts of it will be reused in the new region) 084 * @param region2 second region (will be unusable after the operation as 085 * parts of it will be reused in the new region) 086 * @return a new region, result of {@code region1 intersection region2} 087 */ 088 public Region<S> intersection(final Region<S> region1, final Region<S> region2) { 089 final BSPTree<S> tree = 090 region1.getTree(false).merge(region2.getTree(false), new IntersectionMerger()); 091 tree.visit(nodeCleaner); 092 return region1.buildNew(tree); 093 } 094 095 /** Compute the symmetric difference (exclusive or) of two regions. 096 * @param region1 first region (will be unusable after the operation as 097 * parts of it will be reused in the new region) 098 * @param region2 second region (will be unusable after the operation as 099 * parts of it will be reused in the new region) 100 * @return a new region, result of {@code region1 xor region2} 101 */ 102 public Region<S> xor(final Region<S> region1, final Region<S> region2) { 103 final BSPTree<S> tree = 104 region1.getTree(false).merge(region2.getTree(false), new XorMerger()); 105 tree.visit(nodeCleaner); 106 return region1.buildNew(tree); 107 } 108 109 /** Compute the difference of two regions. 110 * @param region1 first region (will be unusable after the operation as 111 * parts of it will be reused in the new region) 112 * @param region2 second region (will be unusable after the operation as 113 * parts of it will be reused in the new region) 114 * @return a new region, result of {@code region1 minus region2} 115 */ 116 public Region<S> difference(final Region<S> region1, final Region<S> region2) { 117 final BSPTree<S> tree = 118 region1.getTree(false).merge(region2.getTree(false), new DifferenceMerger()); 119 tree.visit(nodeCleaner); 120 return region1.buildNew(tree); 121 } 122 123 /** Get the complement of the region (exchanged interior/exterior). 124 * @param region region to complement, it will not modified, a new 125 * region independent region will be built 126 * @return a new region, complement of the specified one 127 */ 128 public Region<S> getComplement(final Region<S> region) { 129 return region.buildNew(recurseComplement(region.getTree(false))); 130 } 131 132 /** Recursively build the complement of a BSP tree. 133 * @param node current node of the original tree 134 * @return new tree, complement of the node 135 */ 136 private BSPTree<S> recurseComplement(final BSPTree<S> node) { 137 if (node.getCut() == null) { 138 return new BSPTree<S>(((Boolean) node.getAttribute()) ? Boolean.FALSE : Boolean.TRUE); 139 } 140 141 @SuppressWarnings("unchecked") 142 BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute(); 143 if (attribute != null) { 144 final SubHyperplane<S> plusOutside = 145 (attribute.getPlusInside() == null) ? null : attribute.getPlusInside().copySelf(); 146 final SubHyperplane<S> plusInside = 147 (attribute.getPlusOutside() == null) ? null : attribute.getPlusOutside().copySelf(); 148 attribute = new BoundaryAttribute<S>(plusOutside, plusInside); 149 } 150 151 return new BSPTree<S>(node.getCut().copySelf(), 152 recurseComplement(node.getPlus()), 153 recurseComplement(node.getMinus()), 154 attribute); 155 156 } 157 158 /** BSP tree leaf merger computing union of two regions. */ 159 private class UnionMerger implements BSPTree.LeafMerger<S> { 160 /** {@inheritDoc} */ 161 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, 162 final BSPTree<S> parentTree, 163 final boolean isPlusChild, final boolean leafFromInstance) { 164 if ((Boolean) leaf.getAttribute()) { 165 // the leaf node represents an inside cell 166 leaf.insertInTree(parentTree, isPlusChild); 167 return leaf; 168 } 169 // the leaf node represents an outside cell 170 tree.insertInTree(parentTree, isPlusChild); 171 return tree; 172 } 173 } 174 175 /** BSP tree leaf merger computing union of two regions. */ 176 private class IntersectionMerger implements BSPTree.LeafMerger<S> { 177 /** {@inheritDoc} */ 178 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, 179 final BSPTree<S> parentTree, 180 final boolean isPlusChild, final boolean leafFromInstance) { 181 if ((Boolean) leaf.getAttribute()) { 182 // the leaf node represents an inside cell 183 tree.insertInTree(parentTree, isPlusChild); 184 return tree; 185 } 186 // the leaf node represents an outside cell 187 leaf.insertInTree(parentTree, isPlusChild); 188 return leaf; 189 } 190 } 191 192 /** BSP tree leaf merger computing union of two regions. */ 193 private class XorMerger implements BSPTree.LeafMerger<S> { 194 /** {@inheritDoc} */ 195 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, 196 final BSPTree<S> parentTree, final boolean isPlusChild, 197 final boolean leafFromInstance) { 198 BSPTree<S> t = tree; 199 if ((Boolean) leaf.getAttribute()) { 200 // the leaf node represents an inside cell 201 t = recurseComplement(t); 202 } 203 t.insertInTree(parentTree, isPlusChild); 204 return t; 205 } 206 } 207 208 /** BSP tree leaf merger computing union of two regions. */ 209 private class DifferenceMerger implements BSPTree.LeafMerger<S> { 210 /** {@inheritDoc} */ 211 public BSPTree<S> merge(final BSPTree<S> leaf, final BSPTree<S> tree, 212 final BSPTree<S> parentTree, final boolean isPlusChild, 213 final boolean leafFromInstance) { 214 if ((Boolean) leaf.getAttribute()) { 215 // the leaf node represents an inside cell 216 final BSPTree<S> argTree = 217 recurseComplement(leafFromInstance ? tree : leaf); 218 argTree.insertInTree(parentTree, isPlusChild); 219 return argTree; 220 } 221 // the leaf node represents an outside cell 222 final BSPTree<S> instanceTree = 223 leafFromInstance ? leaf : tree; 224 instanceTree.insertInTree(parentTree, isPlusChild); 225 return instanceTree; 226 } 227 } 228 229 /** Visitor removing internal nodes attributes. */ 230 private class NodesCleaner implements BSPTreeVisitor<S> { 231 232 /** {@inheritDoc} */ 233 public Order visitOrder(final BSPTree<S> node) { 234 return Order.PLUS_SUB_MINUS; 235 } 236 237 /** {@inheritDoc} */ 238 public void visitInternalNode(final BSPTree<S> node) { 239 node.setAttribute(null); 240 } 241 242 /** {@inheritDoc} */ 243 public void visitLeafNode(final BSPTree<S> node) { 244 } 245 246 } 247 248 }