RegionFactory.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      https://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/*
 * This is not the original file distributed by the Apache Software Foundation
 * It has been modified by the Hipparchus project
 */
package org.hipparchus.geometry.partitioning;

import java.util.HashMap;
import java.util.Map;

import org.hipparchus.exception.MathIllegalArgumentException;
import org.hipparchus.geometry.LocalizedGeometryFormats;
import org.hipparchus.geometry.Point;
import org.hipparchus.geometry.Space;
import org.hipparchus.geometry.partitioning.BSPTree.VanishingCutHandler;
import org.hipparchus.geometry.partitioning.Region.Location;
import org.hipparchus.geometry.partitioning.SubHyperplane.SplitSubHyperplane;

/** This class is a factory for {@link Region}.

 * @param <S> Type of the space.
 * @param <P> Type of the points in space.
 * @param <H> Type of the hyperplane.
 * @param <I> Type of the sub-hyperplane.

 */
public class RegionFactory<S extends Space, P extends Point<S, P>, H extends Hyperplane<S, P, H, I>, I extends SubHyperplane<S, P, H, I>> {

    /** Visitor removing internal nodes attributes. */
    private final NodesCleaner nodeCleaner;

    /** Simple constructor.
     */
    public RegionFactory() {
        nodeCleaner = new NodesCleaner();
    }

    /** Build a convex region from a collection of bounding hyperplanes.
     * @param hyperplanes collection of bounding hyperplanes
     * @return a new convex region, or null if the collection is empty
     */
    @SafeVarargs
    public final Region<S, P, H, I> buildConvex(final H... hyperplanes) {
        if ((hyperplanes == null) || (hyperplanes.length == 0)) {
            return null;
        }

        // use the first hyperplane to build the right class
        final Region<S, P, H, I> region = hyperplanes[0].wholeSpace();

        // chop off parts of the space
        BSPTree<S, P, H, I> node = region.getTree(false);
        node.setAttribute(Boolean.TRUE);
        for (final H hyperplane : hyperplanes) {
            if (node.insertCut(hyperplane)) {
                node.setAttribute(null);
                node.getPlus().setAttribute(Boolean.FALSE);
                node = node.getMinus();
                node.setAttribute(Boolean.TRUE);
            } else {
                // the hyperplane could not be inserted in the current leaf node
                // either it is completely outside (which means the input hyperplanes
                // are wrong), or it is parallel to a previous hyperplane
                I s = hyperplane.wholeHyperplane();
                for (BSPTree<S, P, H, I> tree = node; tree.getParent() != null && s != null; tree = tree.getParent()) {
                    final H         other = tree.getParent().getCut().getHyperplane();
                    final SplitSubHyperplane<S, P, H, I> split = s.split(other);
                    switch (split.getSide()) {
                        case HYPER :
                            // the hyperplane is parallel to a previous hyperplane
                            if (!hyperplane.sameOrientationAs(other)) {
                                // this hyperplane is opposite to the other one,
                                // the region is thinner than the tolerance, we consider it empty
                                return getComplement(hyperplanes[0].wholeSpace());
                            }
                            // the hyperplane is an extension of an already known hyperplane, we just ignore it
                            break;
                        case PLUS :
                        // the hyperplane is outside of the current convex zone,
                        // the input hyperplanes are inconsistent
                        throw new MathIllegalArgumentException(LocalizedGeometryFormats.NOT_CONVEX_HYPERPLANES);
                        default :
                            s = split.getMinus();
                    }
                }
            }
        }

        return region;

    }

    /** Compute the union of two regions.
     * @param region1 first region (will be unusable after the operation as
     * parts of it will be reused in the new region)
     * @param region2 second region (will be unusable after the operation as
     * parts of it will be reused in the new region)
     * @return a new region, result of {@code region1 union region2}
     */
    public Region<S, P, H, I> union(final Region<S, P, H, I> region1, final Region<S, P, H, I> region2) {
        final BSPTree<S, P, H, I> tree =
            region1.getTree(false).merge(region2.getTree(false), new UnionMerger());
        tree.visit(nodeCleaner);
        return region1.buildNew(tree);
    }

