    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    }