text: // Copyright 2005 Google Inc. All Rights Reserved.
  
  #ifndef UTIL_GEOMETRY_S2LATLNGRECT_H_
  #define UTIL_GEOMETRY_S2LATLNGRECT_H_
  
  #include <iostream>
  using std::ostream;
  using std::endl;
  
  
  #include "base/basictypes.h"
  #include "base/logging.h"
  #include "s1angle.h"
  #include "r1interval.h"
  #include "s1interval.h"
  #include "s2region.h"
  #include "s2latlng.h"
  
  // An S2LatLngRect represents a closed latitude-longitude rectangle.  It is
  // capable of representing the empty and full rectangles as well as
  // single points.
  //
  // This class is intended to be copied by value as desired.  It uses
  // the default copy constructor and assignment operator, however it is
  // not a "plain old datatype" (POD) because it has virtual functions.
  class S2LatLngRect : public S2Region {
   public:
    // Construct a rectangle from minimum and maximum latitudes and longitudes.
    // If lo.lng() > hi.lng(), the rectangle spans the 180 degree longitude
    // line. Both points must be normalized, with lo.lat() <= hi.lat().
    // The rectangle contains all the points p such that 'lo' <= p <= 'hi',
    // where '<=' is defined in the obvious way.
    inline S2LatLngRect(S2LatLng const& lo, S2LatLng const& hi);
  
    // Construct a rectangle from latitude and longitude intervals.  The two
    // intervals must either be both empty or both non-empty, and the latitude
    // interval must not extend outside [-90, +90] degrees.
    // Note that both intervals (and hence the rectangle) are closed.
    inline S2LatLngRect(R1Interval const& lat, S1Interval const& lng);
  
    // The default constructor creates an empty S2LatLngRect.
    inline S2LatLngRect();
  
    // Construct a rectangle of the given size centered around the given point.
    // "center" needs to be normalized, but "size" does not.  The latitude
    // interval of the result is clamped to [-90,90] degrees, and the longitude
    // interval of the result is Full() if and only if the longitude size is
    // 360 degrees or more.  Examples of clamping (in degrees):
    //
    //   center=(80,170),  size=(40,60)   -> lat=[60,90],   lng=[140,-160]
    //   center=(10,40),   size=(210,400) -> lat=[-90,90],  lng=[-180,180]
    //   center=(-90,180), size=(20,50)   -> lat=[-90,-80], lng=[155,-155]
    static S2LatLngRect FromCenterSize(S2LatLng const& center,
                                       S2LatLng const& size);
  
    // Construct a rectangle containing a single (normalized) point.
    static S2LatLngRect FromPoint(S2LatLng const& p);
  
    // Construct the minimal bounding rectangle containing the two given
    // normalized points.  This is equivalent to starting with an empty
    // rectangle and calling AddPoint() twice.  Note that it is different than
    // the S2LatLngRect(lo, hi) constructor, where the first point is always
    // used as the lower-left corner of the resulting rectangle.
    static S2LatLngRect FromPointPair(S2LatLng const& p1, S2LatLng const& p2);
  
    // Accessor methods.
    S1Angle lat_lo() const { return S1Angle::Radians(lat_.lo()); }
    S1Angle lat_hi() const { return S1Angle::Radians(lat_.hi()); }
    S1Angle lng_lo() const { return S1Angle::Radians(lng_.lo()); }
    S1Angle lng_hi() const { return S1Angle::Radians(lng_.hi()); }
    R1Interval const& lat() const { return lat_; }
    S1Interval const& lng() const { return lng_; }
    R1Interval *mutable_lat() { return &lat_; }
    S1Interval *mutable_lng() { return &lng_; }
    S2LatLng lo() const { return S2LatLng(lat_lo(), lng_lo()); }
    S2LatLng hi() const { return S2LatLng(lat_hi(), lng_hi()); }
  
    // The canonical empty and full rectangles.
    static inline S2LatLngRect Empty();
    static inline S2LatLngRect Full();
  
    // The full allowable range of latitudes and longitudes.
    static R1Interval FullLat() { return R1Interval(-M_PI_2, M_PI_2); }
    static S1Interval FullLng() { return S1Interval::Full(); }
  
    // Return true if the rectangle is valid, which essentially just means
    // that the latitude bounds do not exceed Pi/2 in absolute value and
    // the longitude bounds do not exceed Pi in absolute value.  Also, if
    // either the latitude or longitude bound is empty then both must be.
    inline bool is_valid() const;
  
    // Return true if the rectangle is empty, i.e. it contains no points at all.
    inline bool is_empty() const;
  
    // Return true if the rectangle is full, i.e. it contains all points.
    inline bool is_full() const;
  
    // Return true if the rectangle is a point, i.e. lo() == hi()
    inline bool is_point() const;
  
    // Return true if lng_.lo() > lng_.hi(), i.e. the rectangle crosses
    // the 180 degree longitude line.
    bool is_inverted() const { return lng_.is_inverted(); }
  
    // Return the k-th vertex of the rectangle (k = 0,1,2,3) in CCW order.
    S2LatLng GetVertex(int k) const;
  
    // Return the center of the rectangle in latitude-longitude space
    // (in general this is not the center of the region on the sphere).
    S2LatLng GetCenter() const;
  
    // Return the width and height of this rectangle in latitude-longitude
    // space.  Empty rectangles have a negative width and height.
    S2LatLng GetSize() const;
  
    // Returns the surface area of this rectangle on the unit sphere.
    double Area() const;
  
    // More efficient version of Contains() that accepts a S2LatLng rather than
    // an S2Point.  The argument must be normalized.
    bool Contains(S2LatLng const& ll) const;
  
    // Return true if and only if the given point is contained in the interior
    // of the region (i.e. the region excluding its boundary).  The point 'p'
    // does not need to be normalized.
    bool InteriorContains(S2Point const& p) const;
  
    // More efficient version of InteriorContains() that accepts a S2LatLng
    // rather than an S2Point.  The argument must be normalized.
    bool InteriorContains(S2LatLng const& ll) const;
  
    // Return true if and only if the rectangle contains the given other
    // rectangle.
    bool Contains(S2LatLngRect const& other) const;
  
    // Return true if and only if the interior of this rectangle contains all
    // points of the given other rectangle (including its boundary).
    bool InteriorContains(S2LatLngRect const& other) const;
  
    // Return true if this rectangle and the given other rectangle have any
    // points in common.
    bool Intersects(S2LatLngRect const& other) const;
  
    // Returns true if this rectangle intersects the given cell.  (This is an
    // exact test and may be fairly expensive, see also MayIntersect below.)
    bool Intersects(S2Cell const& cell) const;
  
    // Return true if and only if the interior of this rectangle intersects
    // any point (including the boundary) of the given other rectangle.
    bool InteriorIntersects(S2LatLngRect const& other) const;
  
    // Increase the size of the bounding rectangle to include the given point.
    // The rectangle is expanded by the minimum amount possible.  The S2LatLng
    // argument must be normalized.
    void AddPoint(S2Point const& p);
    void AddPoint(S2LatLng const& ll);
  
    // Return a rectangle that contains all points whose latitude distance from
    // this rectangle is at most margin.lat(), and whose longitude distance
    // from this rectangle is at most margin.lng().  In particular, latitudes
    // are clamped while longitudes are wrapped.  Note that any expansion of an
    // empty interval remains empty, and both components of the given margin
    // must be non-negative.  "margin" does not need to be normalized.
    //
    // NOTE: If you are trying to grow a rectangle by a certain *distance* on
    // the sphere (e.g. 5km), use the ConvolveWithCap() method instead.
    S2LatLngRect Expanded(S2LatLng const& margin) const;
  
    // Return the smallest rectangle containing the union of this rectangle and
    // the given rectangle.
    S2LatLngRect Union(S2LatLngRect const& other) const;
  
    // Return the smallest rectangle containing the intersection of this
    // rectangle and the given rectangle.  Note that the region of intersection
    // may consist of two disjoint rectangles, in which case a single rectangle
    // spanning both of them is returned.
    S2LatLngRect Intersection(S2LatLngRect const& other) const;
  
    // Return a rectangle that contains the convolution of this rectangle with a
    // cap of the given angle.  This expands the rectangle by a fixed distance
    // (as opposed to growing the rectangle in latitude-longitude space).  The
    // returned rectangle includes all points whose minimum distance to the
    // original rectangle is at most the given angle.
    S2LatLngRect ConvolveWithCap(S1Angle const& angle) const;
  
    // Returns the minimum distance (measured along the surface of the sphere) to
    // the given S2LatLngRect. Both S2LatLngRects must be non-empty.
    S1Angle GetDistance(S2LatLngRect const& other) const;
  
    // Returns the minimum distance (measured along the surface of the sphere)
    // from a given point to the rectangle (both its boundary and its interior).
    // The latlng must be valid.
    S1Angle GetDistance(S2LatLng const& p) const;
  
    // Returns the (directed or undirected) Hausdorff distance (measured along the
    // surface of the sphere) to the given S2LatLngRect. The directed Hausdorff
    // distance from rectangle A to rectangle B is given by
    //     h(A, B) = max_{p in A} min_{q in B} d(p, q).
    // The Hausdorff distance between rectangle A and rectangle B is given by
    //     H(A, B) = max{h(A, B), h(B, A)}.
    S1Angle GetDirectedHausdorffDistance(S2LatLngRect const& other) const;
    S1Angle GetHausdorffDistance(S2LatLngRect const& other) const;
  
    // Return true if two rectangles contains the same set of points.
    inline bool operator==(S2LatLngRect const& other) const;
  
    // Return the opposite of what operator == returns.
    inline bool operator!=(S2LatLngRect const& other) const;
  
    // Return true if the latitude and longitude intervals of the two rectangles
    // are the same up to the given tolerance (see r1interval.h and s1interval.h
    // for details).
    bool ApproxEquals(S2LatLngRect const& other, double max_error = 1e-15) const;
  
    ////////////////////////////////////////////////////////////////////////
    // S2Region interface (see s2region.h for details):
  
    virtual S2LatLngRect* Clone() const;
    virtual S2Cap GetCapBound() const;
    virtual S2LatLngRect GetRectBound() const;
    virtual bool Contains(S2Cell const& cell) const;
    virtual bool VirtualContainsPoint(S2Point const& p) const {
      return Contains(p);  // The same as Contains() below, just virtual.
    }
  
    // This test is cheap but is NOT exact.  Use Intersects() if you want a more
    // accurate and more expensive test.  Note that when this method is used by
    // an S2RegionCoverer, the accuracy isn't all that important since if a cell
    // may intersect the region then it is subdivided, and the accuracy of this
    // method goes up as the cells get smaller.
    virtual bool MayIntersect(S2Cell const& cell) const;
  
    // The point 'p' does not need to be normalized.
    bool Contains(S2Point const& p) const;
  
    virtual void Encode(Encoder* const encoder) const;
    virtual bool Decode(Decoder* const decoder);
  
   private:
    // Return true if the edge AB intersects the given edge of constant
    // longitude.
    static bool IntersectsLngEdge(S2Point const& a, S2Point const& b,
                                  R1Interval const& lat, double lng);
  
    // Return true if the edge AB intersects the given edge of constant
    // latitude.
    static bool IntersectsLatEdge(S2Point const& a, S2Point const& b,
                                  double lat, S1Interval const& lng);
  
    // Helper function. See .cc for description.
    static S1Angle GetDirectedHausdorffDistance(double lng_diff,
                                                R1Interval const& a_lat,
                                                R1Interval const& b_lat);
  
    // Helper function. See .cc for description.
    static S1Angle GetInteriorMaxDistance(R1Interval const& a_lat,
                                          S2Point const& b);
  
    // Helper function. See .cc for description.
    static S2Point GetBisectorIntersection(R1Interval const& lat, double lng);
  
    R1Interval lat_;
    S1Interval lng_;
  };
  
  inline S2LatLngRect::S2LatLngRect(S2LatLng const& lo, S2LatLng const& hi)
    : lat_(lo.lat().radians(), hi.lat().radians()),
      lng_(lo.lng().radians(), hi.lng().radians()) {
    DCHECK(is_valid()) << lo << ", " << hi;
  }
  
  inline S2LatLngRect::S2LatLngRect(R1Interval const& lat, S1Interval const& lng)
    : lat_(lat), lng_(lng) {
    DCHECK(is_valid()) << lat << ", " << lng;
  }
  
  inline S2LatLngRect::S2LatLngRect()
      : lat_(R1Interval::Empty()), lng_(S1Interval::Empty()) {
  }
  
  inline S2LatLngRect S2LatLngRect::Empty() {
    return S2LatLngRect();
  }
  
  inline S2LatLngRect S2LatLngRect::Full() {
    return S2LatLngRect(FullLat(), FullLng());
  }
  
  inline bool S2LatLngRect::is_valid() const {
    // The lat/lng ranges must either be both empty or both non-empty.
    return (fabs(lat_.lo()) <= M_PI_2 &&
            fabs(lat_.hi()) <= M_PI_2 &&
            lng_.is_valid() &&
            lat_.is_empty() == lng_.is_empty());
  }
  
  inline bool S2LatLngRect::is_empty() const {
    return lat_.is_empty();
  }
  
  inline bool S2LatLngRect::is_full() const {
    return lat_ == FullLat() && lng_.is_full();
  }
  
  inline bool S2LatLngRect::is_point() const {
    return lat_.lo() == lat_.hi() && lng_.lo() == lng_.hi();
  }
  
  inline bool S2LatLngRect::operator==(S2LatLngRect const& other) const {
    return lat() == other.lat() && lng() == other.lng();
  }
  
  inline bool S2LatLngRect::operator!=(S2LatLngRect const& other) const {
    return !operator==(other);
  }
  
  ostream& operator<<(ostream& os, S2LatLngRect const& r);
  
  #endif  // UTIL_GEOMETRY_S2LATLNGRECT_H_
  