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 }