Source file src/github.com/golang/geo/s2/polygon_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2015 Google Inc. All rights reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package s2
    16  
    17  import (
    18  	"math"
    19  	"math/rand"
    20  	"testing"
    21  
    22  	"github.com/golang/geo/s1"
    23  )
    24  
    25  const (
    26  	// A set of nested loops around the LatLng point 0:0.
    27  	// Every vertex of nearLoop0 is also a vertex of nearLoop1.
    28  	nearPoint    = "0:0"
    29  	nearLoop0    = "-1:0, 0:1, 1:0, 0:-1;"
    30  	nearLoop1    = "-1:-1, -1:0, -1:1, 0:1, 1:1, 1:0, 1:-1, 0:-1;"
    31  	nearLoop2    = "-1:-2, -2:5, 5:-2;"
    32  	nearLoop3    = "-2:-2, -3:6, 6:-3;"
    33  	nearLoopHemi = "0:-90, -90:0, 0:90, 90:0;"
    34  
    35  	// A set of nested loops around the LatLng point 0:180. Every vertex of
    36  	// farLoop0 and farLoop2 belongs to farLoop1, and all the loops except
    37  	// farLoop2 are non-convex.
    38  	farPoint    = "0:180"
    39  	farLoop0    = "0:179, 1:180, 0:-179, 2:-180;"
    40  	farLoop1    = "0:179, -1:179, 1:180, -1:-179, 0:-179, 3:-178, 2:-180, 3:178;"
    41  	farLoop2    = "3:-178, 3:178, -1:179, -1:-179;"
    42  	farLoop3    = "-3:-178, 4:-177, 4:177, -3:178, -2:179;"
    43  	farLoopHemi = "0:-90, 60:90, -60:90;"
    44  
    45  	// A set of nested loops around the LatLng point -90:0.
    46  	southLoopPoint = "-89.9999:0.001"
    47  	southLoop0a    = "-90:0, -89.99:0.01, -89.99:0;"
    48  	southLoop0b    = "-90:0, -89.99:0.03, -89.99:0.02;"
    49  	southLoop0c    = "-90:0, -89.99:0.05, -89.99:0.04;"
    50  	southLoop1     = "-90:0, -89.9:0.1, -89.9:-0.1;"
    51  	southLoop2     = "-90:0, -89.8:0.2, -89.8:-0.2;"
    52  	southLoopHemi  = "0:-180, 0:60, 0:-60;"
    53  
    54  	// Two different loops that surround all the near and far loops except
    55  	// for the hemispheres.
    56  	nearFarLoop1 = "-1:-9, -9:-9, -9:9, 9:9, 9:-9, 1:-9, " +
    57  		"1:-175, 9:-175, 9:175, -9:175, -9:-175, -1:-175;"
    58  	nearFarLoop2 = "-2:15, -2:170, -8:-175, 8:-175, " +
    59  		"2:170, 2:15, 8:-4, -8:-4;"
    60  
    61  	// Loop that results from intersection of other loops.
    62  	farHemiSouthHemiLoop = "0:-180, 0:90, -60:90, 0:-90;"
    63  
    64  	// Rectangles that form a cross, with only shared vertices, no crossing
    65  	// edges. Optional holes outside the intersecting region.
    66  	loopCross1          = "-2:1, -1:1, 1:1, 2:1, 2:-1, 1:-1, -1:-1, -2:-1;"
    67  	loopCross1SideHole  = "-1.5:0.5, -1.2:0.5, -1.2:-0.5, -1.5:-0.5;"
    68  	loopCrossCenterHole = "-0.5:0.5, 0.5:0.5, 0.5:-0.5, -0.5:-0.5;"
    69  	loopCross2SideHole  = "0.5:-1.5, 0.5:-1.2, -0.5:-1.2, -0.5:-1.5;"
    70  	loopCross2          = "1:-2, 1:-1, 1:1, 1:2, -1:2, -1:1, -1:-1, -1:-2;"
    71  
    72  	// Two rectangles that intersect, but no edges cross and there's always
    73  	// local containment (rather than crossing) at each shared vertex.
    74  	// In this ugly ASCII art, 1 is A+B, 2 is B+C:
    75  	//   +---+---+---+
    76  	//   | A | B | C |
    77  	//   +---+---+---+
    78  	loopOverlap1          = "0:1, 1:1, 2:1, 2:0, 1:0, 0:0;"
    79  	loopOverlap1SideHole  = "0.2:0.8, 0.8:0.8, 0.8:0.2, 0.2:0.2;"
    80  	loopOverlapCenterHole = "1.2:0.8, 1.8:0.8, 1.8:0.2, 1.2:0.2;"
    81  	loopOverlap2SideHole  = "2.2:0.8, 2.8:0.8, 2.8:0.2, 2.2:0.2;"
    82  	loopOverlap2          = "1:1, 2:1, 3:1, 3:0, 2:0, 1:0;"
    83  
    84  	// By symmetry, the intersection of the two polygons has almost half the area
    85  	// of either polygon.
    86  	//   +---+
    87  	//   | 3 |
    88  	//   +---+---+
    89  	//   |3+4| 4 |
    90  	//   +---+---+
    91  	loopOverlap3 = "-10:10, 0:10, 0:-10, -10:-10, -10:0"
    92  	loopOverlap4 = "-10:0, 10:0, 10:-10, -10:-10"
    93  )
    94  
    95  var (
    96  	// Some standard polygons to use in the tests.
    97  	emptyPolygon = &Polygon{}
    98  	fullPolygon  = FullPolygon()
    99  
   100  	near0Polygon     = makePolygon(nearLoop0, true)
   101  	near01Polygon    = makePolygon(nearLoop0+nearLoop1, true)
   102  	near30Polygon    = makePolygon(nearLoop3+nearLoop0, true)
   103  	near23Polygon    = makePolygon(nearLoop2+nearLoop3, true)
   104  	near0231Polygon  = makePolygon(nearLoop0+nearLoop2+nearLoop3+nearLoop1, true)
   105  	near023H1Polygon = makePolygon(nearLoop0+nearLoop2+nearLoop3+nearLoopHemi+nearLoop1, true)
   106  
   107  	far01Polygon    = makePolygon(farLoop0+farLoop1, true)
   108  	far21Polygon    = makePolygon(farLoop2+farLoop1, true)
   109  	far231Polygon   = makePolygon(farLoop2+farLoop3+farLoop1, true)
   110  	far2H0Polygon   = makePolygon(farLoop2+farLoopHemi+farLoop0, true)
   111  	far2H013Polygon = makePolygon(farLoop2+farLoopHemi+farLoop0+farLoop1+farLoop3, true)
   112  
   113  	south0abPolygon     = makePolygon(southLoop0a+southLoop0b, true)
   114  	south2Polygon       = makePolygon(southLoop2, true)
   115  	south20b1Polygon    = makePolygon(southLoop2+southLoop0b+southLoop1, true)
   116  	south2H1Polygon     = makePolygon(southLoop2+southLoopHemi+southLoop1, true)
   117  	south20bH0acPolygon = makePolygon(southLoop2+southLoop0b+southLoopHemi+
   118  		southLoop0a+southLoop0c, true)
   119  
   120  	nf1N10F2S10abcPolygon = makePolygon(southLoop0c+farLoop2+nearLoop1+
   121  		nearFarLoop1+nearLoop0+southLoop1+southLoop0b+southLoop0a, true)
   122  
   123  	nf2N2F210S210abPolygon = makePolygon(farLoop2+southLoop0a+farLoop1+
   124  		southLoop1+farLoop0+southLoop0b+nearFarLoop2+southLoop2+nearLoop2, true)
   125  
   126  	f32n0Polygon  = makePolygon(farLoop2+nearLoop0+farLoop3, true)
   127  	n32s0bPolygon = makePolygon(nearLoop3+southLoop0b+nearLoop2, true)
   128  
   129  	cross1Polygon           = makePolygon(loopCross1, true)
   130  	cross1SideHolePolygon   = makePolygon(loopCross1+loopCross1SideHole, true)
   131  	cross1CenterHolePolygon = makePolygon(loopCross1+loopCrossCenterHole, true)
   132  	cross2Polygon           = makePolygon(loopCross2, true)
   133  	cross2SideHolePolygon   = makePolygon(loopCross2+loopCross2SideHole, true)
   134  	cross2CenterHolePolygon = makePolygon(loopCross2+loopCrossCenterHole, true)
   135  
   136  	overlap1Polygon           = makePolygon(loopOverlap1, true)
   137  	overlap1SideHolePolygon   = makePolygon(loopOverlap1+loopOverlap1SideHole, true)
   138  	overlap1CenterHolePolygon = makePolygon(loopOverlap1+loopOverlapCenterHole, true)
   139  	overlap2Polygon           = makePolygon(loopOverlap2, true)
   140  	overlap2SideHolePolygon   = makePolygon(loopOverlap2+loopOverlap2SideHole, true)
   141  	overlap2CenterHolePolygon = makePolygon(loopOverlap2+loopOverlapCenterHole, true)
   142  
   143  	overlap3Polygon = makePolygon(loopOverlap3, true)
   144  	overlap4Polygon = makePolygon(loopOverlap4, true)
   145  
   146  	farHemiPolygon      = makePolygon(farLoopHemi, true)
   147  	southHemiPolygon    = makePolygon(southLoopHemi, true)
   148  	farSouthHemiPolygon = makePolygon(farHemiSouthHemiLoop, true)
   149  )
   150  
   151  func TestPolygonInitSingleLoop(t *testing.T) {
   152  	if !PolygonFromLoops([]*Loop{EmptyLoop()}).IsEmpty() {
   153  		t.Errorf("polygon from Empty Loop should make an EmptyPolygon")
   154  	}
   155  	if !PolygonFromLoops([]*Loop{FullLoop()}).IsFull() {
   156  		t.Errorf("polygon from Full Loop should make a FullPolygon")
   157  	}
   158  	p := PolygonFromLoops([]*Loop{makeLoop("0:0, 0:10, 10:0")})
   159  	if got, want := p.numVertices, 3; got != want {
   160  		t.Errorf("%v.numVertices = %v, want %v", p, got, want)
   161  	}
   162  }
   163  
   164  func TestPolygonEmpty(t *testing.T) {
   165  	shape := emptyPolygon
   166  
   167  	if got, want := shape.NumEdges(), 0; got != want {
   168  		t.Errorf("shape.NumEdges() = %v, want %v", got, want)
   169  	}
   170  	if got, want := shape.NumChains(), 0; got != want {
   171  		t.Errorf("shape.NumChains() = %v, want %v", got, want)
   172  	}
   173  	if got, want := shape.Dimension(), 2; got != want {
   174  		t.Errorf("shape.Dimension() = %v, want %v", got, want)
   175  	}
   176  	if !shape.IsEmpty() {
   177  		t.Errorf("shape.IsEmpty() = false, want true")
   178  	}
   179  	if shape.IsFull() {
   180  		t.Errorf("shape.IsFull() = true, want false")
   181  	}
   182  	if shape.ReferencePoint().Contained {
   183  		t.Errorf("shape.ReferencePoint().Contained = true, want false")
   184  	}
   185  }
   186  
   187  func TestPolygonFull(t *testing.T) {
   188  	shape := fullPolygon
   189  
   190  	if got, want := shape.NumEdges(), 0; got != want {
   191  		t.Errorf("shape.NumEdges() = %v, want %v", got, want)
   192  	}
   193  	if got, want := shape.NumChains(), 1; got != want {
   194  		t.Errorf("shape.NumChains() = %v, want %v", got, want)
   195  	}
   196  	if got, want := shape.Chain(0).Start, 0; got != want {
   197  		t.Errorf("fullPolygon.Chain(0).Start = %d, want %d", got, want)
   198  	}
   199  	if got, want := shape.Chain(0).Length, 0; got != want {
   200  		t.Errorf("fullPolygon.Chain(0).Length = %d, want %d", got, want)
   201  	}
   202  	if got, want := shape.Dimension(), 2; got != want {
   203  		t.Errorf("shape.Dimension() = %v, want %v", got, want)
   204  	}
   205  	if shape.IsEmpty() {
   206  		t.Errorf("shape.IsEmpty() = true, want false")
   207  	}
   208  	if !shape.IsFull() {
   209  		t.Errorf("shape.IsFull() = false, want true")
   210  	}
   211  	if !shape.ReferencePoint().Contained {
   212  		t.Errorf("shape.ReferencePoint().Contained = false, want true")
   213  	}
   214  }
   215  
   216  func TestPolygonInitLoopPropertiesGetsRightBounds(t *testing.T) {
   217  	// Before the change to initLoopProperties to start the bounds as an
   218  	// EmptyRect instead of it default to the zero rect, the bounds
   219  	// computations failed. Lo was set to min (0, 12.55) and Hi was set to
   220  	// max (0, -70.02).  So this poly would have a bounds of
   221  	//   Lo: [0, -70.05],     Hi: [12.58, 0]]      instead of:
   222  	//   Lo: [12.55, -70.05], Hi: [12.58, -70.02]]
   223  
   224  	p := PolygonFromLoops([]*Loop{
   225  		makeLoop("12.55:-70.05, 12.55:-70.02, 12.58:-70.02, 12.58:-70.05"),
   226  		makeLoop("12.56:-70.04, 12.56:-70.03, 12.58:-70.03, 12.58:-70.04"),
   227  	})
   228  	want := rectFromDegrees(12.55, -70.05, 12.58, -70.02)
   229  	if got := p.RectBound(); !rectsApproxEqual(got, want, 1e-6, 1e-6) {
   230  		t.Errorf("%v.RectBound() = %v, want %v", p, got, want)
   231  	}
   232  }
   233  
   234  func TestPolygonShape(t *testing.T) {
   235  	const numLoops = 100
   236  	const numVerticesPerLoop = 6
   237  	concentric := concentricLoopsPolygon(PointFromCoords(1, 0, 0), numLoops, numVerticesPerLoop)
   238  
   239  	tests := []struct {
   240  		p *Polygon
   241  	}{
   242  		{near0Polygon},    // one loop polygon
   243  		{near0231Polygon}, // several loops polygon
   244  		{concentric},      // many loops polygon
   245  	}
   246  
   247  	for _, test := range tests {
   248  		shape := Shape(test.p)
   249  
   250  		if got, want := shape.NumEdges(), test.p.numVertices; got != want {
   251  			t.Errorf("the number of vertices in a polygon should equal the number of edges. got %v, want %v", got, want)
   252  		}
   253  		if got, want := shape.NumChains(), test.p.NumLoops(); got != want {
   254  			t.Errorf("the number of loops in a polygon should equal the number of chains. got %v, want %v", got, want)
   255  		}
   256  
   257  		edgeID := 0
   258  		for i, l := range test.p.loops {
   259  			if edgeID != shape.Chain(i).Start {
   260  				t.Errorf("the edge id of the start of loop(%d) should equal the sum of vertices so far in the polygon. got %d, want %d", i, shape.Chain(i).Start, edgeID)
   261  			}
   262  			if len(l.vertices) != shape.Chain(i).Length {
   263  				t.Errorf("the length of Chain(%d) should equal the length of loop(%d), got %v, want %v", i, i, shape.Chain(i).Length, len(l.vertices))
   264  			}
   265  			for j := 0; j < len(l.Vertices()); j++ {
   266  				edge := shape.Edge(edgeID)
   267  				if l.OrientedVertex(j) != edge.V0 {
   268  					t.Errorf("l.Vertex(%d) = %v, want %v", j, l.Vertex(j), edge.V0)
   269  				}
   270  				if l.OrientedVertex(j+1) != edge.V1 {
   271  					t.Errorf("l.Vertex(%d) = %v, want %v", j+1, l.Vertex(j+1), edge.V1)
   272  				}
   273  				edgeID++
   274  			}
   275  		}
   276  		if got, want := shape.Dimension(), 2; got != want {
   277  			t.Errorf("shape.Dimension() = %v, want %v", got, want)
   278  		}
   279  		if shape.IsEmpty() {
   280  			t.Errorf("shape.IsEmpty() = true, want false")
   281  		}
   282  		if shape.IsFull() {
   283  			t.Errorf("shape.IsFull() = true, want false")
   284  		}
   285  
   286  		if got, want := test.p.ContainsPoint(OriginPoint()), shape.ReferencePoint().Contained; got != want {
   287  			t.Errorf("p.ContainsPoint(OriginPoint()) != shape.ReferencePoint().Contained")
   288  		}
   289  	}
   290  }
   291  
   292  // reverseLoopVertices reverses the order of all vertices in the given loop.
   293  func reverseLoopVertices(l *Loop) {
   294  	for i := 0; i < len(l.vertices)/2; i++ {
   295  		l.vertices[i], l.vertices[len(l.vertices)-i-1] = l.vertices[len(l.vertices)-i-1], l.vertices[i]
   296  	}
   297  }
   298  
   299  // shuffleLoops randomizes the slice of loops using Fisher-Yates shuffling.
   300  func shuffleLoops(loops []*Loop) {
   301  	n := len(loops)
   302  	for i := 0; i < n; i++ {
   303  		// choose index uniformly in [i, n-1]
   304  		r := i + rand.Intn(n-i)
   305  		loops[r], loops[i] = loops[i], loops[r]
   306  	}
   307  }
   308  
   309  // modifyPolygonFunc declares a function that can tweak a Polygon for testing.
   310  type modifyPolygonFunc func(p *Polygon)
   311  
   312  // polygonSetInvalidLoopNesting flips a random loops orientation within the polygon.
   313  func polygonSetInvalidLoopNesting(p *Polygon) {
   314  	if len(p.loops) > 0 {
   315  		i := randomUniformInt(len(p.loops))
   316  		p.loops[i].Invert()
   317  	}
   318  }
   319  
   320  // polygonSetInvalidLoopDepth randomly changes a loops depth value in the given polygon
   321  func polygonSetInvalidLoopDepth(p *Polygon) {
   322  	i := randomUniformInt(len(p.loops))
   323  	if i == 0 || oneIn(3) {
   324  		p.loops[i].depth = -1
   325  	} else {
   326  		p.loops[i].depth = p.loops[i-1].depth + 2
   327  	}
   328  }
   329  
   330  // generatePolygonConcentricTestLoops creates the given number of nested regular
   331  // loops around a common center point. All loops will have the same number of
   332  // vertices (at least minVertices). Furthermore, the vertices at the same index
   333  // position are collinear with the common center point of all the loops. The
   334  // loop radii decrease exponentially in order to prevent accidental loop crossings
   335  // when one of the loops is modified.
   336  func generatePolygonConcentricTestLoops(numLoops, minVertices int) []*Loop {
   337  	var loops []*Loop
   338  	center := randomPoint()
   339  	numVertices := minVertices + randomUniformInt(10)
   340  	for i := 0; i < numLoops; i++ {
   341  		radius := s1.Angle(80*math.Pow(0.1, float64(i))) * s1.Degree
   342  		loops = append(loops, RegularLoop(center, radius, numVertices))
   343  	}
   344  	return loops
   345  }
   346  
   347  func checkPolygonInvalid(t *testing.T, label string, loops []*Loop, initOriented bool, f modifyPolygonFunc) {
   348  	shuffleLoops(loops)
   349  	var polygon *Polygon
   350  	if initOriented {
   351  		polygon = PolygonFromOrientedLoops(loops)
   352  	} else {
   353  		polygon = PolygonFromLoops(loops)
   354  	}
   355  
   356  	if f != nil {
   357  		f(polygon)
   358  	}
   359  
   360  	if err := polygon.Validate(); err == nil {
   361  		t.Errorf("%s: %v.Validate() = %v, want non-nil", label, polygon, err)
   362  	}
   363  }
   364  
   365  func TestPolygonUninitializedIsValid(t *testing.T) {
   366  	p := &Polygon{}
   367  	if err := p.Validate(); err != nil {
   368  		t.Errorf("an uninitialized polygon failed validation: %v", err)
   369  	}
   370  }
   371  
   372  func TestPolygonIsValidLoopNestingInvalid(t *testing.T) {
   373  	const iters = 1000
   374  
   375  	for iter := 0; iter < iters; iter++ {
   376  		loops := generatePolygonConcentricTestLoops(2+randomUniformInt(4), 3)
   377  		// Randomly invert all the loops in order to generate cases where the
   378  		// outer loop encompasses almost the entire sphere. This tests different
   379  		// code paths because bounding box checks are not as useful.
   380  		if oneIn(2) {
   381  			for _, loop := range loops {
   382  				reverseLoopVertices(loop)
   383  			}
   384  		}
   385  		checkPolygonInvalid(t, "invalid nesting", loops, false, polygonSetInvalidLoopNesting)
   386  	}
   387  }
   388  
   389  // TODO(roberts): Implement remaining validity tests.
   390  // IsValidTests
   391  //   TestUnitLength
   392  //   TestVertexCount
   393  //   TestDuplicateVertex
   394  //   TestSelfIntersection
   395  //   TestEmptyLoop
   396  //   TestFullLoop
   397  //   TestLoopsCrossing
   398  //   TestDuplicateEdge
   399  //   TestInconsistentOrientations
   400  //   TestLoopDepthNegative
   401  //   TestLoopNestingInvalid
   402  //   TestFuzzTest
   403  
   404  func TestPolygonParent(t *testing.T) {
   405  	p1 := PolygonFromLoops([]*Loop{{}})
   406  	tests := []struct {
   407  		p    *Polygon
   408  		have int
   409  		want int
   410  		ok   bool
   411  	}{
   412  		{fullPolygon, 0, -1, false},
   413  		{p1, 0, -1, false},
   414  
   415  		// TODO: When multiple loops are supported, add more test cases to
   416  		// more fully show the parent levels.
   417  	}
   418  
   419  	for _, test := range tests {
   420  		if got, ok := test.p.Parent(test.have); ok != test.ok || got != test.want {
   421  			t.Errorf("%v.Parent(%d) = %d,%v, want %d,%v", test.p, test.have, got, ok, test.want, test.ok)
   422  		}
   423  	}
   424  }
   425  
   426  func TestPolygonLastDescendant(t *testing.T) {
   427  	p1 := PolygonFromLoops([]*Loop{{}})
   428  
   429  	tests := []struct {
   430  		p    *Polygon
   431  		have int
   432  		want int
   433  	}{
   434  		{fullPolygon, 0, 0},
   435  		{fullPolygon, -1, 0},
   436  
   437  		{p1, 0, 0},
   438  		{p1, -1, 0},
   439  
   440  		// TODO: When multiple loops are supported, add more test cases.
   441  	}
   442  
   443  	for _, test := range tests {
   444  		if got := test.p.LastDescendant(test.have); got != test.want {
   445  			t.Errorf("%v.LastDescendant(%d) = %d, want %d", test.p, test.have, got, test.want)
   446  		}
   447  	}
   448  }
   449  
   450  func TestPolygonContainsPoint(t *testing.T) {
   451  	tests := []struct {
   452  		polygon string
   453  		point   string
   454  	}{
   455  		{nearLoop0, nearPoint},
   456  		{nearLoop1, nearPoint},
   457  		{nearLoop2, nearPoint},
   458  		{nearLoop3, nearPoint},
   459  		{nearLoopHemi, nearPoint},
   460  		{southLoop0a, southLoopPoint},
   461  		{southLoop1, southLoopPoint},
   462  		{southLoop2, southLoopPoint},
   463  		{southLoopHemi, southLoopPoint},
   464  	}
   465  
   466  	for _, test := range tests {
   467  		poly := makePolygon(test.polygon, true)
   468  		pt := parsePoint(test.point)
   469  		if !poly.ContainsPoint(pt) {
   470  			t.Errorf("%v.ContainsPoint(%v) = false, want true", test.polygon, test.point)
   471  		}
   472  	}
   473  }
   474  
   475  // Given a pair of polygons where A contains B, check that various identities
   476  // involving union, intersection, and difference operations hold true.
   477  func testPolygonOneNestedPair(t *testing.T, a, b *Polygon) {
   478  	if !a.Contains(b) {
   479  		t.Errorf("%v.Contains(%v) = false, want true", a, b)
   480  	}
   481  	if got, want := a.Intersects(b), !b.IsEmpty(); got != want {
   482  		t.Errorf("%v.Intersects(%v) = %v, want %v", a, b, got, want)
   483  	}
   484  	if got, want := b.Intersects(a), !b.IsEmpty(); got != want {
   485  		t.Errorf("%v.Intersects(%v) = %v, want %v", b, a, got, want)
   486  	}
   487  
   488  	// TODO(roberts): Add the remaining checks related to construction
   489  	// via union, intersection, and difference.
   490  }
   491  
   492  // Given a pair of disjoint polygons A and B, check that various identities
   493  // involving union, intersection, and difference operations hold true.
   494  func testPolygonOneDisjointPair(t *testing.T, a, b *Polygon) {
   495  	if a.Intersects(b) {
   496  		t.Errorf("%v.Intersects(%v) = true, want false", a, b)
   497  	}
   498  	if b.Intersects(a) {
   499  		t.Errorf("%v.Intersects(%v) = true, want false", b, a)
   500  	}
   501  	if got, want := a.Contains(b), b.IsEmpty(); got != want {
   502  		t.Errorf("%v.Contains(%v) = %v, want %v", b, a, got, want)
   503  	}
   504  
   505  	if got, want := b.Contains(a), a.IsEmpty(); got != want {
   506  		t.Errorf("%v.Contains(%v) = %v, want %v", b, a, got, want)
   507  	}
   508  
   509  	// TODO(roberts): Add the remaining checks related to construction
   510  	// via builder, union, intersection, and difference.
   511  }
   512  
   513  // Given polygons A and B whose union covers the sphere, check that various
   514  // identities involving union, intersection, and difference hold true.
   515  func testPolygonOneCoveringPair(t *testing.T, a, b *Polygon) {
   516  	if got, want := a.Contains(b), a.IsFull(); got != want {
   517  		t.Errorf("%v.Contains(%v) = %v, want %v", a, b, got, want)
   518  	}
   519  	if got, want := b.Contains(a), b.IsFull(); got != want {
   520  		t.Errorf("%v.Contains(%v) = %v, want %v", a, b, got, want)
   521  	}
   522  	// TODO(roberts): Add the remaining checks related to construction via union
   523  
   524  }
   525  
   526  // Given polygons A and B such that both A and its complement intersect both B
   527  // and its complement, check that various identities involving union,
   528  // intersection, and difference hold true.
   529  func testPolygonOneOverlappingPair(t *testing.T, a, b *Polygon) {
   530  	if a.Contains(b) {
   531  		t.Errorf("%v.Contains(%v) = true, want false", a, b)
   532  	}
   533  	if b.Contains(a) {
   534  		t.Errorf("%v.Contains(%v) = true, want false", b, a)
   535  	}
   536  	if !a.Intersects(b) {
   537  		t.Errorf("%v.Intersects(%v) = false, want true", a, b)
   538  	}
   539  
   540  	// TODO(roberts): Add the remaining checks related to construction
   541  	// via builder, union, intersection, and difference.
   542  }
   543  
   544  // Given a pair of polygons where A contains B, test various identities
   545  // involving A, B, and their complements.
   546  func testPolygonNestedPair(t *testing.T, a, b *Polygon) {
   547  	// TODO(roberts): Uncomment once complement is completed
   548  	// a1 := InitToComplement(a)
   549  	// b1 := InitToComplement(b)
   550  
   551  	testPolygonOneNestedPair(t, a, b)
   552  	// testPolygonOneNestedPair(t, b1, a1)
   553  	// testPolygonOneDisjointPair(t, a1, b)
   554  	// testPolygonOneCoveringPair(t, a, b1)
   555  }
   556  
   557  // Given a pair of disjoint polygons A and B, test various identities
   558  // involving A, B, and their complements.
   559  func testPolygonDisjointPair(t *testing.T, a, b *Polygon) {
   560  	// TODO(roberts): Uncomment once complement is completed
   561  	// a1 := InitToComplement(a)
   562  	// b1 := InitToComplement(b)
   563  
   564  	testPolygonOneDisjointPair(t, a, b)
   565  	// testPolygonOneCoveringPair(t, a1, b1)
   566  	// testPolygonOneNestedPair(t, a1, b)
   567  	// testPolygonOneNestedPair(t, b1, a)
   568  }
   569  
   570  // Given polygons A and B such that both A and its complement intersect both B
   571  // and its complement, test various identities involving these four polygons.
   572  func testPolygonOverlappingPair(t *testing.T, a, b *Polygon) {
   573  	// TODO(roberts): Uncomment once complement is completed
   574  	// a1 := InitToComplement(a);
   575  	// b1 := InitToComplement(b);
   576  
   577  	testPolygonOneOverlappingPair(t, a, b)
   578  	// testPolygonOneOverlappingPair(t, a1, b1);
   579  	// testPolygonOneOverlappingPair(t, a1, b);
   580  	// testPolygonOneOverlappingPair(t, a, b1);
   581  }
   582  
   583  // Test identities that should hold for any pair of polygons A, B and their
   584  // complements.
   585  func testPolygonComplements(t *testing.T, a, b *Polygon) {
   586  	// TODO(roberts): Uncomment once complement is completed
   587  	// a1 := InitToComplement(a);
   588  	// b1 := InitToComplement(b);
   589  
   590  	// testOneComplementPair(t, a, a1, b, b1)
   591  	// testOneComplementPair(t, a1, a, b, b1)
   592  	// testOneComplementPair(t, a, a1, b1, b)
   593  	// testOneComplementPair(t, a1, a, b1, b)
   594  
   595  	// TODO(roberts): Add the checks related to construction via union, etc.
   596  }
   597  
   598  func testPolygonDestructiveUnion(t *testing.T, a, b *Polygon) {
   599  	// TODO(roberts): Add the checks related to construction via union, etc.
   600  }
   601  
   602  func TestPolygonRelations(t *testing.T) {
   603  	tests := []struct {
   604  		a, b       *Polygon
   605  		contains   bool // A contains B
   606  		contained  bool // B contains A
   607  		intersects bool // A and B intersect
   608  	}{
   609  		{
   610  			a:          near01Polygon,
   611  			b:          emptyPolygon,
   612  			contains:   true,
   613  			contained:  false,
   614  			intersects: false,
   615  		},
   616  		{
   617  			a:          near01Polygon,
   618  			b:          near01Polygon,
   619  			contains:   true,
   620  			contained:  true,
   621  			intersects: true,
   622  		},
   623  		{
   624  			a:          fullPolygon,
   625  			b:          near01Polygon,
   626  			contains:   true,
   627  			contained:  false,
   628  			intersects: true,
   629  		},
   630  		{
   631  			a:          near01Polygon,
   632  			b:          near30Polygon,
   633  			contains:   false,
   634  			contained:  true,
   635  			intersects: true,
   636  		},
   637  		{
   638  			a:          near01Polygon,
   639  			b:          near23Polygon,
   640  			contains:   false,
   641  			contained:  false,
   642  			intersects: false,
   643  		},
   644  		{
   645  			a:          near01Polygon,
   646  			b:          near0231Polygon,
   647  			contains:   false,
   648  			contained:  true,
   649  			intersects: true,
   650  		},
   651  		{
   652  			a:          near01Polygon,
   653  			b:          near023H1Polygon,
   654  			contains:   false,
   655  			contained:  false,
   656  			intersects: false,
   657  		},
   658  		{
   659  			a:          near30Polygon,
   660  			b:          near23Polygon,
   661  			contains:   true,
   662  			contained:  false,
   663  			intersects: true,
   664  		},
   665  		{
   666  			a:          near30Polygon,
   667  			b:          near0231Polygon,
   668  			contains:   true,
   669  			contained:  false,
   670  			intersects: true,
   671  		},
   672  		{
   673  			a:          near30Polygon,
   674  			b:          near023H1Polygon,
   675  			contains:   false,
   676  			contained:  false,
   677  			intersects: true,
   678  		},
   679  		{
   680  			a:          near23Polygon,
   681  			b:          near0231Polygon,
   682  			contains:   false,
   683  			contained:  true,
   684  			intersects: true,
   685  		},
   686  		{
   687  			a:          near23Polygon,
   688  			b:          near023H1Polygon,
   689  			contains:   false,
   690  			contained:  false,
   691  			intersects: false,
   692  		},
   693  		{
   694  			a:          near0231Polygon,
   695  			b:          near023H1Polygon,
   696  			contains:   false,
   697  			contained:  false,
   698  			intersects: false,
   699  		},
   700  
   701  		{
   702  			a:          far01Polygon,
   703  			b:          far21Polygon,
   704  			contains:   false,
   705  			contained:  false,
   706  			intersects: false,
   707  		},
   708  		{
   709  			a:          far01Polygon,
   710  			b:          far231Polygon,
   711  			contains:   false,
   712  			contained:  true,
   713  			intersects: true,
   714  		},
   715  		{
   716  			a:          far01Polygon,
   717  			b:          far2H0Polygon,
   718  			contains:   false,
   719  			contained:  false,
   720  			intersects: false,
   721  		},
   722  		{
   723  			a:          far01Polygon,
   724  			b:          far2H013Polygon,
   725  			contains:   false,
   726  			contained:  false,
   727  			intersects: false,
   728  		},
   729  		{
   730  			a:          far21Polygon,
   731  			b:          far231Polygon,
   732  			contains:   false,
   733  			contained:  false,
   734  			intersects: false,
   735  		},
   736  		{
   737  			a:          far21Polygon,
   738  			b:          far2H0Polygon,
   739  			contains:   false,
   740  			contained:  false,
   741  			intersects: false,
   742  		},
   743  		{
   744  			a:          far21Polygon,
   745  			b:          far2H013Polygon,
   746  			contains:   false,
   747  			contained:  true,
   748  			intersects: true,
   749  		},
   750  		{
   751  			a:          far231Polygon,
   752  			b:          far2H0Polygon,
   753  			contains:   false,
   754  			contained:  false,
   755  			intersects: true,
   756  		},
   757  		{
   758  			a:          far231Polygon,
   759  			b:          far2H013Polygon,
   760  			contains:   false,
   761  			contained:  false,
   762  			intersects: true,
   763  		},
   764  		{
   765  			a:          far2H0Polygon,
   766  			b:          far2H013Polygon,
   767  			contains:   false,
   768  			contained:  false,
   769  			intersects: true,
   770  		},
   771  
   772  		{
   773  			a:          south0abPolygon,
   774  			b:          south2Polygon,
   775  			contains:   false,
   776  			contained:  true,
   777  			intersects: true,
   778  		},
   779  		{
   780  			a:          south0abPolygon,
   781  			b:          south20b1Polygon,
   782  			contains:   false,
   783  			contained:  false,
   784  			intersects: true,
   785  		},
   786  		{
   787  			a:          south0abPolygon,
   788  			b:          south2H1Polygon,
   789  			contains:   false,
   790  			contained:  true,
   791  			intersects: true,
   792  		},
   793  		{
   794  			a:          south0abPolygon,
   795  			b:          south20bH0acPolygon,
   796  			contains:   false,
   797  			contained:  true,
   798  			intersects: true,
   799  		},
   800  		{
   801  			a:          south2Polygon,
   802  			b:          south20b1Polygon,
   803  			contains:   true,
   804  			contained:  false,
   805  			intersects: true,
   806  		},
   807  		{
   808  			a:          south2Polygon,
   809  			b:          south2H1Polygon,
   810  			contains:   false,
   811  			contained:  false,
   812  			intersects: true,
   813  		},
   814  		{
   815  			a:          south2Polygon,
   816  			b:          south20bH0acPolygon,
   817  			contains:   false,
   818  			contained:  false,
   819  			intersects: true,
   820  		},
   821  		{
   822  			a:          south20b1Polygon,
   823  			b:          south2H1Polygon,
   824  			contains:   false,
   825  			contained:  false,
   826  			intersects: true,
   827  		},
   828  		{
   829  			a:          south20b1Polygon,
   830  			b:          south20bH0acPolygon,
   831  			contains:   false,
   832  			contained:  false,
   833  			intersects: true,
   834  		},
   835  		{
   836  			a:          south2H1Polygon,
   837  			b:          south20bH0acPolygon,
   838  			contains:   true,
   839  			contained:  false,
   840  			intersects: true,
   841  		},
   842  
   843  		{
   844  			a:          nf1N10F2S10abcPolygon,
   845  			b:          nf2N2F210S210abPolygon,
   846  			contains:   false,
   847  			contained:  false,
   848  			intersects: true,
   849  		},
   850  		{
   851  			a:          nf1N10F2S10abcPolygon,
   852  			b:          near23Polygon,
   853  			contains:   true,
   854  			contained:  false,
   855  			intersects: true,
   856  		},
   857  		{
   858  			a:          nf1N10F2S10abcPolygon,
   859  			b:          far21Polygon,
   860  			contains:   false,
   861  			contained:  false,
   862  			intersects: false,
   863  		},
   864  		{
   865  			a:          nf1N10F2S10abcPolygon,
   866  			b:          south0abPolygon,
   867  			contains:   false,
   868  			contained:  false,
   869  			intersects: false,
   870  		},
   871  		{
   872  			a:          nf1N10F2S10abcPolygon,
   873  			b:          f32n0Polygon,
   874  			contains:   true,
   875  			contained:  false,
   876  			intersects: true,
   877  		},
   878  
   879  		{
   880  			a:          nf2N2F210S210abPolygon,
   881  			b:          near01Polygon,
   882  			contains:   false,
   883  			contained:  false,
   884  			intersects: false,
   885  		},
   886  		{
   887  			a:          nf2N2F210S210abPolygon,
   888  			b:          far01Polygon,
   889  			contains:   true,
   890  			contained:  false,
   891  			intersects: true,
   892  		},
   893  		{
   894  			a:          nf2N2F210S210abPolygon,
   895  			b:          south20b1Polygon,
   896  			contains:   true,
   897  			contained:  false,
   898  			intersects: true,
   899  		},
   900  		{
   901  			a:          nf2N2F210S210abPolygon,
   902  			b:          south0abPolygon,
   903  			contains:   true,
   904  			contained:  false,
   905  			intersects: true,
   906  		},
   907  		{
   908  			a:          nf2N2F210S210abPolygon,
   909  			b:          n32s0bPolygon,
   910  			contains:   true,
   911  			contained:  false,
   912  			intersects: true,
   913  		},
   914  		{
   915  			a:          cross1Polygon,
   916  			b:          cross2Polygon,
   917  			contains:   false,
   918  			contained:  false,
   919  			intersects: true,
   920  		},
   921  		{
   922  			a:          cross1SideHolePolygon,
   923  			b:          cross2Polygon,
   924  			contains:   false,
   925  			contained:  false,
   926  			intersects: true,
   927  		},
   928  		{
   929  			a:          cross1CenterHolePolygon,
   930  			b:          cross2Polygon,
   931  			contains:   false,
   932  			contained:  false,
   933  			intersects: true,
   934  		},
   935  		{
   936  			a:          cross1Polygon,
   937  			b:          cross2SideHolePolygon,
   938  			contains:   false,
   939  			contained:  false,
   940  			intersects: true,
   941  		},
   942  		{
   943  			a:          cross1Polygon,
   944  			b:          cross2CenterHolePolygon,
   945  			contains:   false,
   946  			contained:  false,
   947  			intersects: true,
   948  		},
   949  		{
   950  			a:          cross1SideHolePolygon,
   951  			b:          cross2SideHolePolygon,
   952  			contains:   false,
   953  			contained:  false,
   954  			intersects: true,
   955  		},
   956  		{
   957  			a:          cross1CenterHolePolygon,
   958  			b:          cross2SideHolePolygon,
   959  			contains:   false,
   960  			contained:  false,
   961  			intersects: true,
   962  		},
   963  		{
   964  			a:          cross1SideHolePolygon,
   965  			b:          cross2CenterHolePolygon,
   966  			contains:   false,
   967  			contained:  false,
   968  			intersects: true,
   969  		},
   970  		{
   971  			a:          cross1CenterHolePolygon,
   972  			b:          cross2CenterHolePolygon,
   973  			contains:   false,
   974  			contained:  false,
   975  			intersects: true,
   976  		},
   977  		// These cases, when either polygon has a hole, test a different code path
   978  		// from the other cases.
   979  		{
   980  			a:          overlap1Polygon,
   981  			b:          overlap2Polygon,
   982  			contains:   false,
   983  			contained:  false,
   984  			intersects: true,
   985  		},
   986  		{
   987  			a:          overlap1SideHolePolygon,
   988  			b:          overlap2Polygon,
   989  			contains:   false,
   990  			contained:  false,
   991  			intersects: true,
   992  		},
   993  		{
   994  			a:          overlap1CenterHolePolygon,
   995  			b:          overlap2Polygon,
   996  			contains:   false,
   997  			contained:  false,
   998  			intersects: true,
   999  		},
  1000  		{
  1001  			a:          overlap1Polygon,
  1002  			b:          overlap2SideHolePolygon,
  1003  			contains:   false,
  1004  			contained:  false,
  1005  			intersects: true,
  1006  		},
  1007  		{
  1008  			a:          overlap1Polygon,
  1009  			b:          overlap2CenterHolePolygon,
  1010  			contains:   false,
  1011  			contained:  false,
  1012  			intersects: true,
  1013  		},
  1014  		{
  1015  			a:          overlap1SideHolePolygon,
  1016  			b:          overlap2SideHolePolygon,
  1017  			contains:   false,
  1018  			contained:  false,
  1019  			intersects: true,
  1020  		},
  1021  		{
  1022  			a:          overlap1CenterHolePolygon,
  1023  			b:          overlap2SideHolePolygon,
  1024  			contains:   false,
  1025  			contained:  false,
  1026  			intersects: true,
  1027  		},
  1028  		{
  1029  			a:          overlap1SideHolePolygon,
  1030  			b:          overlap2CenterHolePolygon,
  1031  			contains:   false,
  1032  			contained:  false,
  1033  			intersects: true,
  1034  		},
  1035  		{
  1036  			a:          overlap1CenterHolePolygon,
  1037  			b:          overlap2CenterHolePolygon,
  1038  			contains:   false,
  1039  			contained:  false,
  1040  			intersects: true,
  1041  		},
  1042  	}
  1043  
  1044  	for i, test := range tests {
  1045  		if got := test.a.Contains(test.b); got != test.contains {
  1046  			t.Errorf("%d. %v.Contains(%v) = %v, want %v", i, test.a, test.b, got, test.contains)
  1047  		}
  1048  
  1049  		if got := test.b.Contains(test.a); got != test.contained {
  1050  			t.Errorf("%d. %v.Contains(%v) = %v, want %v", i, test.b, test.a, got, test.contained)
  1051  		}
  1052  
  1053  		if got := test.a.Intersects(test.b); got != test.intersects {
  1054  			t.Errorf("%v.Intersects(%v) = %v, want %v", test.a, test.b, got, test.intersects)
  1055  		}
  1056  
  1057  		if test.contains {
  1058  			testPolygonNestedPair(t, test.a, test.b)
  1059  		}
  1060  		if test.contained {
  1061  			testPolygonNestedPair(t, test.b, test.a)
  1062  		}
  1063  		if !test.intersects {
  1064  			testPolygonDisjointPair(t, test.a, test.b)
  1065  		}
  1066  		if test.intersects && !(test.contains || test.contained) {
  1067  			testPolygonOverlappingPair(t, test.a, test.b)
  1068  		}
  1069  		testPolygonDestructiveUnion(t, test.a, test.b)
  1070  		testPolygonComplements(t, test.a, test.b)
  1071  	}
  1072  
  1073  	testPolygonNestedPair(t, emptyPolygon, emptyPolygon)
  1074  	testPolygonNestedPair(t, fullPolygon, emptyPolygon)
  1075  	testPolygonNestedPair(t, fullPolygon, fullPolygon)
  1076  }
  1077  
  1078  func TestPolygonArea(t *testing.T) {
  1079  	tests := []struct {
  1080  		have *Polygon
  1081  		want float64
  1082  	}{
  1083  		{have: emptyPolygon, want: 0},
  1084  		{have: fullPolygon, want: 4 * math.Pi},
  1085  		{have: southHemiPolygon, want: 2 * math.Pi},
  1086  		{have: farSouthHemiPolygon, want: math.Pi},
  1087  		{
  1088  			// compare the polygon of two shells to the sum of its loops.
  1089  			have: makePolygon(loopCross1SideHole+loopCrossCenterHole, true),
  1090  			// the strings for the loops contain ';' so copy and paste without it
  1091  			want: makeLoop("-1.5:0.5, -1.2:0.5, -1.2:-0.5, -1.5:-0.5").Area() +
  1092  				makeLoop("-0.5:0.5, 0.5:0.5, 0.5:-0.5, -0.5:-0.5").Area(),
  1093  		},
  1094  		{
  1095  			// test that polygon with a shell and a hole matches its loop parts.
  1096  			have: makePolygon(loopCross1+loopCrossCenterHole, true),
  1097  			// the strings for the loops contain ';' so copy and paste without it
  1098  			want: makeLoop("-2:1, -1:1, 1:1, 2:1, 2:-1, 1:-1, -1:-1, -2:-1").Area() -
  1099  				makeLoop("-0.5:0.5, 0.5:0.5, 0.5:-0.5, -0.5:-0.5").Area(),
  1100  		},
  1101  	}
  1102  
  1103  	for _, test := range tests {
  1104  		if got := test.have.Area(); !float64Eq(got, test.want) {
  1105  			t.Errorf("%v.Area() = %v, want %v", test.have, got, test.want)
  1106  		}
  1107  	}
  1108  }
  1109  
  1110  func TestPolygonCentroid(t *testing.T) {
  1111  	tests := []struct {
  1112  		have *Polygon
  1113  		want Point
  1114  	}{
  1115  		{have: emptyPolygon, want: Point{}},
  1116  		{have: fullPolygon, want: Point{}},
  1117  		{
  1118  			// compare the polygon of two shells to the sum of its loops.
  1119  			have: makePolygon(loopCross1SideHole+loopCrossCenterHole, true),
  1120  			// the strings for the loops contain ';' so copy and paste without it
  1121  			want: Point{
  1122  				makeLoop("-1.5:0.5, -1.2:0.5, -1.2:-0.5, -1.5:-0.5").Centroid().Vector.Add(
  1123  					makeLoop("-0.5:0.5, 0.5:0.5, 0.5:-0.5, -0.5:-0.5").Centroid().Vector)},
  1124  		},
  1125  		{
  1126  			// test that polygon with a shell and a hole matches its loop parts.
  1127  			have: makePolygon(loopCross1+loopCrossCenterHole, true),
  1128  			// the strings for the loops contain ';' so copy and paste without it
  1129  			want: Point{
  1130  				makeLoop("-2:1, -1:1, 1:1, 2:1, 2:-1, 1:-1, -1:-1, -2:-1").Centroid().Vector.Sub(
  1131  					makeLoop("-0.5:0.5, 0.5:0.5, 0.5:-0.5, -0.5:-0.5").Centroid().Vector)},
  1132  		},
  1133  	}
  1134  
  1135  	for _, test := range tests {
  1136  		if got := test.have.Centroid(); got.Vector.Cmp(test.want.Vector) != 0 {
  1137  			t.Errorf("%v.Centroid() = %v, want %v", test.have, got, test.want)
  1138  		}
  1139  	}
  1140  }
  1141  
  1142  func TestPolygonInvert(t *testing.T) {
  1143  	origin := PointFromLatLng(LatLngFromDegrees(0, 0))
  1144  	pt := PointFromLatLng(LatLngFromDegrees(30, 30))
  1145  	p := PolygonFromLoops([]*Loop{
  1146  		RegularLoop(origin, 1000/earthRadiusKm, 100),
  1147  	})
  1148  
  1149  	if p.ContainsPoint(pt) {
  1150  		t.Errorf("polygon contains point outside itself")
  1151  	}
  1152  
  1153  	p.Invert()
  1154  	if !p.ContainsPoint(pt) {
  1155  		t.Errorf("inverted polygon does not contain point that is inside itself")
  1156  	}
  1157  }
  1158  
  1159  // TODO(roberts): Remaining Tests
  1160  // TestInit
  1161  // TestMultipleInit
  1162  // TestInitSingleLoop
  1163  // TestCellConstructorAndContains
  1164  // TestOverlapFractions
  1165  // TestOriginNearPole
  1166  // TestTestApproxContainsAndDisjoint
  1167  // TestOneLoopPolygonShape
  1168  // TestSeveralLoopPolygonShape
  1169  // TestManyLoopPolygonShape
  1170  // TestPointInBigLoop
  1171  // TestOperations
  1172  // TestIntersectionSnapFunction
  1173  // TestIntersectionPreservesLoopOrder
  1174  // TestLoopPointers
  1175  // TestBug1 - Bug14
  1176  // TestPolylineIntersection
  1177  // TestSplitting
  1178  // TestInitToCellUnionBorder
  1179  // TestUnionWithAmbgiuousCrossings
  1180  // TestInitToSloppySupportsEmptyPolygons
  1181  // TestInitToSnappedDoesNotRotateVertices
  1182  // TestInitToSnappedWithSnapLevel
  1183  // TestInitToSnappedIsValid_A
  1184  // TestInitToSnappedIsValid_B
  1185  // TestInitToSnappedIsValid_C
  1186  // TestInitToSnappedIsValid_D
  1187  // TestProject
  1188  // TestDistance
  1189  //
  1190  // PolygonSimplifier
  1191  //   TestNoSimplification
  1192  //   TestSimplifiedLoopSelfIntersects
  1193  //   TestNoSimplificationManyLoops
  1194  //   TestTinyLoopDisappears
  1195  //   TestStraightLinesAreSimplified
  1196  //   TestEdgeSplitInManyPieces
  1197  //   TestEdgesOverlap
  1198  //   TestLargeRegularPolygon
  1199  //
  1200  // InitToSimplifiedInCell
  1201  //   TestPointsOnCellBoundaryKept
  1202  //   TestPointsInsideCellSimplified
  1203  //   TestCellCornerKept
  1204  //   TestNarrowStripRemoved
  1205  //   TestNarrowGapRemoved
  1206  //   TestCloselySpacedEdgeVerticesKept
  1207  //   TestPolylineAssemblyBug
  1208  

View as plain text