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.euclidean.oned; 018 019 import java.util.ArrayList; 020 import java.util.Collection; 021 import java.util.List; 022 023 import org.apache.commons.math3.geometry.partitioning.AbstractRegion; 024 import org.apache.commons.math3.geometry.partitioning.BSPTree; 025 import org.apache.commons.math3.geometry.partitioning.SubHyperplane; 026 import org.apache.commons.math3.util.Precision; 027 028 /** This class represents a 1D region: a set of intervals. 029 * @version $Id: IntervalsSet.java 1416643 2012-12-03 19:37:14Z tn $ 030 * @since 3.0 031 */ 032 public class IntervalsSet extends AbstractRegion<Euclidean1D, Euclidean1D> { 033 034 /** Build an intervals set representing the whole real line. 035 */ 036 public IntervalsSet() { 037 super(); 038 } 039 040 /** Build an intervals set corresponding to a single interval. 041 * @param lower lower bound of the interval, must be lesser or equal 042 * to {@code upper} (may be {@code Double.NEGATIVE_INFINITY}) 043 * @param upper upper bound of the interval, must be greater or equal 044 * to {@code lower} (may be {@code Double.POSITIVE_INFINITY}) 045 */ 046 public IntervalsSet(final double lower, final double upper) { 047 super(buildTree(lower, upper)); 048 } 049 050 /** Build an intervals set from an inside/outside BSP tree. 051 * <p>The leaf nodes of the BSP tree <em>must</em> have a 052 * {@code Boolean} attribute representing the inside status of 053 * the corresponding cell (true for inside cells, false for outside 054 * cells). In order to avoid building too many small objects, it is 055 * recommended to use the predefined constants 056 * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p> 057 * @param tree inside/outside BSP tree representing the intervals set 058 */ 059 public IntervalsSet(final BSPTree<Euclidean1D> tree) { 060 super(tree); 061 } 062 063 /** Build an intervals set from a Boundary REPresentation (B-rep). 064 * <p>The boundary is provided as a collection of {@link 065 * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the 066 * interior part of the region on its minus side and the exterior on 067 * its plus side.</p> 068 * <p>The boundary elements can be in any order, and can form 069 * several non-connected sets (like for example polygons with holes 070 * or a set of disjoints polyhedrons considered as a whole). In 071 * fact, the elements do not even need to be connected together 072 * (their topological connections are not used here). However, if the 073 * boundary does not really separate an inside open from an outside 074 * open (open having here its topological meaning), then subsequent 075 * calls to the {@link 076 * org.apache.commons.math3.geometry.partitioning.Region#checkPoint(org.apache.commons.math3.geometry.Vector) 077 * checkPoint} method will not be meaningful anymore.</p> 078 * <p>If the boundary is empty, the region will represent the whole 079 * space.</p> 080 * @param boundary collection of boundary elements 081 */ 082 public IntervalsSet(final Collection<SubHyperplane<Euclidean1D>> boundary) { 083 super(boundary); 084 } 085 086 /** Build an inside/outside tree representing a single interval. 087 * @param lower lower bound of the interval, must be lesser or equal 088 * to {@code upper} (may be {@code Double.NEGATIVE_INFINITY}) 089 * @param upper upper bound of the interval, must be greater or equal 090 * to {@code lower} (may be {@code Double.POSITIVE_INFINITY}) 091 * @return the built tree 092 */ 093 private static BSPTree<Euclidean1D> buildTree(final double lower, final double upper) { 094 if (Double.isInfinite(lower) && (lower < 0)) { 095 if (Double.isInfinite(upper) && (upper > 0)) { 096 // the tree must cover the whole real line 097 return new BSPTree<Euclidean1D>(Boolean.TRUE); 098 } 099 // the tree must be open on the negative infinity side 100 final SubHyperplane<Euclidean1D> upperCut = 101 new OrientedPoint(new Vector1D(upper), true).wholeHyperplane(); 102 return new BSPTree<Euclidean1D>(upperCut, 103 new BSPTree<Euclidean1D>(Boolean.FALSE), 104 new BSPTree<Euclidean1D>(Boolean.TRUE), 105 null); 106 } 107 final SubHyperplane<Euclidean1D> lowerCut = 108 new OrientedPoint(new Vector1D(lower), false).wholeHyperplane(); 109 if (Double.isInfinite(upper) && (upper > 0)) { 110 // the tree must be open on the positive infinity side 111 return new BSPTree<Euclidean1D>(lowerCut, 112 new BSPTree<Euclidean1D>(Boolean.FALSE), 113 new BSPTree<Euclidean1D>(Boolean.TRUE), 114 null); 115 } 116 117 // the tree must be bounded on the two sides 118 final SubHyperplane<Euclidean1D> upperCut = 119 new OrientedPoint(new Vector1D(upper), true).wholeHyperplane(); 120 return new BSPTree<Euclidean1D>(lowerCut, 121 new BSPTree<Euclidean1D>(Boolean.FALSE), 122 new BSPTree<Euclidean1D>(upperCut, 123 new BSPTree<Euclidean1D>(Boolean.FALSE), 124 new BSPTree<Euclidean1D>(Boolean.TRUE), 125 null), 126 null); 127 128 } 129 130 /** {@inheritDoc} */ 131 @Override 132 public IntervalsSet buildNew(final BSPTree<Euclidean1D> tree) { 133 return new IntervalsSet(tree); 134 } 135 136 /** {@inheritDoc} */ 137 @Override 138 protected void computeGeometricalProperties() { 139 if (getTree(false).getCut() == null) { 140 setBarycenter(Vector1D.NaN); 141 setSize(((Boolean) getTree(false).getAttribute()) ? Double.POSITIVE_INFINITY : 0); 142 } else { 143 double size = 0.0; 144 double sum = 0.0; 145 for (final Interval interval : asList()) { 146 size += interval.getSize(); 147 sum += interval.getSize() * interval.getBarycenter(); 148 } 149 setSize(size); 150 if (Double.isInfinite(size)) { 151 setBarycenter(Vector1D.NaN); 152 } else if (size >= Precision.SAFE_MIN) { 153 setBarycenter(new Vector1D(sum / size)); 154 } else { 155 setBarycenter(((OrientedPoint) getTree(false).getCut().getHyperplane()).getLocation()); 156 } 157 } 158 } 159 160 /** Get the lowest value belonging to the instance. 161 * @return lowest value belonging to the instance 162 * ({@code Double.NEGATIVE_INFINITY} if the instance doesn't 163 * have any low bound, {@code Double.POSITIVE_INFINITY} if the 164 * instance is empty) 165 */ 166 public double getInf() { 167 BSPTree<Euclidean1D> node = getTree(false); 168 double inf = Double.POSITIVE_INFINITY; 169 while (node.getCut() != null) { 170 final OrientedPoint op = (OrientedPoint) node.getCut().getHyperplane(); 171 inf = op.getLocation().getX(); 172 node = op.isDirect() ? node.getMinus() : node.getPlus(); 173 } 174 return ((Boolean) node.getAttribute()) ? Double.NEGATIVE_INFINITY : inf; 175 } 176 177 /** Get the highest value belonging to the instance. 178 * @return highest value belonging to the instance 179 * ({@code Double.POSITIVE_INFINITY} if the instance doesn't 180 * have any high bound, {@code Double.NEGATIVE_INFINITY} if the 181 * instance is empty) 182 */ 183 public double getSup() { 184 BSPTree<Euclidean1D> node = getTree(false); 185 double sup = Double.NEGATIVE_INFINITY; 186 while (node.getCut() != null) { 187 final OrientedPoint op = (OrientedPoint) node.getCut().getHyperplane(); 188 sup = op.getLocation().getX(); 189 node = op.isDirect() ? node.getPlus() : node.getMinus(); 190 } 191 return ((Boolean) node.getAttribute()) ? Double.POSITIVE_INFINITY : sup; 192 } 193 194 /** Build an ordered list of intervals representing the instance. 195 * <p>This method builds this intervals set as an ordered list of 196 * {@link Interval Interval} elements. If the intervals set has no 197 * lower limit, the first interval will have its low bound equal to 198 * {@code Double.NEGATIVE_INFINITY}. If the intervals set has 199 * no upper limit, the last interval will have its upper bound equal 200 * to {@code Double.POSITIVE_INFINITY}. An empty tree will 201 * build an empty list while a tree representing the whole real line 202 * will build a one element list with both bounds beeing 203 * infinite.</p> 204 * @return a new ordered list containing {@link Interval Interval} 205 * elements 206 */ 207 public List<Interval> asList() { 208 final List<Interval> list = new ArrayList<Interval>(); 209 recurseList(getTree(false), list, 210 Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY); 211 return list; 212 } 213 214 /** Update an intervals list. 215 * @param node current node 216 * @param list list to update 217 * @param lower lower bound of the current convex cell 218 * @param upper upper bound of the current convex cell 219 */ 220 private void recurseList(final BSPTree<Euclidean1D> node, 221 final List<Interval> list, 222 final double lower, final double upper) { 223 224 if (node.getCut() == null) { 225 if ((Boolean) node.getAttribute()) { 226 // this leaf cell is an inside cell: an interval 227 list.add(new Interval(lower, upper)); 228 } 229 } else { 230 final OrientedPoint op = (OrientedPoint) node.getCut().getHyperplane(); 231 final Vector1D loc = op.getLocation(); 232 double x = loc.getX(); 233 234 // make sure we explore the tree in increasing order 235 final BSPTree<Euclidean1D> low = 236 op.isDirect() ? node.getMinus() : node.getPlus(); 237 final BSPTree<Euclidean1D> high = 238 op.isDirect() ? node.getPlus() : node.getMinus(); 239 240 recurseList(low, list, lower, x); 241 if ((checkPoint(low, loc) == Location.INSIDE) && 242 (checkPoint(high, loc) == Location.INSIDE)) { 243 // merge the last interval added and the first one of the high sub-tree 244 x = list.remove(list.size() - 1).getInf(); 245 } 246 recurseList(high, list, x, upper); 247 248 } 249 250 } 251 252 }