1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * https://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 /* 19 * This is not the original file distributed by the Apache Software Foundation 20 * It has been modified by the Hipparchus project 21 */ 22 package org.hipparchus.geometry.partitioning; 23 24 import org.hipparchus.geometry.Point; 25 import org.hipparchus.geometry.Space; 26 27 /** This interface represents a region of a space as a partition. 28 29 * <p>Region are subsets of a space, they can be infinite (whole 30 * space, half space, infinite stripe ...) or finite (polygons in 2D, 31 * polyhedrons in 3D ...). Their main characteristic is to separate 32 * points that are considered to be <em>inside</em> the region from 33 * points considered to be <em>outside</em> of it. In between, there 34 * may be points on the <em>boundary</em> of the region.</p> 35 36 * <p>This implementation is limited to regions for which the boundary 37 * is composed of several {@link SubHyperplane sub-hyperplanes}, 38 * including regions with no boundary at all: the whole space and the 39 * empty region. They are not necessarily finite and not necessarily 40 * path-connected. They can contain holes.</p> 41 42 * <p>Regions can be combined using the traditional sets operations : 43 * union, intersection, difference and symetric difference (exclusive 44 * or) for the binary operations, complement for the unary 45 * operation.</p> 46 47 * <p> 48 * Note that this interface is <em>not</em> intended to be implemented 49 * by Hipparchus users, it is only intended to be implemented 50 * within the library itself. New methods may be added even for minor 51 * versions, which breaks compatibility for external implementations. 52 * </p> 53 54 * @param <S> Type of the space. 55 * @param <P> Type of the points in the space. 56 * @param <H> Type of the hyperplane. 57 * @param <I> Type of the sub-hyperplane. 58 59 */ 60 public interface Region<S extends Space, P extends Point<S, P>, H extends Hyperplane<S, P, H, I>, I extends SubHyperplane<S, P, H, I>> { 61 62 /** Enumerate for the location of a point with respect to the region. */ 63 enum Location { 64 /** Code for points inside the partition. */ 65 INSIDE, 66 67 /** Code for points outside of the partition. */ 68 OUTSIDE, 69 70 /** Code for points on the partition boundary. */ 71 BOUNDARY 72 } 73 74 /** Build a region using the instance as a prototype. 75 * <p>This method allow to create new instances without knowing 76 * exactly the type of the region. It is an application of the 77 * prototype design pattern.</p> 78 * <p>The leaf nodes of the BSP tree <em>must</em> have a 79 * {@code Boolean} attribute representing the inside status of 80 * the corresponding cell (true for inside cells, false for outside 81 * cells). In order to avoid building too many small objects, it is 82 * recommended to use the predefined constants 83 * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The 84 * tree also <em>must</em> have either null internal nodes or 85 * internal nodes representing the boundary as specified in the 86 * {@link #getTree getTree} method).</p> 87 * @param newTree inside/outside BSP tree representing the new region 88 * @return the built region 89 */ 90 Region<S, P, H, I> buildNew(BSPTree<S, P, H, I> newTree); 91 92 /** Copy the instance. 93 * <p>The instance created is completely independant of the original 94 * one. A deep copy is used, none of the underlying objects are 95 * shared (except for the underlying tree {@code Boolean} 96 * attributes and immutable objects).</p> 97 * @return a new region, copy of the instance 98 */ 99 Region<S, P, H, I> copySelf(); 100 101 /** Check if the instance is empty. 102 * @return true if the instance is empty 103 */ 104 boolean isEmpty(); 105 106 /** Check if the sub-tree starting at a given node is empty. 107 * @param node root node of the sub-tree (<em>must</em> have {@link 108 * Region Region} tree semantics, i.e. the leaf nodes must have 109 * {@code Boolean} attributes representing an inside/outside 110 * property) 111 * @return true if the sub-tree starting at the given node is empty 112 */ 113 boolean isEmpty(BSPTree<S, P, H, I> node); 114 115 /** Check if the instance covers the full space. 116 * @return true if the instance covers the full space 117 */ 118 boolean isFull(); 119 120 /** Check if the sub-tree starting at a given node covers the full space. 121 * @param node root node of the sub-tree (<em>must</em> have {@link 122 * Region Region} tree semantics, i.e. the leaf nodes must have 123 * {@code Boolean} attributes representing an inside/outside 124 * property) 125 * @return true if the sub-tree starting at the given node covers the full space 126 */ 127 boolean isFull(BSPTree<S, P, H, I> node); 128 129 /** Check if the instance entirely contains another region. 130 * @param region region to check against the instance 131 * @return true if the instance contains the specified tree 132 */ 133 boolean contains(Region<S, P, H, I> region); 134 135 /** Check a point with respect to the region. 136 * @param point point to check 137 * @return a code representing the point status: either {@link 138 * Location#INSIDE}, {@link Location#OUTSIDE} or {@link Location#BOUNDARY} 139 */ 140 Location checkPoint(P point); 141 142 /** Project a point on the boundary of the region. 143 * @param point point to check 144 * @return projection of the point on the boundary 145 */ 146 BoundaryProjection<S, P> projectToBoundary(P point); 147 148 /** Get the underlying BSP tree. 149 150 * <p>Regions are represented by an underlying inside/outside BSP 151 * tree whose leaf attributes are {@code Boolean} instances 152 * representing inside leaf cells if the attribute value is 153 * {@code true} and outside leaf cells if the attribute is 154 * {@code false}. These leaf attributes are always present and 155 * guaranteed to be non null.</p> 156 157 * <p>In addition to the leaf attributes, the internal nodes which 158 * correspond to cells split by cut sub-hyperplanes may contain 159 * {@link BoundaryAttribute BoundaryAttribute} objects representing 160 * the parts of the corresponding cut sub-hyperplane that belong to 161 * the boundary. When the boundary attributes have been computed, 162 * all internal nodes are guaranteed to have non-null 163 * attributes, however some {@link BoundaryAttribute 164 * BoundaryAttribute} instances may have their {@link 165 * BoundaryAttribute#getPlusInside() getPlusInside} and {@link 166 * BoundaryAttribute#getPlusOutside() getPlusOutside} methods both 167 * returning null if the corresponding cut sub-hyperplane does not 168 * have any parts belonging to the boundary.</p> 169 170 * <p>Since computing the boundary is not always required and can be 171 * time-consuming for large trees, these internal nodes attributes 172 * are computed using lazy evaluation only when required by setting 173 * the {@code includeBoundaryAttributes} argument to 174 * {@code true}. Once computed, these attributes remain in the 175 * tree, which implies that in this case, further calls to the 176 * method for the same region will always include these attributes 177 * regardless of the value of the 178 * {@code includeBoundaryAttributes} argument.</p> 179 180 * @param includeBoundaryAttributes if true, the boundary attributes 181 * at internal nodes are guaranteed to be included (they may be 182 * included even if the argument is false, if they have already been 183 * computed due to a previous call) 184 * @return underlying BSP tree 185 * @see BoundaryAttribute 186 */ 187 BSPTree<S, P, H, I> getTree(boolean includeBoundaryAttributes); 188 189 /** Get the size of the boundary. 190 * @return the size of the boundary (this is 0 in 1D, a length in 191 * 2D, an area in 3D ...) 192 */ 193 double getBoundarySize(); 194 195 /** Get the size of the instance. 196 * @return the size of the instance (this is a length in 1D, an area 197 * in 2D, a volume in 3D ...) 198 */ 199 double getSize(); 200 201 /** Get the barycenter of the instance. 202 * @return an object representing the barycenter 203 */ 204 P getBarycenter(); 205 206 /** Get an interior point. 207 * @return an arbitrary interior point, or null if region is empty 208 * @since 4.0 209 */ 210 P getInteriorPoint(); 211 212 /** Get the parts of a sub-hyperplane that are contained in the region. 213 * <p>The parts of the sub-hyperplane that belong to the boundary are 214 * <em>not</em> included in the resulting parts.</p> 215 * @param sub sub-hyperplane traversing the region 216 * @return filtered sub-hyperplane 217 */ 218 I intersection(I sub); 219 220 }