text: // Copyright 2017 Google Inc. All Rights Reserved.
  //
  // 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.
  //
  
  // Author: ericv@google.com (Eric Veach)
  
  #include "s2/s2shape_index_buffered_region.h"
  
  #include <iostream>
  #include <memory>
  #include <gtest/gtest.h>
  #include "s2/third_party/absl/memory/memory.h"
  #include "s2/mutable_s2shape_index.h"
  #include "s2/s2cap.h"
  #include "s2/s2cell_union.h"
  #include "s2/s2polygon.h"
  #include "s2/s2region_coverer.h"
  #include "s2/s2shape_index.h"
  #include "s2/s2testing.h"
  #include "s2/s2text_format.h"
  
  using s2_absl::make_unique;
  using s2textformat::MakeIndexOrDie;
  using s2textformat::MakePointOrDie;
  using std::cout;
  
  TEST(S2ShapeIndexBufferedRegion, EmptyIndex) {
    // Test buffering an empty S2ShapeIndex.
    MutableS2ShapeIndex index;
    S1ChordAngle radius(S1Angle::Degrees(2));
    S2ShapeIndexBufferedRegion region(&index, radius);
    S2RegionCoverer coverer;
    S2CellUnion covering = coverer.GetCovering(region);
    EXPECT_TRUE(covering.empty());
  }
  
  TEST(S2ShapeIndexBufferedRegion, FullPolygon) {
    // Test buffering an S2ShapeIndex that contains a full polygon.
    auto index = MakeIndexOrDie("# # full");
    S1ChordAngle radius(S1Angle::Degrees(2));
    S2ShapeIndexBufferedRegion region(index.get(), radius);
    S2RegionCoverer coverer;
    S2CellUnion covering = coverer.GetCovering(region);
    ASSERT_EQ(6, covering.num_cells());
    for (S2CellId id : covering) {
      EXPECT_TRUE(id.is_face());
    }
  }
  
  TEST(S2ShapeIndexBufferedRegion, FullAfterBuffering) {
    // Test a region that becomes the full polygon after buffering.
    auto index = MakeIndexOrDie("0:0 | 0:90 | 0:180 | 0:-90 | 90:0 | -90:0 # #");
    S1ChordAngle radius(S1Angle::Degrees(60));
    S2ShapeIndexBufferedRegion region(index.get(), radius);
    S2RegionCoverer coverer;
    coverer.mutable_options()->set_max_cells(1000);
    S2CellUnion covering = coverer.GetCovering(region);
    ASSERT_EQ(6, covering.num_cells());
    for (S2CellId id : covering) {
      EXPECT_TRUE(id.is_face());
    }
  }
  
  TEST(S2ShapeIndexBufferedRegion, PointZeroRadius) {
    // Test that buffering a point using a zero radius produces a non-empty
    // covering.  (This requires using "less than or equal to" distance tests.)
    auto index = MakeIndexOrDie("34:25 # #");
    S2ShapeIndexBufferedRegion region(index.get(), S1ChordAngle::Zero());
    S2RegionCoverer coverer;
    S2CellUnion covering = coverer.GetCovering(region);
    EXPECT_EQ(1, covering.num_cells());
    for (S2CellId id : covering) {
      EXPECT_TRUE(id.is_leaf());
    }
  }
  
  TEST(S2ShapeIndexBufferedRegion, BufferedPointVsCap) {
    // Compute an S2Cell covering of a buffered S2Point, then make sure that the
    // covering is equivalent to the corresponding S2Cap.
    auto index = MakeIndexOrDie("3:5 # #");
    S2Point point = MakePointOrDie("3:5");
    S1ChordAngle radius(S1Angle::Degrees(2));
    S2ShapeIndexBufferedRegion region(index.get(), radius);
    S2RegionCoverer coverer;
    coverer.mutable_options()->set_max_cells(50);
    S2CellUnion covering = coverer.GetCovering(region);
    S2Cap equivalent_cap(point, radius);
    S2Testing::CheckCovering(equivalent_cap, covering, true);
  }
  
  // Verifies that an arbitrary S2ShapeIndex is buffered correctly, by first
  // converting the covering to an S2Polygon and then checking that (a) the
  // S2Polygon contains the original geometry and (b) the distance between the
  // original geometry and the boundary of the S2Polygon is at least "radius".
  //
  // The "radius" parameter is an S1Angle for convenience.
  // TODO(ericv): Add Degrees, Radians, etc, methods to S1ChordAngle?
  void TestBufferIndex(const string& index_str, S1Angle radius_angle,
                       S2RegionCoverer* coverer) {
    auto index = MakeIndexOrDie(index_str);
    S1ChordAngle radius(radius_angle);
    S2ShapeIndexBufferedRegion region(index.get(), radius);
    S2CellUnion covering = coverer->GetCovering(region);
    S2_LOG(INFO) << "Covering uses " << covering.num_cells()
              << " cells vs. max of " << coverer->options().max_cells();
    if (S2_VLOG_IS_ON(2)) {
      // Output the cells in the covering for visualization purposes.
      for (S2CellId id : covering) {
        cout << "\nS2Polygon: " << s2textformat::ToString(S2Polygon(S2Cell(id)));
      }
      cout << "\n\n" << std::flush;
    }
    // Compute an S2Polygon representing the union of the cells in the covering.
    S2Polygon covering_polygon;
    covering_polygon.InitToCellUnionBorder(covering);
    MutableS2ShapeIndex covering_index;
    covering_index.Add(make_unique<S2Polygon::Shape>(&covering_polygon));
  
    // (a) Check that the covering contains the original index.
    EXPECT_TRUE(S2BooleanOperation::Contains(covering_index, *index));
  
    // (b) Check that the distance between the boundary of the covering and the
    // the original indexed geometry is at least "radius".
    S2ClosestEdgeQuery query(&covering_index);
    query.mutable_options()->set_include_interiors(false);
    S2ClosestEdgeQuery::ShapeIndexTarget target(index.get());
    EXPECT_FALSE(query.IsDistanceLess(&target, radius));
  }
  
  TEST(S2ShapeIndexBufferedRegion, PointSet) {
    // Test buffering a set of points.
    S2RegionCoverer coverer;
    coverer.mutable_options()->set_max_cells(100);
    TestBufferIndex("10:20 | 10:23 | 10:26 # #", S1Angle::Degrees(5), &coverer);
  }
  
  TEST(S2ShapeIndexBufferedRegion, Polyline) {
    // Test buffering a polyline.
    S2RegionCoverer coverer;
    coverer.mutable_options()->set_max_cells(100);
    TestBufferIndex("# 10:5, 20:30, -10:60, -60:100 #",
                    S1Angle::Degrees(2), &coverer);
  }
  
  TEST(S2ShapeIndexBufferedRegion, PolygonWithHole) {
    // Test buffering a polygon with a hole.
    S2RegionCoverer coverer;
    coverer.mutable_options()->set_max_cells(100);
    TestBufferIndex("# # 10:10, 10:100, 70:0; 11:11, 69:0, 11:99",
                    S1Angle::Degrees(2), &coverer);
  }
  