func (p *Polygon) ContainsCell(cell Cell) bool {
	it := p.index.Iterator()
	relation := it.LocateCellID(cell.ID())
	if relation != Indexed {
		return false
	}
	if p.boundaryApproxIntersects(it, cell) {
		return false
	}
	return p.iteratorContainsPoint(it, cell.Center())
}
ContainsCell reports whether the polygon contains the given cell.
package s2
import (
	"fmt"
	"io"
	"math"
)
type Polygon struct {
	loops []*Loop
	index *ShapeIndex
	hasHoles bool
	numVertices int
	numEdges int
	bound Rect
	subregionBound Rect
	cumulativeEdges []int
}
func PolygonFromLoops(loops []*Loop) *Polygon {
	p := &Polygon{}
	if len(loops) == 1 && loops[0].IsEmpty() {
		p.initLoopProperties()
		return p
	}
	p.loops = loops
	p.initNested()
	return p
}
func PolygonFromOrientedLoops(loops []*Loop) *Polygon {
	containedOrigin := make(map[*Loop]bool)
	for _, l := range loops {
		containedOrigin[l] = l.ContainsOrigin()
	}
	for _, l := range loops {
		angle := l.TurningAngle()
		if math.Abs(angle) > l.turningAngleMaxError() {
			if angle < 0 {
				l.Invert()
			}
		} else {
			if l.ContainsOrigin() {
				l.Invert()
			}
		}
	}
	p := PolygonFromLoops(loops)
	if p.NumLoops() > 0 {
		originLoop := p.Loop(0)
		polygonContainsOrigin := false
		for _, l := range p.Loops() {
			if l.ContainsOrigin() {
				polygonContainsOrigin = !polygonContainsOrigin
				originLoop = l
			}
		}
		if containedOrigin[originLoop] != polygonContainsOrigin {
			p.Invert()
		}
	}
	return p
}
func (p *Polygon) Invert() {
	if p.IsEmpty() {
		*p = *FullPolygon()
		p.initLoopProperties()
		return
	}
	if p.IsFull() {
		*p = Polygon{}
		p.initLoopProperties()
		return
	}
	best := 0
	const none = 10.0  
	bestAngle := none
	for i := 1; i < p.NumLoops(); i++ {
		if p.Loop(i).depth != 0 {
			continue
		}
		if bestAngle == none {
			bestAngle = p.Loop(best).TurningAngle()
		}
		angle := p.Loop(i).TurningAngle()
		if angle < bestAngle || (angle == bestAngle && compareLoops(p.Loop(i), p.Loop(best)) < 0) {
			best = i
			bestAngle = angle
		}
	}
	p.Loop(best).Invert()
	newLoops := make([]*Loop, 0, p.NumLoops())
	lastBest := p.LastDescendant(best)
	newLoops = append(newLoops, p.Loop(best))
	for i, l := range p.Loops() {
		if i < best || i > lastBest {
			l.depth++
			newLoops = append(newLoops, l)
		}
	}
	for i, l := range p.Loops() {
		if i > best && i <= lastBest {
			l.depth--
			newLoops = append(newLoops, l)
		}
	}
	p.loops = newLoops
	p.initLoopProperties()
}
func compareLoops(a, b *Loop) int {
	if na, nb := a.NumVertices(), b.NumVertices(); na != nb {
		return na - nb
	}
	ai, aDir := a.CanonicalFirstVertex()
	bi, bDir := b.CanonicalFirstVertex()
	if aDir != bDir {
		return aDir - bDir
	}
	for n := a.NumVertices() - 1; n >= 0; n, ai, bi = n-1, ai+aDir, bi+bDir {
		if cmp := a.Vertex(ai).Cmp(b.Vertex(bi).Vector); cmp != 0 {
			return cmp
		}
	}
	return 0
}
func PolygonFromCell(cell Cell) *Polygon {
	return PolygonFromLoops([]*Loop{LoopFromCell(cell)})
}
func (p *Polygon) initNested() {
	if len(p.loops) == 1 {
		p.initOneLoop()
		return
	}
	lm := make(loopMap)
	for _, l := range p.loops {
		lm.insertLoop(l, nil)
	}
	p.loops = nil
	p.initLoops(lm)
	p.initLoopProperties()
}
type loopMap map[*Loop][]*Loop
func (lm loopMap) insertLoop(newLoop, parent *Loop) {
	var children []*Loop
	for done := false; !done; {
		children = lm[parent]
		done = true
		for _, child := range children {
			if child.ContainsNested(newLoop) {
				parent = child
				done = false
				break
			}
		}
	}
	newChildren := lm[newLoop]
	for i := 0; i < len(children); {
		child := children[i]
		if newLoop.ContainsNested(child) {
			newChildren = append(newChildren, child)
			children = append(children[0:i], children[i+1:]...)
		} else {
			i++
		}
	}
	lm[newLoop] = newChildren
	lm[parent] = append(children, newLoop)
}
type loopStack []*Loop
func (s *loopStack) push(v *Loop) {
	*s = append(*s, v)
}
func (s *loopStack) pop() *Loop {
	l := len(*s)
	r := (*s)[l-1]
	*s = (*s)[:l-1]
	return r
}
func (p *Polygon) initLoops(lm loopMap) {
	var stack loopStack
	stack.push(nil)
	depth := -1
	for len(stack) > 0 {
		loop := stack.pop()
		if loop != nil {
			depth = loop.depth
			p.loops = append(p.loops, loop)
		}
		children := lm[loop]
		for i := len(children) - 1; i >= 0; i-- {
			child := children[i]
			child.depth = depth + 1
			stack.push(child)
		}
	}
}
func (p *Polygon) initOneLoop() {
	p.hasHoles = false
	p.numVertices = len(p.loops[0].vertices)
	p.bound = p.loops[0].RectBound()
	p.subregionBound = ExpandForSubregions(p.bound)
	p.loops[0].depth = 0
	p.initEdgesAndIndex()
}
func (p *Polygon) initLoopProperties() {
	p.numVertices = 0
	p.bound = EmptyRect()
	p.hasHoles = false
	for _, l := range p.loops {
		if l.IsHole() {
			p.hasHoles = true
		} else {
			p.bound = p.bound.Union(l.RectBound())
		}
		p.numVertices += l.NumVertices()
	}
	p.subregionBound = ExpandForSubregions(p.bound)
	p.initEdgesAndIndex()
}
func (p *Polygon) initEdgesAndIndex() {
	p.numEdges = 0
	p.cumulativeEdges = nil
	if p.IsFull() {
		return
	}
	const maxLinearSearchLoops = 12  
	if len(p.loops) > maxLinearSearchLoops {
		p.cumulativeEdges = make([]int, 0, len(p.loops))
	}
	for _, l := range p.loops {
		if p.cumulativeEdges != nil {
			p.cumulativeEdges = append(p.cumulativeEdges, p.numEdges)
		}
		p.numEdges += len(l.vertices)
	}
	p.index = NewShapeIndex()
	p.index.Add(p)
}
func FullPolygon() *Polygon {
	ret := &Polygon{
		loops: []*Loop{
			FullLoop(),
		},
		numVertices:    len(FullLoop().Vertices()),
		bound:          FullRect(),
		subregionBound: FullRect(),
	}
	ret.initEdgesAndIndex()
	return ret
}
func (p *Polygon) Validate() error {
	for i, l := range p.loops {
		if err := l.findValidationErrorNoIndex(); err != nil {
			return fmt.Errorf("loop %d: %v", i, err)
		}
		if l.IsEmpty() {
			return fmt.Errorf("loop %d: empty loops are not allowed", i)
		}
		if l.IsFull() && len(p.loops) > 1 {
			return fmt.Errorf("loop %d: full loop appears in non-full polygon", i)
		}
	}
	return p.findLoopNestingError()
}
func (p *Polygon) findLoopNestingError() error {
	lastDepth := -1
	for i, l := range p.loops {
		depth := l.depth
		if depth < 0 || depth > lastDepth+1 {
			return fmt.Errorf("loop %d: invalid loop depth (%d)", i, depth)
		}
		lastDepth = depth
	}
	for i, l := range p.loops {
		last := p.LastDescendant(i)
		for j, l2 := range p.loops {
			if i == j {
				continue
			}
			nested := (j >= i+1) && (j <= last)
			const reverseB = false
			if l.containsNonCrossingBoundary(l2, reverseB) != nested {
				nestedStr := ""
				if !nested {
					nestedStr = "not "
				}
				return fmt.Errorf("invalid nesting: loop %d should %scontain loop %d", i, nestedStr, j)
			}
		}
	}
	return nil
}
func (p *Polygon) IsEmpty() bool {
	return len(p.loops) == 0
}
func (p *Polygon) IsFull() bool {
	return len(p.loops) == 1 && p.loops[0].IsFull()
}
func (p *Polygon) NumLoops() int {
	return len(p.loops)
}
func (p *Polygon) Loops() []*Loop {
	return p.loops
}
func (p *Polygon) Loop(k int) *Loop {
	return p.loops[k]
}
func (p *Polygon) Parent(k int) (index int, ok bool) {
	depth := p.loops[k].depth
	if depth == 0 {
		return -1, false
	}
	for k--; k >= 0 && p.loops[k].depth <= depth; k-- {
	}
	return k, true
}
func (p *Polygon) LastDescendant(k int) int {
	if k < 0 {
		return len(p.loops) - 1
	}
	depth := p.loops[k].depth
	for k++; k < len(p.loops) && p.loops[k].depth > depth; k++ {
	}
	return k - 1
}
func (p *Polygon) CapBound() Cap { return p.bound.CapBound() }
func (p *Polygon) RectBound() Rect { return p.bound }
func (p *Polygon) ContainsPoint(point Point) bool {
	if !p.index.IsFresh() && !p.bound.ContainsPoint(point) {
		return false
	}
	const maxBruteForceVertices = 32
	if p.numVertices < maxBruteForceVertices || p.index == nil {
		inside := false
		for _, l := range p.loops {
			inside = inside != l.bruteForceContainsPoint(point)
		}
		return inside
	}
	return NewContainsPointQuery(p.index, VertexModelSemiOpen).Contains(point)
}