Class S1Interval

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable

    @GwtCompatible(serializable=true)
    public final class S1Interval
    extends java.lang.Object
    implements java.lang.Cloneable, java.io.Serializable
    An S1Interval represents a closed interval on a unit circle (also known as a 1-dimensional sphere). It is capable of representing the empty interval (containing no points), the full interval (containing all points), and zero-length intervals (containing a single point).

    Points are represented by the angle they make with the positive x-axis in the range [-Pi, Pi]. An interval is represented by its lower and upper bounds (both inclusive, since the interval is closed). The lower bound may be greater than the upper bound, in which case the interval is "inverted" (i.e. it passes through the point (-1, 0)).

    Note that the point (-1, 0) has two valid representations, Pi and -Pi. The normalized representation of this point internally is Pi, so that endpoints of normal intervals are in the range (-Pi, Pi]. However, we take advantage of the point -Pi to construct two special intervals: the full() interval is [-Pi, Pi], and the Empty() interval is [Pi, -Pi].

    See Also:
    Serialized Form
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private double hi  
      private double lo  
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
        S1Interval()  
        S1Interval​(double lo, double hi)
      Both endpoints must be in the range -Pi to Pi inclusive.
      private S1Interval​(double lo, double hi, boolean checked)
      Internal constructor that just passes the arguments down to set(double, double, boolean).
        S1Interval​(S1Interval interval)
      Copy constructor.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      S1Interval addPoint​(double p)
      Expands the interval by the minimum amount necessary so that it contains the point p (an angle in the range [-Pi, Pi]).
      boolean approxEquals​(S1Interval y)
      As approxEquals(S1Interval, double), with a default maxError of 1e-15.
      boolean approxEquals​(S1Interval y, double maxError)
      Returns true if this interval can be transformed into the interval y by moving each endpoint by at most "maxError" (and without the endpoints crossing, which would invert the interval).
      double clampPoint​(double p)
      Returns the closest point in the interval to the point p.
      S1Interval complement()
      Return the complement of the interior of the interval.
      boolean contains​(double p)
      Returns true if the interval (which is closed) contains the point 'p'.
      boolean contains​(S1Interval y)
      Returns true if the interval contains the interval y.
      static S1Interval empty()  
      boolean equals​(java.lang.Object that)
      Returns true if two intervals contains the same set of points.
      S1Interval expanded​(double margin)
      Returns a new interval that has been expanded on each side by the distance margin.
      (package private) void expandedInternal​(double margin)
      Expands this interval on each side by the distance margin.
      boolean fastContains​(double p)
      Returns true if the interval (which is closed) contains the point 'p'.
      static S1Interval fromPoint​(double radians)
      Convenience method to construct an interval containing a single point.
      static S1Interval fromPointPair​(double p1, double p2)
      Convenience method to construct the minimal interval containing the two given points.
      static S1Interval full()  
      double get​(int endpoint)
      Returns the value of the given endpoint in this interval, which must be 0 for the low end, or 1 for the high end.
      double getCenter()
      Returns the midpoint of the interval.
      double getComplementCenter()
      Return the midpoint of the complement of the interval.
      double getDirectedHausdorffDistance​(S1Interval y)
      Return the Hausdorff distance to the given interval y.
      double getLength()
      Returns the length of the interval.
      int hashCode()  
      double hi()  
      (package private) void initFromPointPair​(double p1, double p2)  
      boolean interiorContains​(double p)
      Returns true if the interior of the interval contains the point 'p'.
      boolean interiorContains​(S1Interval y)
      Returns true if the interior of this interval contains the entire interval 'y'.
      boolean interiorIntersects​(S1Interval y)
      Returns true if the interior of this interval contains any point of the interval y (including its boundary).
      S1Interval intersection​(S1Interval y)
      Returns the smallest interval that contains the intersection of this interval with y.
      (package private) void intersectionInternal​(S1Interval y)
      Sets this interval to the intersection of the current interval and y.
      boolean intersects​(S1Interval y)
      Returns true if the two intervals contain any points in common.
      boolean isEmpty()
      Returns true if the interval is empty, i.e.
      boolean isFull()
      Returns true if the interval contains all points on the unit circle.
      boolean isInverted()
      Returns true if lo() > hi().
      boolean isValid()
      An interval is valid if neither bound exceeds Pi in absolute value, and the value -Pi appears only in the Empty() and full() intervals.
      double lo()  
      static double positiveDistance​(double a, double b)
      Computes the distance from a to b in the range [0, 2*Pi).
      (package private) void set​(double newLo, double newHi, boolean checked)
      Assigns the range of this interval, assuming both arguments are in the correct range, i.e.
      (package private) void setEmpty()
      Sets the range of this interval to the empty interval.
      (package private) void setFull()
      Sets the range of this interval to the full interval.
      java.lang.String toString()  
      S1Interval union​(S1Interval y)
      Returns the smallest interval that contains this interval and the interval y.
      (package private) void unionInternal​(S1Interval y)
      Sets this interval to the union of the current interval and y.
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait
    • Field Detail

      • lo

        private double lo
      • hi

        private double hi
    • Constructor Detail

      • S1Interval

        public S1Interval()
      • S1Interval

        public S1Interval​(double lo,
                          double hi)
        Both endpoints must be in the range -Pi to Pi inclusive. The value -Pi is converted internally to Pi except for the full() and empty() intervals.
      • S1Interval

        public S1Interval​(S1Interval interval)
        Copy constructor. Assumes that the interval is valid.
      • S1Interval

        private S1Interval​(double lo,
                           double hi,
                           boolean checked)
        Internal constructor that just passes the arguments down to set(double, double, boolean).
    • Method Detail

      • set

        void set​(double newLo,
                 double newHi,
                 boolean checked)
        Assigns the range of this interval, assuming both arguments are in the correct range, i.e. normalization from -Pi to Pi is already done. If checked is false, endpoints at -Pi will be moved to +Pi unless the other endpoint is already there.

        Note that because S1Interval has invariants to maintain after each update, values cannot be set singly, both endpoints must be set together.

      • setEmpty

        void setEmpty()
        Sets the range of this interval to the empty interval.

        Package private since only S2 code needs to mutate S1Intervals for now.

      • setFull

        void setFull()
        Sets the range of this interval to the full interval.

        Package private since only S2 code needs to mutate S1Intervals for now.

      • fromPoint

        public static S1Interval fromPoint​(double radians)
        Convenience method to construct an interval containing a single point.
      • fromPointPair

        public static S1Interval fromPointPair​(double p1,
                                               double p2)
        Convenience method to construct the minimal interval containing the two given points. This is equivalent to starting with an empty interval and calling addPoint() twice, but it is more efficient.
      • initFromPointPair

        void initFromPointPair​(double p1,
                               double p2)
      • lo

        public double lo()
      • hi

        public double hi()
      • isValid

        public boolean isValid()
        An interval is valid if neither bound exceeds Pi in absolute value, and the value -Pi appears only in the Empty() and full() intervals.
      • isFull

        public boolean isFull()
        Returns true if the interval contains all points on the unit circle.
      • isEmpty

        public boolean isEmpty()
        Returns true if the interval is empty, i.e. it contains no points.
      • isInverted

        public boolean isInverted()
        Returns true if lo() > hi(). (This is true for empty intervals.)
      • getCenter

        public double getCenter()
        Returns the midpoint of the interval. For full and empty intervals, the result is arbitrary.
      • getLength

        public double getLength()
        Returns the length of the interval. The length of an empty interval is negative.
      • complement

        public S1Interval complement()
        Return the complement of the interior of the interval. An interval and its complement have the same boundary but do not share any interior values. The complement operator is not a bijection, since the complement of a singleton interval (containing a single value) is the same as the complement of an empty interval.
      • getComplementCenter

        public double getComplementCenter()
        Return the midpoint of the complement of the interval. For full and empty intervals, the result is arbitrary. For a singleton interval (containing a single point), the result is its antipodal point on S1.
      • contains

        public boolean contains​(double p)
        Returns true if the interval (which is closed) contains the point 'p'.
      • fastContains

        public boolean fastContains​(double p)
        Returns true if the interval (which is closed) contains the point 'p'. Skips the normalization of 'p' from -Pi to Pi.
      • interiorContains

        public boolean interiorContains​(double p)
        Returns true if the interior of the interval contains the point 'p'.
      • contains

        public boolean contains​(S1Interval y)
        Returns true if the interval contains the interval y. Works for empty, full, and singleton intervals.
      • interiorContains

        public boolean interiorContains​(S1Interval y)
        Returns true if the interior of this interval contains the entire interval 'y'. Note that x.interiorContains(x) is true only when x is the empty or full interval, and x.interiorContains(S1Interval(p,p)) is equivalent to x.InteriorContains(p).
      • intersects

        public boolean intersects​(S1Interval y)
        Returns true if the two intervals contain any points in common. Note that the point +/-Pi has two representations, so the intervals [-Pi,-3] and [2,Pi] intersect, for example.
      • interiorIntersects

        public boolean interiorIntersects​(S1Interval y)
        Returns true if the interior of this interval contains any point of the interval y (including its boundary). Works for empty, full, and singleton intervals.
      • getDirectedHausdorffDistance

        public double getDirectedHausdorffDistance​(S1Interval y)
        Return the Hausdorff distance to the given interval y. For two S1Intervals x and y, this distance is defined by h(x, y) = max_{p in x} min_{q in y} d(p, q), where d(.,.) is measured along S1.
      • addPoint

        @CheckReturnValue
        public S1Interval addPoint​(double p)
        Expands the interval by the minimum amount necessary so that it contains the point p (an angle in the range [-Pi, Pi]).
      • clampPoint

        public double clampPoint​(double p)
        Returns the closest point in the interval to the point p. The interval must be non-empty.
      • expanded

        @CheckReturnValue
        public S1Interval expanded​(double margin)
        Returns a new interval that has been expanded on each side by the distance margin. If "margin" is negative, then shrink the interval on each side by "margin" instead. The resulting interval may be empty or full. Any expansion (positive or negative) of a full interval remains full, and any expansion of an empty interval remains empty.
      • expandedInternal

        void expandedInternal​(double margin)
        Expands this interval on each side by the distance margin. If "margin" is negative, then shrink the interval on each side by "margin" instead. The resulting interval may be empty or full. Any expansion (positive or negative) of a full interval remains full, and any expansion of an empty interval remains empty.

        Package private since only S2 code should be mutating S1Intervals for now.

      • union

        @CheckReturnValue
        public S1Interval union​(S1Interval y)
        Returns the smallest interval that contains this interval and the interval y.
      • unionInternal

        void unionInternal​(S1Interval y)
        Sets this interval to the union of the current interval and y.

        Package private since only S2 classes are intended to mutate S1Intervals for now.

      • get

        public double get​(int endpoint)
        Returns the value of the given endpoint in this interval, which must be 0 for the low end, or 1 for the high end.
      • intersection

        @CheckReturnValue
        public S1Interval intersection​(S1Interval y)
        Returns the smallest interval that contains the intersection of this interval with y. Note that the region of intersection may consist of two disjoint intervals.
      • intersectionInternal

        void intersectionInternal​(S1Interval y)
        Sets this interval to the intersection of the current interval and y.

        Package private since only S2 classes are intended to mutate S1Intervals for now.

      • approxEquals

        public boolean approxEquals​(S1Interval y,
                                    double maxError)
        Returns true if this interval can be transformed into the interval y by moving each endpoint by at most "maxError" (and without the endpoints crossing, which would invert the interval). Empty and full intervals are considered to start at an arbitrary point on the unit circle, thus any interval with (length <= 2*maxError) matches the empty interval, and any interval with (length >= 2*Pi - 2*maxError) matches the full interval.
      • equals

        public boolean equals​(java.lang.Object that)
        Returns true if two intervals contains the same set of points.
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • positiveDistance

        public static double positiveDistance​(double a,
                                              double b)
        Computes the distance from a to b in the range [0, 2*Pi). This is equivalent to drem(b - a - S2.M_PI, 2 * S2.M_PI) + S2.M_PI, except that it is more numerically stable (it does not lose precision for very small positive distances).