    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    import org.apache.commons.math3.geometry.Vector;
    021
    022    /** This interface represents a region of a space as a partition.
    023
    024     * <p>Region are subsets of a space, they can be infinite (whole
    025     * space, half space, infinite stripe ...) or finite (polygons in 2D,
    026     * polyhedrons in 3D ...). Their main characteristic is to separate
    027     * points that are considered to be <em>inside</em> the region from
    028     * points considered to be <em>outside</em> of it. In between, there
    029     * may be points on the <em>boundary</em> of the region.</p>
    030
    031     * <p>This implementation is limited to regions for which the boundary
    032     * is composed of several {@link SubHyperplane sub-hyperplanes},
    033     * including regions with no boundary at all: the whole space and the
    034     * empty region. They are not necessarily finite and not necessarily
    035     * path-connected. They can contain holes.</p>
    036
    037     * <p>Regions can be combined using the traditional sets operations :
    038     * union, intersection, difference and symetric difference (exclusive
    039     * or) for the binary operations, complement for the unary
    040     * operation.</p>
    041
    042     * @param <S> Type of the space.
    043
    044     * @version $Id: Region.java 1416643 2012-12-03 19:37:14Z tn $
    045     * @since 3.0
    046     */
    047    public interface Region<S extends Space> {
    048
    049        /** Enumerate for the location of a point with respect to the region. */
    050        public static enum Location {
    051            /** Code for points inside the partition. */
    052            INSIDE,
    053
    054            /** Code for points outside of the partition. */
    055            OUTSIDE,
    056
    057            /** Code for points on the partition boundary. */
    058            BOUNDARY;
    059        }
    060
    061        /** Build a region using the instance as a prototype.
    062         * <p>This method allow to create new instances without knowing
    063         * exactly the type of the region. It is an application of the
    064         * prototype design pattern.</p>
    065         * <p>The leaf nodes of the BSP tree <em>must</em> have a
    066         * {@code Boolean} attribute representing the inside status of
    067         * the corresponding cell (true for inside cells, false for outside
    068         * cells). In order to avoid building too many small objects, it is
    069         * recommended to use the predefined constants
    070         * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The
    071         * tree also <em>must</em> have either null internal nodes or
    072         * internal nodes representing the boundary as specified in the
    073         * {@link #getTree getTree} method).</p>
    074         * @param newTree inside/outside BSP tree representing the new region
    075         * @return the built region
    076         */
    077        Region<S> buildNew(BSPTree<S> newTree);
    078
    079        /** Copy the instance.
    080         * <p>The instance created is completely independant of the original
    081         * one. A deep copy is used, none of the underlying objects are
    082         * shared (except for the underlying tree {@code Boolean}
    083         * attributes and immutable objects).</p>
    084         * @return a new region, copy of the instance
    085         */
    086        Region<S> copySelf();
    087
    088        /** Check if the instance is empty.
    089         * @return true if the instance is empty
    090         */
    091        boolean isEmpty();
    092
    093        /** Check if the sub-tree starting at a given node is empty.
    094         * @param node root node of the sub-tree (<em>must</em> have {@link
    095         * Region Region} tree semantics, i.e. the leaf nodes must have
    096         * {@code Boolean} attributes representing an inside/outside
    097         * property)
    098         * @return true if the sub-tree starting at the given node is empty
    099         */
    100        boolean isEmpty(final BSPTree<S> node);
    101
    102        /** Check if the instance entirely contains another region.
    103         * @param region region to check against the instance
    104         * @return true if the instance contains the specified tree
    105         */
    106        boolean contains(final Region<S> region);
    107
    108        /** Check a point with respect to the region.
    109         * @param point point to check
    110         * @return a code representing the point status: either {@link
    111         * Location#INSIDE}, {@link Location#OUTSIDE} or {@link Location#BOUNDARY}
    112         */
    113        Location checkPoint(final Vector<S> point);
    114
    115        /** Get the underlying BSP tree.
    116
    117         * <p>Regions are represented by an underlying inside/outside BSP
    118         * tree whose leaf attributes are {@code Boolean} instances
    119         * representing inside leaf cells if the attribute value is
    120         * {@code true} and outside leaf cells if the attribute is
    121         * {@code false}. These leaf attributes are always present and
    122         * guaranteed to be non null.</p>
    123
    124         * <p>In addition to the leaf attributes, the internal nodes which
    125         * correspond to cells split by cut sub-hyperplanes may contain
    126         * {@link BoundaryAttribute BoundaryAttribute} objects representing
    127         * the parts of the corresponding cut sub-hyperplane that belong to
    128         * the boundary. When the boundary attributes have been computed,
    129         * all internal nodes are guaranteed to have non-null
    130         * attributes, however some {@link BoundaryAttribute
    131         * BoundaryAttribute} instances may have their {@link
    132         * BoundaryAttribute#plusInside plusInside} and {@link
    133         * BoundaryAttribute#plusOutside plusOutside} fields both null if
    134         * the corresponding cut sub-hyperplane does not have any parts
    135         * belonging to the boundary.</p>
    136
    137         * <p>Since computing the boundary is not always required and can be
    138         * time-consuming for large trees, these internal nodes attributes
    139         * are computed using lazy evaluation only when required by setting
    140         * the {@code includeBoundaryAttributes} argument to
    141         * {@code true}. Once computed, these attributes remain in the
    142         * tree, which implies that in this case, further calls to the
    143         * method for the same region will always include these attributes
    144         * regardless of the value of the
    145         * {@code includeBoundaryAttributes} argument.</p>
    146
    147         * @param includeBoundaryAttributes if true, the boundary attributes
    148         * at internal nodes are guaranteed to be included (they may be
    149         * included even if the argument is false, if they have already been
    150         * computed due to a previous call)
    151         * @return underlying BSP tree
    152         * @see BoundaryAttribute
    153         */
    154        BSPTree<S> getTree(final boolean includeBoundaryAttributes);
    155
    156        /** Get the size of the boundary.
    157         * @return the size of the boundary (this is 0 in 1D, a length in
    158         * 2D, an area in 3D ...)
    159         */
    160        double getBoundarySize();
    161
    162        /** Get the size of the instance.
    163         * @return the size of the instance (this is a length in 1D, an area
    164         * in 2D, a volume in 3D ...)
    165         */
    166        double getSize();
    167
    168        /** Get the barycenter of the instance.
    169         * @return an object representing the barycenter
    170         */
    171        Vector<S> getBarycenter();
    172
    173        /** Compute the relative position of the instance with respect to an
    174         * hyperplane.
    175         * @param hyperplane reference hyperplane
    176         * @return one of {@link Side#PLUS Side.PLUS}, {@link Side#MINUS
    177         * Side.MINUS}, {@link Side#BOTH Side.BOTH} or {@link Side#HYPER
    178         * Side.HYPER} (the latter result can occur only if the tree
    179         * contains only one cut hyperplane)
    180         */
    181        Side side(final Hyperplane<S> hyperplane);
    182
    183        /** Get the parts of a sub-hyperplane that are contained in the region.
    184         * <p>The parts of the sub-hyperplane that belong to the boundary are
    185         * <em>not</em> included in the resulting parts.</p>
    186         * @param sub sub-hyperplane traversing the region
    187         * @return filtered sub-hyperplane
    188         */
    189        SubHyperplane<S> intersection(final SubHyperplane<S> sub);
    190
    191    }