    /** Compute the intersection of two regions.
     * @param region1 first region (will be unusable after the operation as
     * parts of it will be reused in the new region)
     * @param region2 second region (will be unusable after the operation as
     * parts of it will be reused in the new region)
     * @return a new region, result of {@code region1 intersection region2}
     */
    public Region<S, P, H, I> intersection(final Region<S, P, H, I> region1, final Region<S, P, H, I> region2) {
        final BSPTree<S, P, H, I> tree =
            region1.getTree(false).merge(region2.getTree(false), new IntersectionMerger(region1, region2));
        tree.visit(nodeCleaner);
        return region1.buildNew(tree);
    }

    /** Compute the symmetric difference (exclusive or) of two regions.
     * @param region1 first region (will be unusable after the operation as
     * parts of it will be reused in the new region)
     * @param region2 second region (will be unusable after the operation as
     * parts of it will be reused in the new region)
     * @return a new region, result of {@code region1 xor region2}
     */
    public Region<S, P, H, I> xor(final Region<S, P, H, I> region1, final Region<S, P, H, I> region2) {
        final BSPTree<S, P, H, I> tree =
            region1.getTree(false).merge(region2.getTree(false), new XorMerger());
        tree.visit(nodeCleaner);
        return region1.buildNew(tree);
    }

    /** Compute the difference of two regions.
     * @param region1 first region (will be unusable after the operation as
     * parts of it will be reused in the new region)
     * @param region2 second region (will be unusable after the operation as
     * parts of it will be reused in the new region)
     * @return a new region, result of {@code region1 minus region2}
     */
    public Region<S, P, H, I> difference(final Region<S, P, H, I> region1, final Region<S, P, H, I> region2) {
        final BSPTree<S, P, H, I> tree =
            region1.getTree(false).merge(region2.getTree(false), new DifferenceMerger(region1, region2));
        tree.visit(nodeCleaner);
        return region1.buildNew(tree);
    }

     /** Get the complement of the region (exchanged interior/exterior).
     * @param region region to complement, it will not be modified, a new
     * region independent region will be built
     * @return a new region, complement of the specified one
     */
    public Region<S, P, H, I> getComplement(final Region<S, P, H, I> region) {
        return region.buildNew(recurseComplement(region.getTree(false)));
    }

    /** Recursively build the complement of a BSP tree.
     * @param node current node of the original tree
     * @return new tree, complement of the node
     */
    private BSPTree<S, P, H, I> recurseComplement(final BSPTree<S, P, H, I> node) {

        // transform the tree, except for boundary attribute splitters
        final Map<BSPTree<S, P, H, I>, BSPTree<S, P, H, I>> map = new HashMap<>();
        final BSPTree<S, P, H, I> transformedTree = recurseComplement(node, map);

        // set up the boundary attributes splitters
        for (final Map.Entry<BSPTree<S, P, H, I>, BSPTree<S, P, H, I>> entry : map.entrySet()) {
            if (entry.getKey().getCut() != null) {
                @SuppressWarnings("unchecked")
                BoundaryAttribute<S, P, H, I> original = (BoundaryAttribute<S, P, H, I>) entry.getKey().getAttribute();
                if (original != null) {
                    @SuppressWarnings("unchecked")
                    BoundaryAttribute<S, P, H, I> transformed = (BoundaryAttribute<S, P, H, I>) entry.getValue().getAttribute();
                    for (final BSPTree<S, P, H, I> splitter : original.getSplitters()) {
                        transformed.getSplitters().add(map.get(splitter));
                    }
                }
            }
        }

        return transformedTree;

    }

