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 */
017package org.apache.commons.math3.geometry.partitioning;
018
019import org.apache.commons.math3.geometry.Space;
020import org.apache.commons.math3.geometry.Point;
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 * <p>
043 * Note that this interface is <em>not</em> intended to be implemented
044 * by Apache Commons Math users, it is only intended to be implemented
045 * within the library itself. New methods may be added even for minor
046 * versions, which breaks compatibility for external implementations.
047 * </p>
048
049 * @param <S> Type of the space.
050
051 * @since 3.0
052 */
053public interface Region<S extends Space> {
054
055    /** Enumerate for the location of a point with respect to the region. */
056    public static enum Location {
057        /** Code for points inside the partition. */
058        INSIDE,
059
060        /** Code for points outside of the partition. */
061        OUTSIDE,
062
063        /** Code for points on the partition boundary. */
064        BOUNDARY;
065    }
066
067    /** Build a region using the instance as a prototype.
068     * <p>This method allow to create new instances without knowing
069     * exactly the type of the region. It is an application of the
070     * prototype design pattern.</p>
071     * <p>The leaf nodes of the BSP tree <em>must</em> have a
072     * {@code Boolean} attribute representing the inside status of
073     * the corresponding cell (true for inside cells, false for outside
074     * cells). In order to avoid building too many small objects, it is
075     * recommended to use the predefined constants
076     * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The
077     * tree also <em>must</em> have either null internal nodes or
078     * internal nodes representing the boundary as specified in the
079     * {@link #getTree getTree} method).</p>
080     * @param newTree inside/outside BSP tree representing the new region
081     * @return the built region
082     */
083    Region<S> buildNew(BSPTree<S> newTree);
084
085    /** Copy the instance.
086     * <p>The instance created is completely independant of the original
087     * one. A deep copy is used, none of the underlying objects are
088     * shared (except for the underlying tree {@code Boolean}
089     * attributes and immutable objects).</p>
090     * @return a new region, copy of the instance
091     */
092    Region<S> copySelf();
093
094    /** Check if the instance is empty.
095     * @return true if the instance is empty
096     */
097    boolean isEmpty();
098
099    /** Check if the sub-tree starting at a given node is empty.
100     * @param node root node of the sub-tree (<em>must</em> have {@link
101     * Region Region} tree semantics, i.e. the leaf nodes must have
102     * {@code Boolean} attributes representing an inside/outside
103     * property)
104     * @return true if the sub-tree starting at the given node is empty
105     */
106    boolean isEmpty(final BSPTree<S> node);
107
108    /** Check if the instance covers the full space.
109     * @return true if the instance covers the full space
110     */
111    boolean isFull();
112
113    /** Check if the sub-tree starting at a given node covers the full space.
114     * @param node root node of the sub-tree (<em>must</em> have {@link
115     * Region Region} tree semantics, i.e. the leaf nodes must have
116     * {@code Boolean} attributes representing an inside/outside
117     * property)
118     * @return true if the sub-tree starting at the given node covers the full space
119     */
120    boolean isFull(final BSPTree<S> node);
121
122    /** Check if the instance entirely contains another region.
123     * @param region region to check against the instance
124     * @return true if the instance contains the specified tree
125     */
126    boolean contains(final Region<S> region);
127
128    /** Check a point with respect to the region.
129     * @param point point to check
130     * @return a code representing the point status: either {@link
131     * Location#INSIDE}, {@link Location#OUTSIDE} or {@link Location#BOUNDARY}
132     */
133    Location checkPoint(final Point<S> point);
134
135    /** Project a point on the boundary of the region.
136     * @param point point to check
137     * @return projection of the point on the boundary
138     * @since 3.3
139     */
140    BoundaryProjection<S> projectToBoundary(final Point<S> point);
141
142    /** Get the underlying BSP tree.
143
144     * <p>Regions are represented by an underlying inside/outside BSP
145     * tree whose leaf attributes are {@code Boolean} instances
146     * representing inside leaf cells if the attribute value is
147     * {@code true} and outside leaf cells if the attribute is
148     * {@code false}. These leaf attributes are always present and
149     * guaranteed to be non null.</p>
150
151     * <p>In addition to the leaf attributes, the internal nodes which
152     * correspond to cells split by cut sub-hyperplanes may contain
153     * {@link BoundaryAttribute BoundaryAttribute} objects representing
154     * the parts of the corresponding cut sub-hyperplane that belong to
155     * the boundary. When the boundary attributes have been computed,
156     * all internal nodes are guaranteed to have non-null
157     * attributes, however some {@link BoundaryAttribute
158     * BoundaryAttribute} instances may have their {@link
159     * BoundaryAttribute#getPlusInside() getPlusInside} and {@link
160     * BoundaryAttribute#getPlusOutside() getPlusOutside} methods both
161     * returning null if the corresponding cut sub-hyperplane does not
162     * have any parts belonging to the boundary.</p>
163
164     * <p>Since computing the boundary is not always required and can be
165     * time-consuming for large trees, these internal nodes attributes
166     * are computed using lazy evaluation only when required by setting
167     * the {@code includeBoundaryAttributes} argument to
168     * {@code true}. Once computed, these attributes remain in the
169     * tree, which implies that in this case, further calls to the
170     * method for the same region will always include these attributes
171     * regardless of the value of the
172     * {@code includeBoundaryAttributes} argument.</p>
173
174     * @param includeBoundaryAttributes if true, the boundary attributes
175     * at internal nodes are guaranteed to be included (they may be
176     * included even if the argument is false, if they have already been
177     * computed due to a previous call)
178     * @return underlying BSP tree
179     * @see BoundaryAttribute
180     */
181    BSPTree<S> getTree(final boolean includeBoundaryAttributes);
182
183    /** Get the size of the boundary.
184     * @return the size of the boundary (this is 0 in 1D, a length in
185     * 2D, an area in 3D ...)
186     */
187    double getBoundarySize();
188
189    /** Get the size of the instance.
190     * @return the size of the instance (this is a length in 1D, an area
191     * in 2D, a volume in 3D ...)
192     */
193    double getSize();
194
195    /** Get the barycenter of the instance.
196     * @return an object representing the barycenter
197     */
198    Point<S> getBarycenter();
199
200    /** Compute the relative position of the instance with respect to an
201     * hyperplane.
202     * @param hyperplane reference hyperplane
203     * @return one of {@link Side#PLUS Side.PLUS}, {@link Side#MINUS
204     * Side.MINUS}, {@link Side#BOTH Side.BOTH} or {@link Side#HYPER
205     * Side.HYPER} (the latter result can occur only if the tree
206     * contains only one cut hyperplane)
207     */
208    Side side(final Hyperplane<S> hyperplane);
209
210    /** Get the parts of a sub-hyperplane that are contained in the region.
211     * <p>The parts of the sub-hyperplane that belong to the boundary are
212     * <em>not</em> included in the resulting parts.</p>
213     * @param sub sub-hyperplane traversing the region
214     * @return filtered sub-hyperplane
215     */
216    SubHyperplane<S> intersection(final SubHyperplane<S> sub);
217
218}