func TestPolygonParent(t *testing.T) {
	p1 := PolygonFromLoops([]*Loop{{}})
	tests := []struct {
		p    *Polygon
		have int
		want int
		ok   bool
	}{
		{fullPolygon, 0, -1, false},
		{p1, 0, -1, false},
	}
	for _, test := range tests {
		if got, ok := test.p.Parent(test.have); ok != test.ok || got != test.want {
			t.Errorf("%v.Parent(%d) = %d,%v, want %d,%v", test.p, test.have, got, ok, test.want, test.ok)
		}
	}
}
TODO(roberts): Implement remaining validity tests.
IsValidTests
TestUnitLength
TestVertexCount
TestDuplicateVertex
TestSelfIntersection
TestEmptyLoop
TestFullLoop
TestLoopsCrossing
TestDuplicateEdge
TestInconsistentOrientations
TestLoopDepthNegative
TestLoopNestingInvalid
TestFuzzTest
package s2
import (
	"math"
	"math/rand"
	"testing"
	"github.com/golang/geo/s1"
)
const (
	nearPoint    = "0:0"
	nearLoop0    = "-1:0, 0:1, 1:0, 0:-1;"
	nearLoop1    = "-1:-1, -1:0, -1:1, 0:1, 1:1, 1:0, 1:-1, 0:-1;"
	nearLoop2    = "-1:-2, -2:5, 5:-2;"
	nearLoop3    = "-2:-2, -3:6, 6:-3;"
	nearLoopHemi = "0:-90, -90:0, 0:90, 90:0;"
	farPoint    = "0:180"
	farLoop0    = "0:179, 1:180, 0:-179, 2:-180;"
	farLoop1    = "0:179, -1:179, 1:180, -1:-179, 0:-179, 3:-178, 2:-180, 3:178;"
	farLoop2    = "3:-178, 3:178, -1:179, -1:-179;"
	farLoop3    = "-3:-178, 4:-177, 4:177, -3:178, -2:179;"
	farLoopHemi = "0:-90, 60:90, -60:90;"
	southLoopPoint = "-89.9999:0.001"
	southLoop0a    = "-90:0, -89.99:0.01, -89.99:0;"
	southLoop0b    = "-90:0, -89.99:0.03, -89.99:0.02;"
	southLoop0c    = "-90:0, -89.99:0.05, -89.99:0.04;"
	southLoop1     = "-90:0, -89.9:0.1, -89.9:-0.1;"
	southLoop2     = "-90:0, -89.8:0.2, -89.8:-0.2;"
	southLoopHemi  = "0:-180, 0:60, 0:-60;"
	nearFarLoop1 = "-1:-9, -9:-9, -9:9, 9:9, 9:-9, 1:-9, " +
		"1:-175, 9:-175, 9:175, -9:175, -9:-175, -1:-175;"
	nearFarLoop2 = "-2:15, -2:170, -8:-175, 8:-175, " +
		"2:170, 2:15, 8:-4, -8:-4;"
	farHemiSouthHemiLoop = "0:-180, 0:90, -60:90, 0:-90;"
	loopCross1          = "-2:1, -1:1, 1:1, 2:1, 2:-1, 1:-1, -1:-1, -2:-1;"
	loopCross1SideHole  = "-1.5:0.5, -1.2:0.5, -1.2:-0.5, -1.5:-0.5;"
	loopCrossCenterHole = "-0.5:0.5, 0.5:0.5, 0.5:-0.5, -0.5:-0.5;"
	loopCross2SideHole  = "0.5:-1.5, 0.5:-1.2, -0.5:-1.2, -0.5:-1.5;"
	loopCross2          = "1:-2, 1:-1, 1:1, 1:2, -1:2, -1:1, -1:-1, -1:-2;"
	loopOverlap1          = "0:1, 1:1, 2:1, 2:0, 1:0, 0:0;"
	loopOverlap1SideHole  = "0.2:0.8, 0.8:0.8, 0.8:0.2, 0.2:0.2;"
	loopOverlapCenterHole = "1.2:0.8, 1.8:0.8, 1.8:0.2, 1.2:0.2;"
	loopOverlap2SideHole  = "2.2:0.8, 2.8:0.8, 2.8:0.2, 2.2:0.2;"
	loopOverlap2          = "1:1, 2:1, 3:1, 3:0, 2:0, 1:0;"
	loopOverlap3 = "-10:10, 0:10, 0:-10, -10:-10, -10:0"
	loopOverlap4 = "-10:0, 10:0, 10:-10, -10:-10"
)
var (
	emptyPolygon = &Polygon{}
	fullPolygon  = FullPolygon()
	near0Polygon     = makePolygon(nearLoop0, true)
	near01Polygon    = makePolygon(nearLoop0+nearLoop1, true)
	near30Polygon    = makePolygon(nearLoop3+nearLoop0, true)
	near23Polygon    = makePolygon(nearLoop2+nearLoop3, true)
	near0231Polygon  = makePolygon(nearLoop0+nearLoop2+nearLoop3+nearLoop1, true)
	near023H1Polygon = makePolygon(nearLoop0+nearLoop2+nearLoop3+nearLoopHemi+nearLoop1, true)
	far01Polygon    = makePolygon(farLoop0+farLoop1, true)
	far21Polygon    = makePolygon(farLoop2+farLoop1, true)
	far231Polygon   = makePolygon(farLoop2+farLoop3+farLoop1, true)
	far2H0Polygon   = makePolygon(farLoop2+farLoopHemi+farLoop0, true)
	far2H013Polygon = makePolygon(farLoop2+farLoopHemi+farLoop0+farLoop1+farLoop3, true)
	south0abPolygon     = makePolygon(southLoop0a+southLoop0b, true)
	south2Polygon       = makePolygon(southLoop2, true)
	south20b1Polygon    = makePolygon(southLoop2+southLoop0b+southLoop1, true)
	south2H1Polygon     = makePolygon(southLoop2+southLoopHemi+southLoop1, true)
	south20bH0acPolygon = makePolygon(southLoop2+southLoop0b+southLoopHemi+
		southLoop0a+southLoop0c, true)
	nf1N10F2S10abcPolygon = makePolygon(southLoop0c+farLoop2+nearLoop1+
		nearFarLoop1+nearLoop0+southLoop1+southLoop0b+southLoop0a, true)
	nf2N2F210S210abPolygon = makePolygon(farLoop2+southLoop0a+farLoop1+
		southLoop1+farLoop0+southLoop0b+nearFarLoop2+southLoop2+nearLoop2, true)
	f32n0Polygon  = makePolygon(farLoop2+nearLoop0+farLoop3, true)
	n32s0bPolygon = makePolygon(nearLoop3+southLoop0b+nearLoop2, true)
	cross1Polygon           = makePolygon(loopCross1, true)
	cross1SideHolePolygon   = makePolygon(loopCross1+loopCross1SideHole, true)
	cross1CenterHolePolygon = makePolygon(loopCross1+loopCrossCenterHole, true)
	cross2Polygon           = makePolygon(loopCross2, true)
	cross2SideHolePolygon   = makePolygon(loopCross2+loopCross2SideHole, true)
	cross2CenterHolePolygon = makePolygon(loopCross2+loopCrossCenterHole, true)
	overlap1Polygon           = makePolygon(loopOverlap1, true)
	overlap1SideHolePolygon   = makePolygon(loopOverlap1+loopOverlap1SideHole, true)
	overlap1CenterHolePolygon = makePolygon(loopOverlap1+loopOverlapCenterHole, true)
	overlap2Polygon           = makePolygon(loopOverlap2, true)
	overlap2SideHolePolygon   = makePolygon(loopOverlap2+loopOverlap2SideHole, true)
	overlap2CenterHolePolygon = makePolygon(loopOverlap2+loopOverlapCenterHole, true)
	overlap3Polygon = makePolygon(loopOverlap3, true)
	overlap4Polygon = makePolygon(loopOverlap4, true)
	farHemiPolygon      = makePolygon(farLoopHemi, true)
	southHemiPolygon    = makePolygon(southLoopHemi, true)
	farSouthHemiPolygon = makePolygon(farHemiSouthHemiLoop, true)
)
func TestPolygonInitSingleLoop(t *testing.T) {
	if !PolygonFromLoops([]*Loop{EmptyLoop()}).IsEmpty() {
		t.Errorf("polygon from Empty Loop should make an EmptyPolygon")
	}
	if !PolygonFromLoops([]*Loop{FullLoop()}).IsFull() {
		t.Errorf("polygon from Full Loop should make a FullPolygon")
	}
	p := PolygonFromLoops([]*Loop{makeLoop("0:0, 0:10, 10:0")})
	if got, want := p.numVertices, 3; got != want {
		t.Errorf("%v.numVertices = %v, want %v", p, got, want)
	}
}
func TestPolygonEmpty(t *testing.T) {
	shape := emptyPolygon
	if got, want := shape.NumEdges(), 0; got != want {
		t.Errorf("shape.NumEdges() = %v, want %v", got, want)
	}
	if got, want := shape.NumChains(), 0; got != want {
		t.Errorf("shape.NumChains() = %v, want %v", got, want)
	}
	if got, want := shape.Dimension(), 2; got != want {
		t.Errorf("shape.Dimension() = %v, want %v", got, want)
	}
	if !shape.IsEmpty() {
		t.Errorf("shape.IsEmpty() = false, want true")
	}
	if shape.IsFull() {
		t.Errorf("shape.IsFull() = true, want false")
	}
	if shape.ReferencePoint().Contained {
		t.Errorf("shape.ReferencePoint().Contained = true, want false")
	}
}
func TestPolygonFull(t *testing.T) {
	shape := fullPolygon
	if got, want := shape.NumEdges(), 0; got != want {
		t.Errorf("shape.NumEdges() = %v, want %v", got, want)
	}
	if got, want := shape.NumChains(), 1; got != want {
		t.Errorf("shape.NumChains() = %v, want %v", got, want)
	}
	if got, want := shape.Chain(0).Start, 0; got != want {
		t.Errorf("fullPolygon.Chain(0).Start = %d, want %d", got, want)
	}
	if got, want := shape.Chain(0).Length, 0; got != want {
		t.Errorf("fullPolygon.Chain(0).Length = %d, want %d", got, want)
	}
	if got, want := shape.Dimension(), 2; got != want {
		t.Errorf("shape.Dimension() = %v, want %v", got, want)
	}
	if shape.IsEmpty() {
		t.Errorf("shape.IsEmpty() = true, want false")
	}
	if !shape.IsFull() {
		t.Errorf("shape.IsFull() = false, want true")
	}
	if !shape.ReferencePoint().Contained {
		t.Errorf("shape.ReferencePoint().Contained = false, want true")
	}
}
func TestPolygonInitLoopPropertiesGetsRightBounds(t *testing.T) {
	p := PolygonFromLoops([]*Loop{
		makeLoop("12.55:-70.05, 12.55:-70.02, 12.58:-70.02, 12.58:-70.05"),
		makeLoop("12.56:-70.04, 12.56:-70.03, 12.58:-70.03, 12.58:-70.04"),
	})
	want := rectFromDegrees(12.55, -70.05, 12.58, -70.02)
	if got := p.RectBound(); !rectsApproxEqual(got, want, 1e-6, 1e-6) {
		t.Errorf("%v.RectBound() = %v, want %v", p, got, want)
	}
}
func TestPolygonShape(t *testing.T) {
	const numLoops = 100
	const numVerticesPerLoop = 6
	concentric := concentricLoopsPolygon(PointFromCoords(1, 0, 0), numLoops, numVerticesPerLoop)
	tests := []struct {
		p *Polygon
	}{
		{near0Polygon},     
		{near0231Polygon},  
		{concentric},       
	}
	for _, test := range tests {
		shape := Shape(test.p)
		if got, want := shape.NumEdges(), test.p.numVertices; got != want {
			t.Errorf("the number of vertices in a polygon should equal the number of edges. got %v, want %v", got, want)
		}
		if got, want := shape.NumChains(), test.p.NumLoops(); got != want {
			t.Errorf("the number of loops in a polygon should equal the number of chains. got %v, want %v", got, want)
		}
		edgeID := 0
		for i, l := range test.p.loops {
			if edgeID != shape.Chain(i).Start {
				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)
			}
			if len(l.vertices) != shape.Chain(i).Length {
				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))
			}
			for j := 0; j < len(l.Vertices()); j++ {
				edge := shape.Edge(edgeID)
				if l.OrientedVertex(j) != edge.V0 {
					t.Errorf("l.Vertex(%d) = %v, want %v", j, l.Vertex(j), edge.V0)
				}
				if l.OrientedVertex(j+1) != edge.V1 {
					t.Errorf("l.Vertex(%d) = %v, want %v", j+1, l.Vertex(j+1), edge.V1)
				}
				edgeID++
			}
		}
		if got, want := shape.Dimension(), 2; got != want {
			t.Errorf("shape.Dimension() = %v, want %v", got, want)
		}
		if shape.IsEmpty() {
			t.Errorf("shape.IsEmpty() = true, want false")
		}
		if shape.IsFull() {
			t.Errorf("shape.IsFull() = true, want false")
		}
		if got, want := test.p.ContainsPoint(OriginPoint()), shape.ReferencePoint().Contained; got != want {
			t.Errorf("p.ContainsPoint(OriginPoint()) != shape.ReferencePoint().Contained")
		}
	}
}
func reverseLoopVertices(l *Loop) {
	for i := 0; i < len(l.vertices)/2; i++ {
		l.vertices[i], l.vertices[len(l.vertices)-i-1] = l.vertices[len(l.vertices)-i-1], l.vertices[i]
	}
}
func shuffleLoops(loops []*Loop) {
	n := len(loops)
	for i := 0; i < n; i++ {
		r := i + rand.Intn(n-i)
		loops[r], loops[i] = loops[i], loops[r]
	}
}
type modifyPolygonFunc func(p *Polygon)
func polygonSetInvalidLoopNesting(p *Polygon) {
	if len(p.loops) > 0 {
		i := randomUniformInt(len(p.loops))
		p.loops[i].Invert()
	}
}
func polygonSetInvalidLoopDepth(p *Polygon) {
	i := randomUniformInt(len(p.loops))
	if i == 0 || oneIn(3) {
		p.loops[i].depth = -1
	} else {
		p.loops[i].depth = p.loops[i-1].depth + 2
	}
}
func generatePolygonConcentricTestLoops(numLoops, minVertices int) []*Loop {
	var loops []*Loop
	center := randomPoint()
	numVertices := minVertices + randomUniformInt(10)
	for i := 0; i < numLoops; i++ {
		radius := s1.Angle(80*math.Pow(0.1, float64(i))) * s1.Degree
		loops = append(loops, RegularLoop(center, radius, numVertices))
	}
	return loops
}
func checkPolygonInvalid(t *testing.T, label string, loops []*Loop, initOriented bool, f modifyPolygonFunc) {
	shuffleLoops(loops)
	var polygon *Polygon
	if initOriented {
		polygon = PolygonFromOrientedLoops(loops)
	} else {
		polygon = PolygonFromLoops(loops)
	}
	if f != nil {
		f(polygon)
	}
	if err := polygon.Validate(); err == nil {
		t.Errorf("%s: %v.Validate() = %v, want non-nil", label, polygon, err)
	}
}
func TestPolygonUninitializedIsValid(t *testing.T) {
	p := &Polygon{}
	if err := p.Validate(); err != nil {
		t.Errorf("an uninitialized polygon failed validation: %v", err)
	}
}
func TestPolygonIsValidLoopNestingInvalid(t *testing.T) {
	const iters = 1000
	for iter := 0; iter < iters; iter++ {
		loops := generatePolygonConcentricTestLoops(2+randomUniformInt(4), 3)
		if oneIn(2) {
			for _, loop := range loops {
				reverseLoopVertices(loop)
			}
		}
		checkPolygonInvalid(t, "invalid nesting", loops, false, polygonSetInvalidLoopNesting)
	}
}