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}