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 }