func (s *ShapeIndex) Len() int {
	return len(s.shapes)
}
Len reports the number of Shapes in this index.
package s2
import (
	"math"
	"sort"
	"sync"
	"sync/atomic"
	"github.com/golang/geo/r1"
	"github.com/golang/geo/r2"
)
type CellRelation int
const (
	Indexed CellRelation = iota
	Subdivided
	Disjoint
)
const (
	cellPadding = 2.0 * (faceClipErrorUVCoord + edgeClipErrorUVCoord)
	cellSizeToLongEdgeRatio = 1.0
)
type clippedShape struct {
	shapeID int32
	containsCenter bool
	edges []int
}
func newClippedShape(id int32, numEdges int) *clippedShape {
	return &clippedShape{
		shapeID: id,
		edges:   make([]int, numEdges),
	}
}
func (c *clippedShape) numEdges() int {
	return len(c.edges)
}
func (c *clippedShape) containsEdge(id int) bool {
	for _, e := range c.edges {
		if e == id {
			return true
		}
	}
	return false
}
type ShapeIndexCell struct {
	shapes []*clippedShape
}
func NewShapeIndexCell(numShapes int) *ShapeIndexCell {
	return &ShapeIndexCell{
		shapes: make([]*clippedShape, numShapes),
	}
}
func (s *ShapeIndexCell) numEdges() int {
	var e int
	for _, cs := range s.shapes {
		e += cs.numEdges()
	}
	return e
}
func (s *ShapeIndexCell) add(c *clippedShape) {
	s.shapes = append(s.shapes, c)
}
func (s *ShapeIndexCell) findByShapeID(shapeID int32) *clippedShape {
	for _, clipped := range s.shapes {
		if clipped.shapeID == shapeID {
			return clipped
		}
	}
	return nil
}
type faceEdge struct {
	shapeID     int32     
	edgeID      int       
	maxLevel    int       
	hasInterior bool      
	a, b        r2.Point  
	edge        Edge      
}
type clippedEdge struct {
	faceEdge *faceEdge  
	bound    r2.Rect    
}
type ShapeIndexIteratorPos int
const (
	IteratorBegin ShapeIndexIteratorPos = iota
	IteratorEnd
)
type ShapeIndexIterator struct {
	index    *ShapeIndex
	position int
	id       CellID
	cell     *ShapeIndexCell
}
func NewShapeIndexIterator(index *ShapeIndex, pos ...ShapeIndexIteratorPos) *ShapeIndexIterator {
	s := &ShapeIndexIterator{
		index: index,
	}
	if len(pos) > 0 {
		if len(pos) > 1 {
			panic("too many ShapeIndexIteratorPos arguments")
		}
		switch pos[0] {
		case IteratorBegin:
			s.Begin()
		case IteratorEnd:
			s.End()
		default:
			panic("unknown ShapeIndexIteratorPos value")
		}
	}
	return s
}
func (s *ShapeIndexIterator) clone() *ShapeIndexIterator {
	return &ShapeIndexIterator{
		index:    s.index,
		position: s.position,
		id:       s.id,
		cell:     s.cell,
	}
}
func (s *ShapeIndexIterator) CellID() CellID {
	return s.id
}
func (s *ShapeIndexIterator) IndexCell() *ShapeIndexCell {
	return s.cell
}
func (s *ShapeIndexIterator) Center() Point {
	return s.CellID().Point()
}
func (s *ShapeIndexIterator) Begin() {
	if !s.index.IsFresh() {
		s.index.maybeApplyUpdates()
	}
	s.position = 0
	s.refresh()
}
func (s *ShapeIndexIterator) Next() {
	s.position++
	s.refresh()
}
func (s *ShapeIndexIterator) Prev() bool {
	if s.position <= 0 {
		return false
	}
	s.position--
	s.refresh()
	return true
}
func (s *ShapeIndexIterator) End() {
	s.position = len(s.index.cells)
	s.refresh()
}
func (s *ShapeIndexIterator) Done() bool {
	return s.id == SentinelCellID
}
func (s *ShapeIndexIterator) refresh() {
	if s.position < len(s.index.cells) {
		s.id = s.index.cells[s.position]
		s.cell = s.index.cellMap[s.CellID()]
	} else {
		s.id = SentinelCellID
		s.cell = nil
	}
}
func (s *ShapeIndexIterator) seek(target CellID) {
	s.position = sort.Search(len(s.index.cells), func(i int) bool {
		return s.index.cells[i] >= target
	})
	s.refresh()
}
func (s *ShapeIndexIterator) LocatePoint(p Point) bool {
	target := cellIDFromPoint(p)
	s.seek(target)
	if !s.Done() && s.CellID().RangeMin() <= target {
		return true
	}
	if s.Prev() && s.CellID().RangeMax() >= target {
		return true
	}
	return false
}
func (s *ShapeIndexIterator) LocateCellID(target CellID) CellRelation {
	s.seek(target.RangeMin())
	if !s.Done() {
		if s.CellID() >= target && s.CellID().RangeMin() <= target {
			return Indexed
		}
		if s.CellID() <= target.RangeMax() {
			return Subdivided
		}
	}
	if s.Prev() && s.CellID().RangeMax() >= target {
		return Indexed
	}
	return Disjoint
}
type tracker struct {
	isActive   bool
	a          Point
	b          Point
	nextCellID CellID
	crosser    *EdgeCrosser
	shapeIDs   []int32
	savedIDs []int32
}
func newTracker() *tracker {
	t := &tracker{
		isActive:   false,
		b:          trackerOrigin(),
		nextCellID: CellIDFromFace(0).ChildBeginAtLevel(maxLevel),
	}
	t.drawTo(Point{faceUVToXYZ(0, -1, -1).Normalize()})  
	return t
}
func trackerOrigin() Point {
	return Point{faceUVToXYZ(0, -1, -1).Normalize()}
}
func (t *tracker) focus() Point { return t.b }
func (t *tracker) addShape(shapeID int32, containsFocus bool) {
	t.isActive = true
	if containsFocus {
		t.toggleShape(shapeID)
	}
}
func (t *tracker) moveTo(b Point) { t.b = b }
func (t *tracker) drawTo(b Point) {
	t.a = t.b
	t.b = b
	t.crosser = NewEdgeCrosser(t.a, t.b)
}
func (t *tracker) testEdge(shapeID int32, edge Edge) {
	if t.crosser.EdgeOrVertexCrossing(edge.V0, edge.V1) {
		t.toggleShape(shapeID)
	}
}
func (t *tracker) setNextCellID(nextCellID CellID) {
	t.nextCellID = nextCellID.RangeMin()
}
func (t *tracker) atCellID(cellid CellID) bool {
	return cellid.RangeMin() == t.nextCellID
}
func (t *tracker) toggleShape(shapeID int32) {
	if len(t.shapeIDs) == 0 {
		t.shapeIDs = append(t.shapeIDs, shapeID)
		return
	}
	if t.shapeIDs[0] == shapeID {
		t.shapeIDs = t.shapeIDs[1:]
		return
	}
	for i, s := range t.shapeIDs {
		if s < shapeID {
			continue
		}
		if s == shapeID {
			copy(t.shapeIDs[i:], t.shapeIDs[i+1:])  
			t.shapeIDs = t.shapeIDs[:len(t.shapeIDs)-1]
			return
		}
		t.shapeIDs = append(t.shapeIDs[0:i],
			append([]int32{shapeID}, t.shapeIDs[i:len(t.shapeIDs)]...)...)
		return
	}
	t.shapeIDs = append(t.shapeIDs, shapeID)
}
func (t *tracker) saveAndClearStateBefore(limitShapeID int32) {
	limit := t.lowerBound(limitShapeID)
	t.savedIDs = append([]int32(nil), t.shapeIDs[:limit]...)
	t.shapeIDs = t.shapeIDs[limit:]
}
func (t *tracker) restoreStateBefore(limitShapeID int32) {
	limit := t.lowerBound(limitShapeID)
	t.shapeIDs = append(append([]int32(nil), t.savedIDs...), t.shapeIDs[limit:]...)
	t.savedIDs = nil
}
func (t *tracker) lowerBound(shapeID int32) int32 {
	panic("not implemented")
}
type removedShape struct {
	shapeID               int32
	hasInterior           bool
	containsTrackerOrigin bool
	edges                 []Edge
}
const (
	stale    int32 = iota  
	updating               
	fresh                  
)
type ShapeIndex struct {
	shapes map[int32]Shape
	maxEdgesPerCell int
	nextID int32
	cellMap map[CellID]*ShapeIndexCell
	cells []CellID
	status int32
	mu sync.RWMutex
	pendingAdditionsPos int32
	pendingRemovals []*removedShape
}
func NewShapeIndex() *ShapeIndex {
	return &ShapeIndex{
		maxEdgesPerCell: 10,
		shapes:          make(map[int32]Shape),
		cellMap:         make(map[CellID]*ShapeIndexCell),
		cells:           nil,
		status:          fresh,
	}
}
func (s *ShapeIndex) Iterator() *ShapeIndexIterator {
	s.maybeApplyUpdates()
	return NewShapeIndexIterator(s, IteratorBegin)
}
func (s *ShapeIndex) Begin() *ShapeIndexIterator {
	s.maybeApplyUpdates()
	return NewShapeIndexIterator(s, IteratorBegin)
}
func (s *ShapeIndex) End() *ShapeIndexIterator {
	s.maybeApplyUpdates()
	return NewShapeIndexIterator(s, IteratorEnd)
}