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    }