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 }