    /** Recursively build the complement of a BSP tree.
     * @param node current node of the original tree
     * @param map transformed nodes map
     * @return new tree, complement of the node
     */
    private BSPTree<S, P, H, I> recurseComplement(final BSPTree<S, P, H, I> node,
                                                  final Map<BSPTree<S, P, H, I>, BSPTree<S, P, H, I>> map) {

        final BSPTree<S, P, H, I> transformedNode;
        if (node.getCut() == null) {
            transformedNode = new BSPTree<>(((Boolean) node.getAttribute()) ? Boolean.FALSE : Boolean.TRUE);
        } else {

            @SuppressWarnings("unchecked")
            BoundaryAttribute<S, P, H, I> attribute = (BoundaryAttribute<S, P, H, I>) node.getAttribute();
            if (attribute != null) {
                final I plusOutside = (attribute.getPlusInside() == null) ? null : attribute.getPlusInside().copySelf();
                final I plusInside  = (attribute.getPlusOutside() == null) ? null : attribute.getPlusOutside().copySelf();
                // we start with an empty list of splitters, it will be filled in out of recursion
                attribute = new BoundaryAttribute<>(plusOutside, plusInside, new NodesSet<>());
            }

            transformedNode = new BSPTree<>(node.getCut().copySelf(),
                                            recurseComplement(node.getPlus(),  map),
                                            recurseComplement(node.getMinus(), map),
                                            attribute);
        }

        map.put(node, transformedNode);
        return transformedNode;

    }

    /** BSP tree leaf merger computing intersection of two regions. */
    private abstract class FixingMerger implements BSPTree.LeafMerger<S, P, H, I>, VanishingCutHandler<S, P, H, I> {

        /** First region. */
        private final Region<S, P, H, I> region1;

        /** Second region. */
        private final Region<S, P, H, I> region2;

        /** Simple constructor.
         * @param region1 first region
         * @param region2 second region
         */
        protected FixingMerger(final Region<S, P, H, I> region1, final Region<S, P, H, I> region2) {
            this.region1 = region1.copySelf();
            this.region2 = region2.copySelf();
        }

        /** {@inheritDoc} */
        @Override
        public BSPTree<S, P, H, I> fixNode(final BSPTree<S, P, H, I> node) {
            // get a representative point in the degenerate cell
            final BSPTree.InteriorPoint<S, P> interior = node.getInteriorPoint(node.getParent().getCut().getHyperplane().arbitraryPoint());
            return new BSPTree<>(shouldBeInside(region1.checkPoint(interior.getPoint()), region2.checkPoint(interior.getPoint())));
        }

        /**
         * Check if node should be an inside or outside node.
         * @param location1 location of representative point in region1
         * @param location2 location of representative point in region2
         * @return true if node should be an inside node
         */
        protected abstract boolean shouldBeInside(Location location1, Location location2);

    }

