View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   */
    17  package org.apache.commons.geometry.euclidean.oned;
    18
    19  import java.text.MessageFormat;
    20
    21  import org.apache.commons.geometry.core.RegionLocation;
    22  import org.apache.commons.geometry.core.Transform;
    23  import org.apache.commons.geometry.core.partitioning.Hyperplane;
    24  import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
    25  import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
    26  import org.apache.commons.geometry.core.partitioning.Split;
    27  import org.apache.commons.numbers.core.Precision;
    28
    29  /** Class representing an interval in one dimension. The interval is defined
    30   * by minimum and maximum values. One or both of these values may be infinite
    31   * although not with the same sign.
    32   *
    33   * <p>Instances of this class are guaranteed to be immutable.</p>
    34   */
    35  public final class Interval implements HyperplaneBoundedRegion<Vector1D> {
    36      /** Interval instance representing the entire real number line. */
    37      private static final Interval FULL = new Interval(null, null);
    38
    39      /** {@link OrientedPoint} instance representing the min boundary of the interval,
    40       * or null if no min boundary exists. If present, this instance will be negative-facing.
    41       * Infinite values are allowed but not NaN.
    42       */
    43      private final OrientedPoint minBoundary;
    44
    45      /** {@link OrientedPoint} instance representing the max boundary of the interval,
    46       * or null if no max boundary exists. If present, this instance will be negative-facing.
    47       * Infinite values are allowed but not NaN.
    48       */
    49      private final OrientedPoint maxBoundary;
    50
    51      /** Create an instance from min and max bounding hyperplanes. No validation is performed.
    52       * Callers are responsible for ensuring that the given hyperplanes represent a valid
    53       * interval.
    54       * @param minBoundary the min (negative-facing) hyperplane
    55       * @param maxBoundary the max (positive-facing) hyperplane
    56       */
    57      private Interval(final OrientedPoint minBoundary, final OrientedPoint maxBoundary) {
    58          this.minBoundary = minBoundary;
    59          this.maxBoundary = maxBoundary;
    60      }
    61
    62      /** Get the minimum value for the interval or {@link Double#NEGATIVE_INFINITY}
    63       * if no minimum value exists.
    64       * @return the minimum value for the interval or {@link Double#NEGATIVE_INFINITY}
    65       *      if no minimum value exists.
    66       */
    67      public double getMin() {
    68          return (minBoundary != null) ? minBoundary.getLocation() : Double.NEGATIVE_INFINITY;
    69      }
    70
    71      /** Get the maximum value for the interval or {@link Double#POSITIVE_INFINITY}
    72       * if no maximum value exists.
    73       * @return the maximum value for the interval or {@link Double#POSITIVE_INFINITY}
    74       *      if no maximum value exists.
    75       */
    76      public double getMax() {
    77          return (maxBoundary != null) ? maxBoundary.getLocation() : Double.POSITIVE_INFINITY;
    78      }
    79
    80      /**
    81       * Get the {@link OrientedPoint} forming the minimum bounding hyperplane
    82       * of the interval, or null if none exists. If present, This hyperplane
    83       * is oriented to point in the negative direction.
    84       * @return the hyperplane forming the minimum boundary of the interval or
    85       *      null if no minimum boundary exists
    86       */
    87      public OrientedPoint getMinBoundary() {
    88          return minBoundary;
    89      }
    90
    91      /**
    92       * Get the {@link OrientedPoint} forming the maximum bounding hyperplane
    93       * of the interval, or null if none exists. If present, this hyperplane
    94       * is oriented to point in the positive direction.
    95       * @return the hyperplane forming the maximum boundary of the interval or
    96       *      null if no maximum boundary exists
    97       */
    98      public OrientedPoint getMaxBoundary() {
    99          return maxBoundary;
    100     }
    101
    102     /** Return true if the interval has a minimum (lower) boundary.
    103      * @return true if the interval has minimum (lower) boundary
    104      */
    105     public boolean hasMinBoundary() {
    106         return minBoundary != null;
    107     }
    108
    109     /** Return true if the interval has a maximum (upper) boundary.
    110      * @return true if the interval has maximum (upper) boundary
    111      */
    112     public boolean hasMaxBoundary() {
    113         return maxBoundary != null;
    114     }
    115
    116     /** True if the region is infinite, meaning that at least one of the boundaries
    117      * does not exist.
    118      * @return true if the region is infinite
    119      */
    120     @Override
    121     public boolean isInfinite() {
    122         return minBoundary == null || maxBoundary == null;
    123     }
    124
    125     /** True if the region is finite, meaning that both the minimum and maximum
    126      * boundaries exist and the region size is finite.
    127      * @return true if the region is finite
    128      */
    129     @Override
    130     public boolean isFinite() {
    131         return !isInfinite();
    132     }
    133
    134     /** {@inheritDoc} */
    135     @Override
    136     public RegionLocation classify(final Vector1D pt) {
    137         return classify(pt.getX());
    138     }
    139
    140     /** Classify a point with respect to the interval.
    141      * @param location the location to classify
    142      * @return the classification of the point with respect to the interval
    143      * @see #classify(Vector1D)
    144      */
    145     public RegionLocation classify(final double location) {
    146         final RegionLocation minLoc = classifyWithBoundary(location, minBoundary);
    147         final RegionLocation maxLoc = classifyWithBoundary(location, maxBoundary);
    148
    149         if (minLoc == RegionLocation.BOUNDARY || maxLoc == RegionLocation.BOUNDARY) {
    150             return RegionLocation.BOUNDARY;
    151         } else if (minLoc == RegionLocation.INSIDE && maxLoc == RegionLocation.INSIDE) {
    152             return RegionLocation.INSIDE;
    153         }
    154         return RegionLocation.OUTSIDE;
    155     }
    156
    157     /** Classify the location using the given interval boundary, which may be null.
    158      * @param location the location to classify
    159      * @param boundary interval boundary to classify against
    160      * @return the location of the point relative to the boundary
    161      */
    162     private RegionLocation classifyWithBoundary(final double location, final OrientedPoint boundary) {
    163         if (Double.isNaN(location)) {
    164             return RegionLocation.OUTSIDE;
    165         } else if (boundary == null) {
    166             return RegionLocation.INSIDE;
    167         } else {
    168             final HyperplaneLocation hyperLoc = boundary.classify(location);
    169
    170             if (hyperLoc == HyperplaneLocation.ON) {
    171                 return RegionLocation.BOUNDARY;
    172             } else if (hyperLoc == HyperplaneLocation.PLUS) {
    173                 return RegionLocation.OUTSIDE;
    174             }
    175             return RegionLocation.INSIDE;
    176         }
    177     }
    178
    179     /** Return true if the given point location is on the inside or boundary
    180      * of the region.
    181      * @param x the location to test
    182      * @return true if the location is on the inside or boundary of the region
    183      * @see #contains(org.apache.commons.geometry.core.Point)
    184      */
    185     public boolean contains(final double x) {
    186         return classify(x) != RegionLocation.OUTSIDE;
    187     }
    188
    189     /** {@inheritDoc}
    190      *
    191      * <p>The point is projected onto the nearest interval boundary. When a point
    192      * is on the inside of the interval and is equidistant from both boundaries,
    193      * then the minimum boundary is selected. when a point is on the outside of the
    194      * interval and is equidistant from both boundaries (as is the case for intervals
    195      * representing a single point), then the boundary facing the point is returned,
    196      * ensuring that the returned offset is positive.
    197      * </p>
    198      */
    199     @Override
    200     public Vector1D project(final Vector1D pt) {
    201
    202         OrientedPoint boundary = null;
    203
    204         if (minBoundary != null && maxBoundary != null) {
    205             // both boundaries are present; use the closest
    206             final double minOffset = minBoundary.offset(pt.getX());
    207             final double maxOffset = maxBoundary.offset(pt.getX());
    208
    209             final double minDist = Math.abs(minOffset);
    210             final double maxDist = Math.abs(maxOffset);
    211
    212             // Project onto the max boundary if it's the closest or the point is on its plus side.
    213             // Otherwise, project onto the min boundary.
    214             if (maxDist < minDist || maxOffset > 0) {
    215                 boundary = maxBoundary;
    216             } else {
    217                 boundary = minBoundary;
    218             }
    219         } else if (minBoundary != null) {
    220             // only the min boundary is present
    221             boundary = minBoundary;
    222         } else if (maxBoundary != null) {
    223             // only the max boundary is present
    224             boundary = maxBoundary;
    225         }
    226
    227         return (boundary != null) ? boundary.project(pt) : null;
    228     }
    229
    230     /** Return a new instance transformed by the argument.
    231      * @param transform transform to apply
    232      * @return a new instance transformed by the argument
    233      */
    234     public Interval transform(final Transform<Vector1D> transform) {
    235         final OrientedPoint transformedMin = (minBoundary != null) ?
    236                 minBoundary.transform(transform) :
    237                 null;
    238         final OrientedPoint transformedMax = (maxBoundary != null) ?
    239                 maxBoundary.transform(transform) :
    240                 null;
    241
    242         return of(transformedMin, transformedMax);
    243     }
    244
    245     /** {@inheritDoc}
    246      *
    247      *  <p>This method always returns false since there is always at least
    248      *  one point that can be classified as not being on the outside of
    249      *  the region.</p>
    250      */
    251     @Override
    252     public boolean isEmpty() {
    253         return false;
    254     }
    255
    256     /** {@inheritDoc} */
    257     @Override
    258     public boolean isFull() {
    259         return minBoundary == null && maxBoundary == null;
    260     }
    261
    262     /** {@inheritDoc} */
    263     @Override
    264     public double getSize() {
    265         if (isInfinite()) {
    266             return Double.POSITIVE_INFINITY;
    267         }
    268
    269         return getMax() - getMin();
    270     }
    271
    272     /** {@inheritDoc}
    273      *
    274      *  <p>This method simply returns 0 because boundaries in one dimension do not
    275      *  have any size.</p>
    276      */
    277     @Override
    278     public double getBoundarySize() {
    279         return 0;
    280     }
    281
    282     /** {@inheritDoc} */
    283     @Override
    284     public Vector1D getCentroid() {
    285         if (isInfinite()) {
    286             return null;
    287         }
    288
    289         final double min = getMin();
    290         final double max = getMax();
    291
    292         return Vector1D.of((0.5 * (max - min)) + min);
    293     }
    294
    295     /** {@inheritDoc} */
    296     @Override
    297     public Split<Interval> split(final Hyperplane<Vector1D> splitter) {
    298         final OrientedPoint splitOrientedPoint = (OrientedPoint) splitter;
    299         final Vector1D splitPoint = splitOrientedPoint.getPoint();
    300
    301         final HyperplaneLocation splitterMinLoc = (minBoundary != null) ? minBoundary.classify(splitPoint) : null;
    302         final HyperplaneLocation splitterMaxLoc = (maxBoundary != null) ? maxBoundary.classify(splitPoint) : null;
    303
    304         Interval low = null;
    305         Interval high = null;
    306
    307         if (splitterMinLoc != HyperplaneLocation.ON || splitterMaxLoc != HyperplaneLocation.ON) {
    308
    309             if (splitterMinLoc != null && splitterMinLoc != HyperplaneLocation.MINUS) {
    310                 // splitter is on or below min boundary
    311                 high = this;
    312             } else if (splitterMaxLoc != null && splitterMaxLoc != HyperplaneLocation.MINUS) {
    313                 // splitter is on or above max boundary
    314                 low = this;
    315             } else {
    316                 // the interval is split in two
    317                 low = new Interval(minBoundary, OrientedPoints.createPositiveFacing(
    318                         splitPoint, splitOrientedPoint.getPrecision()));
    319                 high = new Interval(OrientedPoints.createNegativeFacing(
    320                         splitPoint, splitOrientedPoint.getPrecision()), maxBoundary);
    321             }
    322         }
    323
    324         // assign minus/plus based on the orientation of the splitter
    325         final boolean lowIsMinus = splitOrientedPoint.isPositiveFacing();
    326         final Interval minus = lowIsMinus ? low : high;
    327         final Interval plus = lowIsMinus ? high : low;
    328
    329         return new Split<>(minus, plus);
    330     }
    331
    332     /** Return a {@link RegionBSPTree1D} representing the same region as this instance.
    333      * @return a BSP tree representing the same region
    334      * @see RegionBSPTree1D#from(Interval, Interval...)
    335      */
    336     public RegionBSPTree1D toTree() {
    337         return RegionBSPTree1D.from(this);
    338     }
    339
    340     /** {@inheritDoc} */
    341     @Override
    342     public String toString() {
    343         final StringBuilder sb = new StringBuilder();
    344         sb.append(this.getClass().getSimpleName())
    345             .append("[min= ")
    346             .append(getMin())
    347             .append(", max= ")
    348             .append(getMax())
    349             .append(']');
    350
    351         return sb.toString();
    352     }
    353
    354     /** Create a new interval from the given point locations. The returned interval represents
    355      * the region between the points, regardless of the order they are given as arguments.
    356      * @param a first point location
    357      * @param b second point location
    358      * @param precision precision context used to compare floating point numbers
    359      * @return a new interval representing the region between the given point locations
    360      * @throws IllegalArgumentException if either number is {@link Double#NaN NaN} or the numbers
    361      *      are both infinite and have the same sign
    362      */
    363     public static Interval of(final double a, final double b, final Precision.DoubleEquivalence precision) {
    364         validateIntervalValues(a, b);
    365
    366         final double min = Math.min(a, b);
    367         final double max = Math.max(a, b);
    368
    369         final OrientedPoint minBoundary = Double.isFinite(min) ?
    370                 OrientedPoints.fromLocationAndDirection(min, false, precision) :
    371                 null;
    372
    373         final OrientedPoint maxBoundary = Double.isFinite(max) ?
    374                 OrientedPoints.fromLocationAndDirection(max, true, precision) :
    375                 null;
    376
    377         if (minBoundary == null && maxBoundary == null) {
    378             return FULL;
    379         }
    380
    381         return new Interval(minBoundary, maxBoundary);
    382     }
    383
    384     /** Create a new interval from the given points. The returned interval represents
    385      * the region between the points, regardless of the order they are given as arguments.
    386      * @param a first point
    387      * @param b second point
    388      * @param precision precision context used to compare floating point numbers
    389      * @return a new interval representing the region between the given points
    390      * @throws IllegalArgumentException if either point is {@link Vector1D#isNaN() NaN} or the points
    391      *      are both {@link Vector1D#isInfinite() infinite} and have the same sign
    392      */
    393     public static Interval of(final Vector1D a, final Vector1D b, final Precision.DoubleEquivalence precision) {
    394         return of(a.getX(), b.getX(), precision);
    395     }
    396
    397     /** Create a new interval from the given hyperplanes. The hyperplanes may be given in
    398      * any order but one must be positive-facing and the other negative-facing, with the positive-facing
    399      * hyperplane located above the negative-facing hyperplane. Either or both argument may be null,
    400      * in which case the returned interval will extend to infinity in the appropriate direction. If both
    401      * arguments are null, an interval representing the full space is returned.
    402      * @param a first hyperplane; may be null
    403      * @param b second hyperplane; may be null
    404      * @return a new interval representing the region between the given hyperplanes
    405      * @throws IllegalArgumentException if the hyperplanes have the same orientation or
    406      *      do not form an interval (for example, if the positive-facing hyperplane is below
    407      *      the negative-facing hyperplane)
    408      */
    409     public static Interval of(final OrientedPoint a, final OrientedPoint b) {
    410
    411         validateBoundaryRelationship(a, b);
    412
    413         final boolean hasA = a != null;
    414         final boolean hasB = b != null;
    415
    416         if (!hasA && !hasB) {
    417             // both boundaries null; return the full space
    418             return FULL;
    419         }
    420
    421         // determine the ordering of the hyperplanes; we know that at least one is non-null
    422         final OrientedPoint minBoundary = ((hasA && !a.isPositiveFacing()) || (hasB && b.isPositiveFacing())) ? a : b;
    423         final OrientedPoint maxBoundary = ((hasA && a.isPositiveFacing()) || (hasB && !b.isPositiveFacing())) ? a : b;
    424
    425         // validate the boundary locations; this will ensure that we don't have NaN values
    426         final double minLoc = (minBoundary != null) ? minBoundary.getLocation() : Double.NEGATIVE_INFINITY;
    427         final double maxLoc = (maxBoundary != null) ? maxBoundary.getLocation() : Double.POSITIVE_INFINITY;
    428
    429         validateIntervalValues(minLoc, maxLoc);
    430
    431         // create the interval, replacing infinites with nulls
    432         return new Interval(
    433                 Double.isFinite(minLoc) ? minBoundary : null,
    434                 Double.isFinite(maxLoc) ? maxBoundary : null);
    435     }
    436
    437     /** Return an interval with the given min value and no max.
    438      * @param min min value for the interval
    439      * @param precision precision context used to compare floating point numbers
    440      * @return an interval with the given min value and no max.
    441      */
    442     public static Interval min(final double min, final Precision.DoubleEquivalence precision) {
    443         return of(min, Double.POSITIVE_INFINITY, precision);
    444     }
    445
    446     /** Return an interval with the given max value and no min.
    447      * @param max max value for the interval
    448      * @param precision precision context used to compare floating point numbers
    449      * @return an interval with the given max value and no min.
    450      */
    451     public static Interval max(final double max, final Precision.DoubleEquivalence precision) {
    452         return of(Double.NEGATIVE_INFINITY, max, precision);
    453     }
    454
    455     /** Return an interval representing a single point at the given location.
    456      * @param location the location of the interval
    457      * @param precision precision context used to compare floating point numbers
    458      * @return an interval representing a single point
    459      */
    460     public static Interval point(final double location, final Precision.DoubleEquivalence precision) {
    461         return of(location, location, precision);
    462     }
    463
    464     /** Return an interval representing the entire real number line. The {@link #isFull()}
    465      * method of the instance will return true.
    466      * @return an interval representing the entire real number line
    467      * @see #isFull()
    468      */
    469     public static Interval full() {
    470         return FULL;
    471     }
    472
    473     /** Validate that the orientations and positions of the arguments may be used to create an interval.
    474      * The arguments may be given in any order. Does nothing if one or both arguments are null.
    475      * @param a first boundary; may be null
    476      * @param b second boundary may be null
    477      * @throws IllegalArgumentException is {@code a} and {@code b} have the same orientation or one does
    478      *      not lie on the plus side of the other.
    479      */
    480     private static void validateBoundaryRelationship(final OrientedPoint a, final OrientedPoint b) {
    481         if (a != null && b != null) {
    482             if (a.isPositiveFacing() == b.isPositiveFacing()) {
    483                 throw new IllegalArgumentException(
    484                         MessageFormat.format("Invalid interval: hyperplanes have same orientation: {0}, {1}", a, b));
    485             }
    486
    487             if (a.classify(b.getPoint()) == HyperplaneLocation.PLUS ||
    488                     b.classify(a.getPoint()) == HyperplaneLocation.PLUS) {
    489                 throw new IllegalArgumentException(
    490                         MessageFormat.format("Invalid interval: hyperplanes do not form interval: {0}, {1}", a, b));
    491             }
    492         }
    493     }
    494
    495     /** Validate that the given value can be used to construct an interval. The values
    496      * must not be NaN and if infinite, must have opposite signs.
    497      * @param a first value
    498      * @param b second value
    499      * @throws IllegalArgumentException if either value is NaN or if both values are infinite
    500      *      and have the same sign
    501      */
    502     private static void validateIntervalValues(final double a, final double b) {
    503         if (Double.isNaN(a) || Double.isNaN(b) ||
    504                 (Double.isInfinite(a) && Double.compare(a, b) == 0)) {
    505
    506             throw new IllegalArgumentException(
    507                     MessageFormat.format("Invalid interval values: [{0}, {1}]", a, b));
    508         }
    509     }
    510 }