src/com/google/common/geometry/S1Interval.java - platform/external/s2-geometry-library-java - Git at Google

 /*
  * Copyright 2005 Google Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package com.google.common.geometry;


 /**
  * 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].
  *
  */

 public final strictfp class S1Interval implements Cloneable {

   private final double lo;
   private final 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.
    */
   public S1Interval(double lo, double hi) {
     this(lo, hi, false);
   }

   /**
    * Copy constructor. Assumes that the given interval is valid.
    *
    * TODO(dbeaumont): Make this class immutable and remove this method.
    */
   public S1Interval(S1Interval interval) {
     this.lo = interval.lo;
     this.hi = interval.hi;
   }

   /**
    * Internal constructor that assumes that both arguments are in the correct
    * range, i.e. normalization from -Pi to Pi is already done.
    */
   private S1Interval(double lo, double hi, boolean checked) {
     double newLo = lo;
     double newHi = hi;
     if (!checked) {
       if (lo == -S2.M_PI && hi != S2.M_PI) {
         newLo = S2.M_PI;
       }
       if (hi == -S2.M_PI && lo != S2.M_PI) {
         newHi = S2.M_PI;
       }
     }
     this.lo = newLo;
     this.hi = newHi;
   }

   public static S1Interval empty() {
     return new S1Interval(S2.M_PI, -S2.M_PI, true);
   }

   public static S1Interval full() {
     return new S1Interval(-S2.M_PI, S2.M_PI, true);
   }

   /** Convenience method to construct an interval containing a single point. */
   public static S1Interval fromPoint(double p) {
     if (p == -S2.M_PI) {
       p = S2.M_PI;
     }
     return new S1Interval(p, p, true);
   }

   /**
    * 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.
    */
   public static S1Interval fromPointPair(double p1, double p2) {
     // assert (Math.abs(p1) <= S2.M_PI && Math.abs(p2) <= S2.M_PI);
     if (p1 == -S2.M_PI) {
       p1 = S2.M_PI;
     }
     if (p2 == -S2.M_PI) {
       p2 = S2.M_PI;
     }
     if (positiveDistance(p1, p2) <= S2.M_PI) {
       return new S1Interval(p1, p2, true);
     } else {
       return new S1Interval(p2, p1, true);
     }
   }

   public double lo() {
     return lo;
   }

   public double hi() {
     return hi;
   }

   /**
    * An interval is valid if neither bound exceeds Pi in absolute value, and the
    * value -Pi appears only in the Empty() and Full() intervals.
    */
   public boolean isValid() {
     return (Math.abs(lo()) <= S2.M_PI && Math.abs(hi()) <= S2.M_PI
         && !(lo() == -S2.M_PI && hi() != S2.M_PI) && !(hi() == -S2.M_PI && lo() != S2.M_PI));
   }

   /** Return true if the interval contains all points on the unit circle. */
   public boolean isFull() {
     return hi() - lo() == 2 * S2.M_PI;
   }


   /** Return true if the interval is empty, i.e. it contains no points. */
   public boolean isEmpty() {
     return lo() - hi() == 2 * S2.M_PI;
   }


   /* Return true if lo() > hi(). (This is true for empty intervals.) */
   public boolean isInverted() {
     return lo() > hi();
   }

   /**
    * Return the midpoint of the interval. For full and empty intervals, the
    * result is arbitrary.
    */
   public double getCenter() {
     double center = 0.5 * (lo() + hi());
     if (!isInverted()) {
       return center;
     }
     // Return the center in the range (-Pi, Pi].
     return (center <= 0) ? (center + S2.M_PI) : (center - S2.M_PI);
   }

   /**
    * Return the length of the interval. The length of an empty interval is
    * negative.
    */
   public double getLength() {
     double length = hi() - lo();
     if (length >= 0) {
       return length;
     }
     length += 2 * S2.M_PI;
     // Empty intervals have a negative length.
     return (length > 0) ? length : -1;
   }

   /**
    * 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.
    */
   public S1Interval complement() {
     if (lo() == hi()) {
       return full(); // Singleton.
     }
     return new S1Interval(hi(), lo(), true); // Handles
     // empty and
     // full.
   }

   /** Return true if the interval (which is closed) contains the point 'p'. */
   public boolean contains(double p) {
     // Works for empty, full, and singleton intervals.
     // assert (Math.abs(p) <= S2.M_PI);
     if (p == -S2.M_PI) {
       p = S2.M_PI;
     }
     return fastContains(p);
   }

   /**
    * Return true if the interval (which is closed) contains the point 'p'. Skips
    * the normalization of 'p' from -Pi to Pi.
    *
    */
   public boolean fastContains(double p) {
     if (isInverted()) {
       return (p >= lo() || p <= hi()) && !isEmpty();
     } else {
       return p >= lo() && p <= hi();
     }
   }

   /** Return true if the interior of the interval contains the point 'p'. */
   public boolean interiorContains(double p) {
     // Works for empty, full, and singleton intervals.
     // assert (Math.abs(p) <= S2.M_PI);
     if (p == -S2.M_PI) {
       p = S2.M_PI;
     }

     if (isInverted()) {
       return p > lo() || p < hi();
     } else {
       return (p > lo() && p < hi()) || isFull();
     }
   }

   /**
    * Return true if the interval contains the given interval 'y'. Works for
    * empty, full, and singleton intervals.
    */
   public boolean contains(final S1Interval y) {
     // It might be helpful to compare the structure of these tests to
     // the simpler Contains(double) method above.

     if (isInverted()) {
       if (y.isInverted()) {
         return y.lo() >= lo() && y.hi() <= hi();
       }
       return (y.lo() >= lo() || y.hi() <= hi()) && !isEmpty();
     } else {
       if (y.isInverted()) {
         return isFull() || y.isEmpty();
       }
       return y.lo() >= lo() && y.hi() <= hi();
     }
   }

   /**
    * 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).
    */
   public boolean interiorContains(final S1Interval y) {
     if (isInverted()) {
       if (!y.isInverted()) {
         return y.lo() > lo() || y.hi() < hi();
       }
       return (y.lo() > lo() && y.hi() < hi()) || y.isEmpty();
     } else {
       if (y.isInverted()) {
         return isFull() || y.isEmpty();
       }
       return (y.lo() > lo() && y.hi() < hi()) || isFull();
     }
   }

   /**
    * Return 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.
    */
   public boolean intersects(final S1Interval y) {
     if (isEmpty() || y.isEmpty()) {
       return false;
     }
     if (isInverted()) {
       // Every non-empty inverted interval contains Pi.
       return y.isInverted() || y.lo() <= hi() || y.hi() >= lo();
     } else {
       if (y.isInverted()) {
         return y.lo() <= hi() || y.hi() >= lo();
       }
       return y.lo() <= hi() && y.hi() >= lo();
     }
   }

   /**
    * Return true if the interior of this interval contains any point of the
    * interval 'y' (including its boundary). Works for empty, full, and singleton
    * intervals.
    */
   public boolean interiorIntersects(final S1Interval y) {
     if (isEmpty() || y.isEmpty() || lo() == hi()) {
       return false;
     }
     if (isInverted()) {
       return y.isInverted() || y.lo() < hi() || y.hi() > lo();
     } else {
       if (y.isInverted()) {
         return y.lo() < hi() || y.hi() > lo();
       }
       return (y.lo() < hi() && y.hi() > lo()) || isFull();
     }
   }

   /**
    * Expand the interval by the minimum amount necessary so that it contains the
    * given point "p" (an angle in the range [-Pi, Pi]).
    */
   public S1Interval addPoint(double p) {
     // assert (Math.abs(p) <= S2.M_PI);
     if (p == -S2.M_PI) {
       p = S2.M_PI;
     }

     if (fastContains(p)) {
       return new S1Interval(this);
     }

     if (isEmpty()) {
       return S1Interval.fromPoint(p);
     } else {
       // Compute distance from p to each endpoint.
       double dlo = positiveDistance(p, lo());
       double dhi = positiveDistance(hi(), p);
       if (dlo < dhi) {
         return new S1Interval(p, hi());
       } else {
         return new S1Interval(lo(), p);
       }
       // Adding a point can never turn a non-full interval into a full one.
     }
   }

   /**
    * Return an interval that contains all points within a distance "radius" of
    * a point in this interval. Note that the expansion of an empty interval is
    * always empty. The radius must be non-negative.
    */
   public S1Interval expanded(double radius) {
     // assert (radius >= 0);
     if (isEmpty()) {
       return this;
     }

     // Check whether this interval will be full after expansion, allowing
     // for a 1-bit rounding error when computing each endpoint.
     if (getLength() + 2 * radius >= 2 * S2.M_PI - 1e-15) {
       return full();
     }

     // NOTE(dbeaumont): Should this remainder be 2 * M_PI or just M_PI ??
     double lo = Math.IEEEremainder(lo() - radius, 2 * S2.M_PI);
     double hi = Math.IEEEremainder(hi() + radius, 2 * S2.M_PI);
     if (lo == -S2.M_PI) {
       lo = S2.M_PI;
     }
     return new S1Interval(lo, hi);
   }

   /**
    * Return the smallest interval that contains this interval and the given
    * interval "y".
    */
   public S1Interval union(final S1Interval y) {
     // The y.is_full() case is handled correctly in all cases by the code
     // below, but can follow three separate code paths depending on whether
     // this interval is inverted, is non-inverted but contains Pi, or neither.

     if (y.isEmpty()) {
       return this;
     }
     if (fastContains(y.lo())) {
       if (fastContains(y.hi())) {
         // Either this interval contains y, or the union of the two
         // intervals is the Full() interval.
         if (contains(y)) {
           return this; // is_full() code path
         }
         return full();
       }
       return new S1Interval(lo(), y.hi(), true);
     }
     if (fastContains(y.hi())) {
       return new S1Interval(y.lo(), hi(), true);
     }

     // This interval contains neither endpoint of y. This means that either y
     // contains all of this interval, or the two intervals are disjoint.
     if (isEmpty() || y.fastContains(lo())) {
       return y;
     }

     // Check which pair of endpoints are closer together.
     double dlo = positiveDistance(y.hi(), lo());
     double dhi = positiveDistance(hi(), y.lo());
     if (dlo < dhi) {
       return new S1Interval(y.lo(), hi(), true);
     } else {
       return new S1Interval(lo(), y.hi(), true);
     }
   }

   /**
    * Return the smallest interval that contains the intersection of this
    * interval with "y". Note that the region of intersection may consist of two
    * disjoint intervals.
    */
   public S1Interval intersection(final S1Interval y) {
     // The y.is_full() case is handled correctly in all cases by the code
     // below, but can follow three separate code paths depending on whether
     // this interval is inverted, is non-inverted but contains Pi, or neither.

     if (y.isEmpty()) {
       return empty();
     }
     if (fastContains(y.lo())) {
       if (fastContains(y.hi())) {
         // Either this interval contains y, or the region of intersection
         // consists of two disjoint subintervals. In either case, we want
         // to return the shorter of the two original intervals.
         if (y.getLength() < getLength()) {
           return y; // is_full() code path
         }
         return this;
       }
       return new S1Interval(y.lo(), hi(), true);
     }
     if (fastContains(y.hi())) {
       return new S1Interval(lo(), y.hi(), true);
     }

     // This interval contains neither endpoint of y. This means that either y
     // contains all of this interval, or the two intervals are disjoint.

     if (y.fastContains(lo())) {
       return this; // is_empty() okay here
     }
     // assert (!intersects(y));
     return empty();
   }

   /**
    * Return true if the length of the symmetric difference between the two
    * intervals is at most the given tolerance.
    */
   public boolean approxEquals(final S1Interval y, double maxError) {
     if (isEmpty()) {
       return y.getLength() <= maxError;
     }
     if (y.isEmpty()) {
       return getLength() <= maxError;
     }
     return (Math.abs(Math.IEEEremainder(y.lo() - lo(), 2 * S2.M_PI))
         + Math.abs(Math.IEEEremainder(y.hi() - hi(), 2 * S2.M_PI))) <= maxError;
   }

   public boolean approxEquals(final S1Interval y) {
     return approxEquals(y, 1e-9);
   }

   /**
    * Return true if two intervals contains the same set of points.
    */
   @Override
   public boolean equals(Object that) {
     if (that instanceof S1Interval) {
       S1Interval thatInterval = (S1Interval) that;
       return lo() == thatInterval.lo() && hi() == thatInterval.hi();
     }
     return false;
   }

   @Override
   public int hashCode() {
     long value = 17;
     value = 37 * value + Double.doubleToLongBits(lo());
     value = 37 * value + Double.doubleToLongBits(hi());
     return (int) ((value >>> 32) ^ value);
   }

   @Override
   public String toString() {
     return "[" + this.lo() + ", " + this.hi() + "]";
   }

   /**
    * Compute 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).
    */
   public static double positiveDistance(double a, double b) {
     double d = b - a;
     if (d >= 0) {
       return d;
     }
     // We want to ensure that if b == Pi and a == (-Pi + eps),
     // the return result is approximately 2*Pi and not zero.
     return (b + S2.M_PI) - (a - S2.M_PI);
   }
 }
	/*
	* Copyright 2005 Google Inc.
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package com.google.common.geometry;


	/**
	* 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].
	*
	*/

	public final strictfp class S1Interval implements Cloneable {

	private final double lo;
	private final 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.
	*/
	public S1Interval(double lo, double hi) {
	this(lo, hi, false);
	}

	/**
	* Copy constructor. Assumes that the given interval is valid.
	*
	* TODO(dbeaumont): Make this class immutable and remove this method.
	*/
	public S1Interval(S1Interval interval) {
	this.lo = interval.lo;
	this.hi = interval.hi;
	}

	/**
	* Internal constructor that assumes that both arguments are in the correct
	* range, i.e. normalization from -Pi to Pi is already done.
	*/
	private S1Interval(double lo, double hi, boolean checked) {
	double newLo = lo;
	double newHi = hi;
	if (!checked) {
	if (lo == -S2.M_PI && hi != S2.M_PI) {
	newLo = S2.M_PI;
	}
	if (hi == -S2.M_PI && lo != S2.M_PI) {
	newHi = S2.M_PI;
	}
	}
	this.lo = newLo;
	this.hi = newHi;
	}

	public static S1Interval empty() {
	return new S1Interval(S2.M_PI, -S2.M_PI, true);
	}

	public static S1Interval full() {
	return new S1Interval(-S2.M_PI, S2.M_PI, true);
	}

	/** Convenience method to construct an interval containing a single point. */
	public static S1Interval fromPoint(double p) {
	if (p == -S2.M_PI) {
	p = S2.M_PI;
	}
	return new S1Interval(p, p, true);
	}

	/**
	* 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.
	*/
	public static S1Interval fromPointPair(double p1, double p2) {
	// assert (Math.abs(p1) <= S2.M_PI && Math.abs(p2) <= S2.M_PI);
	if (p1 == -S2.M_PI) {
	p1 = S2.M_PI;
	}
	if (p2 == -S2.M_PI) {
	p2 = S2.M_PI;
	}
	if (positiveDistance(p1, p2) <= S2.M_PI) {
	return new S1Interval(p1, p2, true);
	} else {
	return new S1Interval(p2, p1, true);
	}
	}

	public double lo() {
	return lo;
	}

	public double hi() {
	return hi;
	}

	/**
	* An interval is valid if neither bound exceeds Pi in absolute value, and the
	* value -Pi appears only in the Empty() and Full() intervals.
	*/
	public boolean isValid() {
	return (Math.abs(lo()) <= S2.M_PI && Math.abs(hi()) <= S2.M_PI
	&& !(lo() == -S2.M_PI && hi() != S2.M_PI) && !(hi() == -S2.M_PI && lo() != S2.M_PI));
	}

	/** Return true if the interval contains all points on the unit circle. */
	public boolean isFull() {
	return hi() - lo() == 2 * S2.M_PI;
	}


	/** Return true if the interval is empty, i.e. it contains no points. */
	public boolean isEmpty() {
	return lo() - hi() == 2 * S2.M_PI;
	}


	/* Return true if lo() > hi(). (This is true for empty intervals.) */
	public boolean isInverted() {
	return lo() > hi();
	}

	/**
	* Return the midpoint of the interval. For full and empty intervals, the
	* result is arbitrary.
	*/
	public double getCenter() {
	double center = 0.5 * (lo() + hi());
	if (!isInverted()) {
	return center;
	}
	// Return the center in the range (-Pi, Pi].
	return (center <= 0) ? (center + S2.M_PI) : (center - S2.M_PI);
	}

	/**
	* Return the length of the interval. The length of an empty interval is
	* negative.
	*/
	public double getLength() {
	double length = hi() - lo();
	if (length >= 0) {
	return length;
	}
	length += 2 * S2.M_PI;
	// Empty intervals have a negative length.
	return (length > 0) ? length : -1;
	}

	/**
	* 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.
	*/
	public S1Interval complement() {
	if (lo() == hi()) {
	return full(); // Singleton.
	}
	return new S1Interval(hi(), lo(), true); // Handles
	// empty and
	// full.
	}

	/** Return true if the interval (which is closed) contains the point 'p'. */
	public boolean contains(double p) {
	// Works for empty, full, and singleton intervals.
	// assert (Math.abs(p) <= S2.M_PI);
	if (p == -S2.M_PI) {
	p = S2.M_PI;
	}
	return fastContains(p);
	}

	/**
	* Return true if the interval (which is closed) contains the point 'p'. Skips
	* the normalization of 'p' from -Pi to Pi.
	*
	*/
	public boolean fastContains(double p) {
	if (isInverted()) {
	return (p >= lo() \|\| p <= hi()) && !isEmpty();
	} else {
	return p >= lo() && p <= hi();
	}
	}

	/** Return true if the interior of the interval contains the point 'p'. */
	public boolean interiorContains(double p) {
	// Works for empty, full, and singleton intervals.
	// assert (Math.abs(p) <= S2.M_PI);
	if (p == -S2.M_PI) {
	p = S2.M_PI;
	}

	if (isInverted()) {
	return p > lo() \|\| p < hi();
	} else {
	return (p > lo() && p < hi()) \|\| isFull();
	}
	}

	/**
	* Return true if the interval contains the given interval 'y'. Works for
	* empty, full, and singleton intervals.
	*/
	public boolean contains(final S1Interval y) {
	// It might be helpful to compare the structure of these tests to
	// the simpler Contains(double) method above.

	if (isInverted()) {
	if (y.isInverted()) {
	return y.lo() >= lo() && y.hi() <= hi();
	}
	return (y.lo() >= lo() \|\| y.hi() <= hi()) && !isEmpty();
	} else {
	if (y.isInverted()) {
	return isFull() \|\| y.isEmpty();
	}
	return y.lo() >= lo() && y.hi() <= hi();
	}
	}

	/**
	* 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).
	*/
	public boolean interiorContains(final S1Interval y) {
	if (isInverted()) {
	if (!y.isInverted()) {
	return y.lo() > lo() \|\| y.hi() < hi();
	}
	return (y.lo() > lo() && y.hi() < hi()) \|\| y.isEmpty();
	} else {
	if (y.isInverted()) {
	return isFull() \|\| y.isEmpty();
	}
	return (y.lo() > lo() && y.hi() < hi()) \|\| isFull();
	}
	}

	/**
	* Return 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.
	*/
	public boolean intersects(final S1Interval y) {
	if (isEmpty() \|\| y.isEmpty()) {
	return false;
	}
	if (isInverted()) {
	// Every non-empty inverted interval contains Pi.
	return y.isInverted() \|\| y.lo() <= hi() \|\| y.hi() >= lo();
	} else {
	if (y.isInverted()) {
	return y.lo() <= hi() \|\| y.hi() >= lo();
	}
	return y.lo() <= hi() && y.hi() >= lo();
	}
	}

	/**
	* Return true if the interior of this interval contains any point of the
	* interval 'y' (including its boundary). Works for empty, full, and singleton
	* intervals.
	*/
	public boolean interiorIntersects(final S1Interval y) {
	if (isEmpty() \|\| y.isEmpty() \|\| lo() == hi()) {
	return false;
	}
	if (isInverted()) {
	return y.isInverted() \|\| y.lo() < hi() \|\| y.hi() > lo();
	} else {
	if (y.isInverted()) {
	return y.lo() < hi() \|\| y.hi() > lo();
	}
	return (y.lo() < hi() && y.hi() > lo()) \|\| isFull();
	}
	}

	/**
	* Expand the interval by the minimum amount necessary so that it contains the
	* given point "p" (an angle in the range [-Pi, Pi]).
	*/
	public S1Interval addPoint(double p) {
	// assert (Math.abs(p) <= S2.M_PI);
	if (p == -S2.M_PI) {
	p = S2.M_PI;
	}

	if (fastContains(p)) {
	return new S1Interval(this);
	}

	if (isEmpty()) {
	return S1Interval.fromPoint(p);
	} else {
	// Compute distance from p to each endpoint.
	double dlo = positiveDistance(p, lo());
	double dhi = positiveDistance(hi(), p);
	if (dlo < dhi) {
	return new S1Interval(p, hi());
	} else {
	return new S1Interval(lo(), p);
	}
	// Adding a point can never turn a non-full interval into a full one.
	}
	}

	/**
	* Return an interval that contains all points within a distance "radius" of
	* a point in this interval. Note that the expansion of an empty interval is
	* always empty. The radius must be non-negative.
	*/
	public S1Interval expanded(double radius) {
	// assert (radius >= 0);
	if (isEmpty()) {
	return this;
	}

	// Check whether this interval will be full after expansion, allowing
	// for a 1-bit rounding error when computing each endpoint.
	if (getLength() + 2 * radius >= 2 * S2.M_PI - 1e-15) {
	return full();
	}

	// NOTE(dbeaumont): Should this remainder be 2 * M_PI or just M_PI ??
	double lo = Math.IEEEremainder(lo() - radius, 2 * S2.M_PI);
	double hi = Math.IEEEremainder(hi() + radius, 2 * S2.M_PI);
	if (lo == -S2.M_PI) {
	lo = S2.M_PI;
	}
	return new S1Interval(lo, hi);
	}

	/**
	* Return the smallest interval that contains this interval and the given
	* interval "y".
	*/
	public S1Interval union(final S1Interval y) {
	// The y.is_full() case is handled correctly in all cases by the code
	// below, but can follow three separate code paths depending on whether
	// this interval is inverted, is non-inverted but contains Pi, or neither.

	if (y.isEmpty()) {
	return this;
	}
	if (fastContains(y.lo())) {
	if (fastContains(y.hi())) {
	// Either this interval contains y, or the union of the two
	// intervals is the Full() interval.
	if (contains(y)) {
	return this; // is_full() code path
	}
	return full();
	}
	return new S1Interval(lo(), y.hi(), true);
	}
	if (fastContains(y.hi())) {
	return new S1Interval(y.lo(), hi(), true);
	}

	// This interval contains neither endpoint of y. This means that either y
	// contains all of this interval, or the two intervals are disjoint.
	if (isEmpty() \|\| y.fastContains(lo())) {
	return y;
	}

	// Check which pair of endpoints are closer together.
	double dlo = positiveDistance(y.hi(), lo());
	double dhi = positiveDistance(hi(), y.lo());
	if (dlo < dhi) {
	return new S1Interval(y.lo(), hi(), true);
	} else {
	return new S1Interval(lo(), y.hi(), true);
	}
	}

	/**
	* Return the smallest interval that contains the intersection of this
	* interval with "y". Note that the region of intersection may consist of two
	* disjoint intervals.
	*/
	public S1Interval intersection(final S1Interval y) {
	// The y.is_full() case is handled correctly in all cases by the code
	// below, but can follow three separate code paths depending on whether
	// this interval is inverted, is non-inverted but contains Pi, or neither.

	if (y.isEmpty()) {
	return empty();
	}
	if (fastContains(y.lo())) {
	if (fastContains(y.hi())) {
	// Either this interval contains y, or the region of intersection
	// consists of two disjoint subintervals. In either case, we want
	// to return the shorter of the two original intervals.
	if (y.getLength() < getLength()) {
	return y; // is_full() code path
	}
	return this;
	}
	return new S1Interval(y.lo(), hi(), true);
	}
	if (fastContains(y.hi())) {
	return new S1Interval(lo(), y.hi(), true);
	}

	// This interval contains neither endpoint of y. This means that either y
	// contains all of this interval, or the two intervals are disjoint.

	if (y.fastContains(lo())) {
	return this; // is_empty() okay here
	}
	// assert (!intersects(y));
	return empty();
	}

	/**
	* Return true if the length of the symmetric difference between the two
	* intervals is at most the given tolerance.
	*/
	public boolean approxEquals(final S1Interval y, double maxError) {
	if (isEmpty()) {
	return y.getLength() <= maxError;
	}
	if (y.isEmpty()) {
	return getLength() <= maxError;
	}
	return (Math.abs(Math.IEEEremainder(y.lo() - lo(), 2 * S2.M_PI))
	+ Math.abs(Math.IEEEremainder(y.hi() - hi(), 2 * S2.M_PI))) <= maxError;
	}

	public boolean approxEquals(final S1Interval y) {
	return approxEquals(y, 1e-9);
	}

	/**
	* Return true if two intervals contains the same set of points.
	*/
	@Override
	public boolean equals(Object that) {
	if (that instanceof S1Interval) {
	S1Interval thatInterval = (S1Interval) that;
	return lo() == thatInterval.lo() && hi() == thatInterval.hi();
	}
	return false;
	}

	@Override
	public int hashCode() {
	long value = 17;
	value = 37 * value + Double.doubleToLongBits(lo());
	value = 37 * value + Double.doubleToLongBits(hi());
	return (int) ((value >>> 32) ^ value);
	}

	@Override
	public String toString() {
	return "[" + this.lo() + ", " + this.hi() + "]";
	}

	/**
	* Compute 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).
	*/
	public static double positiveDistance(double a, double b) {
	double d = b - a;
	if (d >= 0) {
	return d;
	}
	// We want to ensure that if b == Pi and a == (-Pi + eps),
	// the return result is approximately 2*Pi and not zero.
	return (b + S2.M_PI) - (a - S2.M_PI);
	}
	}