    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    }