    /** BSP tree leaf merger computing union of two regions. */
    private class UnionMerger implements BSPTree.LeafMerger<S, P, H, I> {
        /** {@inheritDoc} */
        @Override
        public BSPTree<S, P, H, I> merge(final BSPTree<S, P, H, I> leaf, final BSPTree<S, P, H, I> tree,
                                         final BSPTree<S, P, H, I> parentTree,
                                         final boolean isPlusChild, final boolean leafFromInstance) {
            if ((Boolean) leaf.getAttribute()) {
                // the leaf node represents an inside cell
                leaf.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true));
                return leaf;
            }
            // the leaf node represents an outside cell
            tree.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(false));
            return tree;
        }
    }

    /** BSP tree leaf merger computing intersection of two regions. */
    private class IntersectionMerger extends FixingMerger {

        /** Simple constructor.
         * @param region1 first region
         * @param region2 second region
         */
        IntersectionMerger(final Region<S, P, H, I> region1, final Region<S, P, H, I> region2) {
            super(region1, region2);
        }

        /** {@inheritDoc} */
        @Override
        public BSPTree<S, P, H, I> merge(final BSPTree<S, P, H, I> leaf, final BSPTree<S, P, H, I> tree,
                                         final BSPTree<S, P, H, I> parentTree,
                                         final boolean isPlusChild, final boolean leafFromInstance) {
            if ((Boolean) leaf.getAttribute()) {
                // the leaf node represents an inside cell
                tree.insertInTree(parentTree, isPlusChild, this);
                return tree;
            }
            // the leaf node represents an outside cell
            leaf.insertInTree(parentTree, isPlusChild, this);
            return leaf;
        }

        /** {@inheritDoc} */
        @Override
        protected boolean shouldBeInside(final Location location1, final Location location2)
        {
            return !(location1.equals(Location.OUTSIDE) || location2.equals(Location.OUTSIDE));
        }

    }

    /** BSP tree leaf merger computing symmetric difference (exclusive or) of two regions. */
    private class XorMerger implements BSPTree.LeafMerger<S, P, H, I> {
        /** {@inheritDoc} */
        @Override
        public BSPTree<S, P, H, I> merge(final BSPTree<S, P, H, I> leaf, final BSPTree<S, P, H, I> tree,
                                         final BSPTree<S, P, H, I> parentTree, final boolean isPlusChild,
                                         final boolean leafFromInstance) {
            BSPTree<S, P, H, I> t = tree;
            if ((Boolean) leaf.getAttribute()) {
                // the leaf node represents an inside cell
                t = recurseComplement(t);
            }
            t.insertInTree(parentTree, isPlusChild, new VanishingToLeaf(true));
            return t;
        }
    }

    /** BSP tree leaf merger computing difference of two regions. */
    private class DifferenceMerger extends FixingMerger {

        /** Simple constructor.
         * @param region1 region to subtract from
         * @param region2 region to subtract
         */
        DifferenceMerger(final Region<S, P, H, I> region1, final Region<S, P, H, I> region2) {
            super(region1, region2);
        }

        /** {@inheritDoc} */
        @Override
        public BSPTree<S, P, H, I> merge(final BSPTree<S, P, H, I> leaf, final BSPTree<S, P, H, I> tree,
                                         final BSPTree<S, P, H, I> parentTree, final boolean isPlusChild,
                                         final boolean leafFromInstance) {
            if ((Boolean) leaf.getAttribute()) {
                // the leaf node represents an inside cell
                final BSPTree<S, P, H, I> argTree =
                    recurseComplement(leafFromInstance ? tree : leaf);
                argTree.insertInTree(parentTree, isPlusChild, this);
                return argTree;
            }
            // the leaf node represents an outside cell
            final BSPTree<S, P, H, I> instanceTree =
                leafFromInstance ? leaf : tree;
            instanceTree.insertInTree(parentTree, isPlusChild, this);
            return instanceTree;
        }

        /** {@inheritDoc} */
        @Override
        protected boolean shouldBeInside(final Location location1, final Location location2) {
            return location1 == Location.INSIDE && location2 == Location.OUTSIDE;
        }

    }

    /** Visitor removing internal nodes attributes. */
    private class NodesCleaner implements  BSPTreeVisitor<S, P, H, I> {

        /** {@inheritDoc} */
        @Override
        public Order visitOrder(final BSPTree<S, P, H, I> node) {
            return Order.PLUS_SUB_MINUS;
        }

        /** {@inheritDoc} */
        @Override
        public void visitInternalNode(final BSPTree<S, P, H, I> node) {
            node.setAttribute(null);
        }

        /** {@inheritDoc} */
        @Override
        public void visitLeafNode(final BSPTree<S, P, H, I> node) {
        }

    }

    /** Handler replacing nodes with vanishing cuts with leaf nodes. */
    private class VanishingToLeaf implements VanishingCutHandler<S, P, H, I> {

        /** Inside/outside indicator to use for ambiguous nodes. */
        private final boolean inside;

        /** Simple constructor.
         * @param inside inside/outside indicator to use for ambiguous nodes
         */
        VanishingToLeaf(final boolean inside) {
            this.inside = inside;
        }

        /** {@inheritDoc} */
        @Override
        public BSPTree<S, P, H, I> fixNode(final BSPTree<S, P, H, I> node) {
            if (node.getPlus().getAttribute().equals(node.getMinus().getAttribute())) {
                // no ambiguity
                return new BSPTree<>(node.getPlus().getAttribute());
            } else {
                // ambiguous node
                return new BSPTree<>(inside);
            }
        }

    }

}