[chore] add back exif-terminator and use only for jpeg,png,webp (#3161)

* add back exif-terminator and use only for jpeg,png,webp

* fix arguments passed to terminateExif()

* pull in latest exif-terminator

* fix test

* update processed img

---------

Co-authored-by: tobi <tobi.smethurst@protonmail.com>

1 files changed, 1507 insertions, 0 deletions

diff --git a/vendor/github.com/golang/geo/s2/shapeindex.go b/vendor/github.com/golang/geo/s2/shapeindex.go
new file mode 100644
index 000000000..8da299d06
--- /dev/null
+++ b/vendor/github.com/golang/geo/s2/shapeindex.go
@@ -0,0 +1,1507 @@
+// Copyright 2016 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.
+
+package s2
+
+import (
+	"math"
+	"sort"
+	"sync"
+	"sync/atomic"
+
+	"github.com/golang/geo/r1"
+	"github.com/golang/geo/r2"
+)
+
+// CellRelation describes the possible relationships between a target cell
+// and the cells of the ShapeIndex. If the target is an index cell or is
+// contained by an index cell, it is Indexed. If the target is subdivided
+// into one or more index cells, it is Subdivided. Otherwise it is Disjoint.
+type CellRelation int
+
+// The possible CellRelations for a ShapeIndex.
+const (
+	Indexed CellRelation = iota
+	Subdivided
+	Disjoint
+)
+
+const (
+	// cellPadding defines the total error when clipping an edge which comes
+	// from two sources:
+	// (1) Clipping the original spherical edge to a cube face (the face edge).
+	//     The maximum error in this step is faceClipErrorUVCoord.
+	// (2) Clipping the face edge to the u- or v-coordinate of a cell boundary.
+	//     The maximum error in this step is edgeClipErrorUVCoord.
+	// Finally, since we encounter the same errors when clipping query edges, we
+	// double the total error so that we only need to pad edges during indexing
+	// and not at query time.
+	cellPadding = 2.0 * (faceClipErrorUVCoord + edgeClipErrorUVCoord)
+
+	// cellSizeToLongEdgeRatio defines the cell size relative to the length of an
+	// edge at which it is first considered to be long. Long edges do not
+	// contribute toward the decision to subdivide a cell further. For example,
+	// a value of 2.0 means that the cell must be at least twice the size of the
+	// edge in order for that edge to be counted. There are two reasons for not
+	// counting long edges: (1) such edges typically need to be propagated to
+	// several children, which increases time and memory costs without much benefit,
+	// and (2) in pathological cases, many long edges close together could force
+	// subdivision to continue all the way to the leaf cell level.
+	cellSizeToLongEdgeRatio = 1.0
+)
+
+// clippedShape represents the part of a shape that intersects a Cell.
+// It consists of the set of edge IDs that intersect that cell and a boolean
+// indicating whether the center of the cell is inside the shape (for shapes
+// that have an interior).
+//
+// Note that the edges themselves are not clipped; we always use the original
+// edges for intersection tests so that the results will be the same as the
+// original shape.
+type clippedShape struct {
+	// shapeID is the index of the shape this clipped shape is a part of.
+	shapeID int32
+
+	// containsCenter indicates if the center of the CellID this shape has been
+	// clipped to falls inside this shape. This is false for shapes that do not
+	// have an interior.
+	containsCenter bool
+
+	// edges is the ordered set of ShapeIndex original edge IDs. Edges
+	// are stored in increasing order of edge ID.
+	edges []int
+}
+
+// newClippedShape returns a new clipped shape for the given shapeID and number of expected edges.
+func newClippedShape(id int32, numEdges int) *clippedShape {
+	return &clippedShape{
+		shapeID: id,
+		edges:   make([]int, numEdges),
+	}
+}
+
+// numEdges returns the number of edges that intersect the CellID of the Cell this was clipped to.
+func (c *clippedShape) numEdges() int {
+	return len(c.edges)
+}
+
+// containsEdge reports if this clipped shape contains the given edge ID.
+func (c *clippedShape) containsEdge(id int) bool {
+	// Linear search is fast because the number of edges per shape is typically
+	// very small (less than 10).
+	for _, e := range c.edges {
+		if e == id {
+			return true
+		}
+	}
+	return false
+}
+
+// ShapeIndexCell stores the index contents for a particular CellID.
+type ShapeIndexCell struct {
+	shapes []*clippedShape
+}
+
+// NewShapeIndexCell creates a new cell that is sized to hold the given number of shapes.
+func NewShapeIndexCell(numShapes int) *ShapeIndexCell {
+	return &ShapeIndexCell{
+		shapes: make([]*clippedShape, numShapes),
+	}
+}
+
+// numEdges reports the total number of edges in all clipped shapes in this cell.
+func (s *ShapeIndexCell) numEdges() int {
+	var e int
+	for _, cs := range s.shapes {
+		e += cs.numEdges()
+	}
+	return e
+}
+
+// add adds the given clipped shape to this index cell.
+func (s *ShapeIndexCell) add(c *clippedShape) {
+	// C++ uses a set, so it's ordered and unique. We don't currently catch
+	// the case when a duplicate value is added.
+	s.shapes = append(s.shapes, c)
+}
+
+// findByShapeID returns the clipped shape that contains the given shapeID,
+// or nil if none of the clipped shapes contain it.
+func (s *ShapeIndexCell) findByShapeID(shapeID int32) *clippedShape {
+	// Linear search is fine because the number of shapes per cell is typically
+	// very small (most often 1), and is large only for pathological inputs
+	// (e.g. very deeply nested loops).
+	for _, clipped := range s.shapes {
+		if clipped.shapeID == shapeID {
+			return clipped
+		}
+	}
+	return nil
+}
+
+// faceEdge and clippedEdge store temporary edge data while the index is being
+// updated.
+//
+// While it would be possible to combine all the edge information into one
+// structure, there are two good reasons for separating it:
+//
+//  - Memory usage. Separating the two means that we only need to
+//    store one copy of the per-face data no matter how many times an edge is
+//    subdivided, and it also lets us delay computing bounding boxes until
+//    they are needed for processing each face (when the dataset spans
+//    multiple faces).
+//
+//  - Performance. UpdateEdges is significantly faster on large polygons when
+//    the data is separated, because it often only needs to access the data in
+//    clippedEdge and this data is cached more successfully.
+
+// faceEdge represents an edge that has been projected onto a given face,
+type faceEdge struct {
+	shapeID     int32    // The ID of shape that this edge belongs to
+	edgeID      int      // Edge ID within that shape
+	maxLevel    int      // Not desirable to subdivide this edge beyond this level
+	hasInterior bool     // Belongs to a shape that has a dimension of 2
+	a, b        r2.Point // The edge endpoints, clipped to a given face
+	edge        Edge     // The original edge.
+}
+
+// clippedEdge represents the portion of that edge that has been clipped to a given Cell.
+type clippedEdge struct {
+	faceEdge *faceEdge // The original unclipped edge
+	bound    r2.Rect   // Bounding box for the clipped portion
+}
+
+// ShapeIndexIteratorPos defines the set of possible iterator starting positions. By
+// default iterators are unpositioned, since this avoids an extra seek in this
+// situation where one of the seek methods (such as Locate) is immediately called.
+type ShapeIndexIteratorPos int
+
+const (
+	// IteratorBegin specifies the iterator should be positioned at the beginning of the index.
+	IteratorBegin ShapeIndexIteratorPos = iota
+	// IteratorEnd specifies the iterator should be positioned at the end of the index.
+	IteratorEnd
+)
+
+// ShapeIndexIterator is an iterator that provides low-level access to
+// the cells of the index. Cells are returned in increasing order of CellID.
+//
+//   for it := index.Iterator(); !it.Done(); it.Next() {
+//     fmt.Print(it.CellID())
+//   }
+//
+type ShapeIndexIterator struct {
+	index    *ShapeIndex
+	position int
+	id       CellID
+	cell     *ShapeIndexCell
+}
+
+// NewShapeIndexIterator creates a new iterator for the given index. If a starting
+// position is specified, the iterator is positioned at the given spot.
+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
+}
+
+// CellID returns the CellID of the current index cell.
+// If s.Done() is true, a value larger than any valid CellID is returned.
+func (s *ShapeIndexIterator) CellID() CellID {
+	return s.id
+}
+
+// IndexCell returns the current index cell.
+func (s *ShapeIndexIterator) IndexCell() *ShapeIndexCell {
+	// TODO(roberts): C++ has this call a virtual method to allow subclasses
+	// of ShapeIndexIterator to do other work before returning the cell. Do
+	// we need such a thing?
+	return s.cell
+}
+
+// Center returns the Point at the center of the current position of the iterator.
+func (s *ShapeIndexIterator) Center() Point {
+	return s.CellID().Point()
+}
+
+// Begin positions the iterator at the beginning of the index.
+func (s *ShapeIndexIterator) Begin() {
+	if !s.index.IsFresh() {
+		s.index.maybeApplyUpdates()
+	}
+	s.position = 0
+	s.refresh()
+}
+
+// Next positions the iterator at the next index cell.
+func (s *ShapeIndexIterator) Next() {
+	s.position++
+	s.refresh()
+}
+
+// Prev advances the iterator to the previous cell in the index and returns true to
+// indicate it was not yet at the beginning of the index. If the iterator is at the
+// first cell the call does nothing and returns false.
+func (s *ShapeIndexIterator) Prev() bool {
+	if s.position <= 0 {
+		return false
+	}
+
+	s.position--
+	s.refresh()
+	return true
+}
+
+// End positions the iterator at the end of the index.
+func (s *ShapeIndexIterator) End() {
+	s.position = len(s.index.cells)
+	s.refresh()
+}
+
+// Done reports if the iterator is positioned at or after the last index cell.
+func (s *ShapeIndexIterator) Done() bool {
+	return s.id == SentinelCellID
+}
+
+// refresh updates the stored internal iterator values.
+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
+	}
+}
+
+// seek positions the iterator at the first cell whose ID >= target, or at the
+// end of the index if no such cell exists.
+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()
+}
+
+// LocatePoint positions the iterator at the cell that contains the given Point.
+// If no such cell exists, the iterator position is unspecified, and false is returned.
+// The cell at the matched position is guaranteed to contain all edges that might
+// intersect the line segment between target and the cell's center.
+func (s *ShapeIndexIterator) LocatePoint(p Point) bool {
+	// Let I = cellMap.LowerBound(T), where T is the leaf cell containing
+	// point P. Then if T is contained by an index cell, then the
+	// containing cell is either I or I'. We test for containment by comparing
+	// the ranges of leaf cells spanned by T, I, and I'.
+	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
+}
+
+// LocateCellID attempts to position the iterator at the first matching index cell
+// in the index that has some relation to the given CellID. Let T be the target CellID.
+// If T is contained by (or equal to) some index cell I, then the iterator is positioned
+// at I and returns Indexed. Otherwise if T contains one or more (smaller) index cells,
+// then the iterator is positioned at the first such cell I and return Subdivided.
+// Otherwise Disjoint is returned and the iterator position is undefined.
+func (s *ShapeIndexIterator) LocateCellID(target CellID) CellRelation {
+	// Let T be the target, let I = cellMap.LowerBound(T.RangeMin()), and
+	// let I' be the predecessor of I. If T contains any index cells, then T
+	// contains I. Similarly, if T is contained by an index cell, then the
+	// containing cell is either I or I'. We test for containment by comparing
+	// the ranges of leaf cells spanned by T, I, and I'.
+	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
+}
+
+// tracker keeps track of which shapes in a given set contain a particular point
+// (the focus). It provides an efficient way to move the focus from one point
+// to another and incrementally update the set of shapes which contain it. We use
+// this to compute which shapes contain the center of every CellID in the index,
+// by advancing the focus from one cell center to the next.
+//
+// Initially the focus is at the start of the CellID space-filling curve. We then
+// visit all the cells that are being added to the ShapeIndex in increasing order
+// of CellID. For each cell, we draw two edges: one from the entry vertex to the
+// center, and another from the center to the exit vertex (where entry and exit
+// refer to the points where the space-filling curve enters and exits the cell).
+// By counting edge crossings we can incrementally compute which shapes contain
+// the cell center. Note that the same set of shapes will always contain the exit
+// point of one cell and the entry point of the next cell in the index, because
+// either (a) these two points are actually the same, or (b) the intervening
+// cells in CellID order are all empty, and therefore there are no edge crossings
+// if we follow this path from one cell to the other.
+//
+// In C++, this is S2ShapeIndex::InteriorTracker.
+type tracker struct {
+	isActive   bool
+	a          Point
+	b          Point
+	nextCellID CellID
+	crosser    *EdgeCrosser
+	shapeIDs   []int32
+
+	// Shape ids saved by saveAndClearStateBefore. The state is never saved
+	// recursively so we don't need to worry about maintaining a stack.
+	savedIDs []int32
+}
+
+// newTracker returns a new tracker with the appropriate defaults.
+func newTracker() *tracker {
+	// As shapes are added, we compute which ones contain the start of the
+	// CellID space-filling curve by drawing an edge from OriginPoint to this
+	// point and counting how many shape edges cross this edge.
+	t := &tracker{
+		isActive:   false,
+		b:          trackerOrigin(),
+		nextCellID: CellIDFromFace(0).ChildBeginAtLevel(maxLevel),
+	}
+	t.drawTo(Point{faceUVToXYZ(0, -1, -1).Normalize()}) // CellID curve start
+
+	return t
+}
+
+// trackerOrigin returns the initial focus point when the tracker is created
+// (corresponding to the start of the CellID space-filling curve).
+func trackerOrigin() Point {
+	// The start of the S2CellId space-filling curve.
+	return Point{faceUVToXYZ(0, -1, -1).Normalize()}
+}
+
+// focus returns the current focus point of the tracker.
+func (t *tracker) focus() Point { return t.b }
+
+// addShape adds a shape whose interior should be tracked. containsOrigin indicates
+// whether the current focus point is inside the shape. Alternatively, if
+// the focus point is in the process of being moved (via moveTo/drawTo), you
+// can also specify containsOrigin at the old focus point and call testEdge
+// for every edge of the shape that might cross the current drawTo line.
+// This updates the state to correspond to the new focus point.
+//
+// This requires shape.HasInterior
+func (t *tracker) addShape(shapeID int32, containsFocus bool) {
+	t.isActive = true
+	if containsFocus {
+		t.toggleShape(shapeID)
+	}
+}
+
+// moveTo moves the focus of the tracker to the given point. This method should
+// only be used when it is known that there are no edge crossings between the old
+// and new focus locations; otherwise use drawTo.
+func (t *tracker) moveTo(b Point) { t.b = b }
+
+// drawTo moves the focus of the tracker to the given point. After this method is
+// called, testEdge should be called with all edges that may cross the line
+// segment between the old and new focus locations.
+func (t *tracker) drawTo(b Point) {
+	t.a = t.b
+	t.b = b
+	// TODO: the edge crosser may need an in-place Init method if this gets expensive
+	t.crosser = NewEdgeCrosser(t.a, t.b)
+}
+
+// testEdge checks if the given edge crosses the current edge, and if so, then
+// toggle the state of the given shapeID.
+// This requires shape to have an interior.
+func (t *tracker) testEdge(shapeID int32, edge Edge) {
+	if t.crosser.EdgeOrVertexCrossing(edge.V0, edge.V1) {
+		t.toggleShape(shapeID)
+	}
+}
+
+// setNextCellID is used to indicate that the last argument to moveTo or drawTo
+// was the entry vertex of the given CellID, i.e. the tracker is positioned at the
+// start of this cell. By using this method together with atCellID, the caller
+// can avoid calling moveTo in cases where the exit vertex of the previous cell
+// is the same as the entry vertex of the current cell.
+func (t *tracker) setNextCellID(nextCellID CellID) {
+	t.nextCellID = nextCellID.RangeMin()
+}
+
+// atCellID reports if the focus is already at the entry vertex of the given
+// CellID (provided that the caller calls setNextCellID as each cell is processed).
+func (t *tracker) atCellID(cellid CellID) bool {
+	return cellid.RangeMin() == t.nextCellID
+}
+
+// toggleShape adds or removes the given shapeID from the set of IDs it is tracking.
+func (t *tracker) toggleShape(shapeID int32) {
+	// Most shapeIDs slices are small, so special case the common steps.
+
+	// If there is nothing here, add it.
+	if len(t.shapeIDs) == 0 {
+		t.shapeIDs = append(t.shapeIDs, shapeID)
+		return
+	}
+
+	// If it's the first element, drop it from the slice.
+	if t.shapeIDs[0] == shapeID {
+		t.shapeIDs = t.shapeIDs[1:]
+		return
+	}
+
+	for i, s := range t.shapeIDs {
+		if s < shapeID {
+			continue
+		}
+
+		// If it's in the set, cut it out.
+		if s == shapeID {
+			copy(t.shapeIDs[i:], t.shapeIDs[i+1:]) // overwrite the ith element
+			t.shapeIDs = t.shapeIDs[:len(t.shapeIDs)-1]
+			return
+		}
+
+		// We've got to a point in the slice where we should be inserted.
+		// (the given shapeID is now less than the current positions id.)
+		t.shapeIDs = append(t.shapeIDs[0:i],
+			append([]int32{shapeID}, t.shapeIDs[i:len(t.shapeIDs)]...)...)
+		return
+	}
+
+	// We got to the end and didn't find it, so add it to the list.
+	t.shapeIDs = append(t.shapeIDs, shapeID)
+}
+
+// saveAndClearStateBefore makes an internal copy of the state for shape ids below
+// the given limit, and then clear the state for those shapes. This is used during
+// incremental updates to track the state of added and removed shapes separately.
+func (t *tracker) saveAndClearStateBefore(limitShapeID int32) {
+	limit := t.lowerBound(limitShapeID)
+	t.savedIDs = append([]int32(nil), t.shapeIDs[:limit]...)
+	t.shapeIDs = t.shapeIDs[limit:]
+}
+
+// restoreStateBefore restores the state previously saved by saveAndClearStateBefore.
+// This only affects the state for shapeIDs below "limitShapeID".
+func (t *tracker) restoreStateBefore(limitShapeID int32) {
+	limit := t.lowerBound(limitShapeID)
+	t.shapeIDs = append(append([]int32(nil), t.savedIDs...), t.shapeIDs[limit:]...)
+	t.savedIDs = nil
+}
+
+// lowerBound returns the shapeID of the first entry x where x >= shapeID.
+func (t *tracker) lowerBound(shapeID int32) int32 {
+	panic("not implemented")
+}
+
+// removedShape represents a set of edges from the given shape that is queued for removal.
+type removedShape struct {
+	shapeID               int32
+	hasInterior           bool
+	containsTrackerOrigin bool
+	edges                 []Edge
+}
+
+// There are three basic states the index can be in.
+const (
+	stale    int32 = iota // There are pending updates.
+	updating              // Updates are currently being applied.
+	fresh                 // There are no pending updates.
+)
+
+// ShapeIndex indexes a set of Shapes, where a Shape is some collection of edges
+// that optionally defines an interior. It can be used to represent a set of
+// points, a set of polylines, or a set of polygons. For Shapes that have
+// interiors, the index makes it very fast to determine which Shape(s) contain
+// a given point or region.
+//
+// The index can be updated incrementally by adding or removing shapes. It is
+// designed to handle up to hundreds of millions of edges. All data structures
+// are designed to be small, so the index is compact; generally it is smaller
+// than the underlying data being indexed. The index is also fast to construct.
+//
+// Polygon, Loop, and Polyline implement Shape which allows these objects to
+// be indexed easily. You can find useful query methods in CrossingEdgeQuery
+// and ClosestEdgeQuery (Not yet implemented in Go).
+//
+// Example showing how to build an index of Polylines:
+//
+//   index := NewShapeIndex()
+//   for _, polyline := range polylines {
+//       index.Add(polyline);
+//   }
+//   // Now you can use a CrossingEdgeQuery or ClosestEdgeQuery here.
+//
+type ShapeIndex struct {
+	// shapes is a map of shape ID to shape.
+	shapes map[int32]Shape
+
+	// The maximum number of edges per cell.
+	// TODO(roberts): Update the comments when the usage of this is implemented.
+	maxEdgesPerCell int
+
+	// nextID tracks the next ID to hand out. IDs are not reused when shapes
+	// are removed from the index.
+	nextID int32
+
+	// cellMap is a map from CellID to the set of clipped shapes that intersect that
+	// cell. The cell IDs cover a set of non-overlapping regions on the sphere.
+	// In C++, this is a BTree, so the cells are ordered naturally by the data structure.
+	cellMap map[CellID]*ShapeIndexCell
+	// Track the ordered list of cell IDs.
+	cells []CellID
+
+	// The current status of the index; accessed atomically.
+	status int32
+
+	// Additions and removals are queued and processed on the first subsequent
+	// query. There are several reasons to do this:
+	//
+	//  - It is significantly more efficient to process updates in batches if
+	//    the amount of entities added grows.
+	//  - Often the index will never be queried, in which case we can save both
+	//    the time and memory required to build it. Examples:
+	//     + Loops that are created simply to pass to an Polygon. (We don't
+	//       need the Loop index, because Polygon builds its own index.)
+	//     + Applications that load a database of geometry and then query only
+	//       a small fraction of it.
+	//
+	// The main drawback is that we need to go to some extra work to ensure that
+	// some methods are still thread-safe. Note that the goal is *not* to
+	// make this thread-safe in general, but simply to hide the fact that
+	// we defer some of the indexing work until query time.
+	//
+	// This mutex protects all of following fields in the index.
+	mu sync.RWMutex
+
+	// pendingAdditionsPos is the index of the first entry that has not been processed
+	// via applyUpdatesInternal.
+	pendingAdditionsPos int32
+
+	// The set of shapes that have been queued for removal but not processed yet by
+	// applyUpdatesInternal.
+	pendingRemovals []*removedShape
+}
+
+// NewShapeIndex creates a new ShapeIndex.
+func NewShapeIndex() *ShapeIndex {
+	return &ShapeIndex{
+		maxEdgesPerCell: 10,
+		shapes:          make(map[int32]Shape),
+		cellMap:         make(map[CellID]*ShapeIndexCell),
+		cells:           nil,
+		status:          fresh,
+	}
+}
+
+// Iterator returns an iterator for this index.
+func (s *ShapeIndex) Iterator() *ShapeIndexIterator {
+	s.maybeApplyUpdates()
+	return NewShapeIndexIterator(s, IteratorBegin)
+}
+
+// Begin positions the iterator at the first cell in the index.
+func (s *ShapeIndex) Begin() *ShapeIndexIterator {
+	s.maybeApplyUpdates()
+	return NewShapeIndexIterator(s, IteratorBegin)
+}
+
+// End positions the iterator at the last cell in the index.
+func (s *ShapeIndex) End() *ShapeIndexIterator {
+	// TODO(roberts): It's possible that updates could happen to the index between
+	// the time this is called and the time the iterators position is used and this
+	// will be invalid or not the end. For now, things will be undefined if this
+	// happens. See about referencing the IsFresh to guard for this in the future.
+	s.maybeApplyUpdates()
+	return NewShapeIndexIterator(s, IteratorEnd)
+}
+
+// Len reports the number of Shapes in this index.
+func (s *ShapeIndex) Len() int {
+	return len(s.shapes)
+}
+
+// Reset resets the index to its original state.
+func (s *ShapeIndex) Reset() {
+	s.shapes = make(map[int32]Shape)
+	s.nextID = 0
+	s.cellMap = make(map[CellID]*ShapeIndexCell)
+	s.cells = nil
+	atomic.StoreInt32(&s.status, fresh)
+}
+
+// NumEdges returns the number of edges in this index.
+func (s *ShapeIndex) NumEdges() int {
+	numEdges := 0
+	for _, shape := range s.shapes {
+		numEdges += shape.NumEdges()
+	}
+	return numEdges
+}
+
+// NumEdgesUpTo returns the number of edges in the given index, up to the given
+// limit. If the limit is encountered, the current running total is returned,
+// which may be more than the limit.
+func (s *ShapeIndex) NumEdgesUpTo(limit int) int {
+	var numEdges int
+	// We choose to iterate over the shapes in order to match the counting
+	// up behavior in C++ and for test compatibility instead of using a
+	// more idiomatic range over the shape map.
+	for i := int32(0); i <= s.nextID; i++ {
+		s := s.Shape(i)
+		if s == nil {
+			continue
+		}
+		numEdges += s.NumEdges()
+		if numEdges >= limit {
+			break
+		}
+	}
+
+	return numEdges
+}
+
+// Shape returns the shape with the given ID, or nil if the shape has been removed from the index.
+func (s *ShapeIndex) Shape(id int32) Shape { return s.shapes[id] }
+
+// idForShape returns the id of the given shape in this index, or -1 if it is
+// not in the index.
+//
+// TODO(roberts): Need to figure out an appropriate way to expose this on a Shape.
+// C++ allows a given S2 type (Loop, Polygon, etc) to be part of multiple indexes.
+// By having each type extend S2Shape which has an id element, they all inherit their
+// own id field rather than having to track it themselves.
+func (s *ShapeIndex) idForShape(shape Shape) int32 {
+	for k, v := range s.shapes {
+		if v == shape {
+			return k
+		}
+	}
+	return -1
+}
+
+// Add adds the given shape to the index and returns the assigned ID..
+func (s *ShapeIndex) Add(shape Shape) int32 {
+	s.shapes[s.nextID] = shape
+	s.nextID++
+	atomic.StoreInt32(&s.status, stale)
+	return s.nextID - 1
+}
+
+// Remove removes the given shape from the index.
+func (s *ShapeIndex) Remove(shape Shape) {
+	// The index updates itself lazily because it is much more efficient to
+	// process additions and removals in batches.
+	id := s.idForShape(shape)
+
+	// If the shape wasn't found, it's already been removed or was not in the index.
+	if s.shapes[id] == nil {
+		return
+	}
+
+	// Remove the shape from the shapes map.
+	delete(s.shapes, id)
+
+	// We are removing a shape that has not yet been added to the index,
+	// so there is nothing else to do.
+	if id >= s.pendingAdditionsPos {
+		return
+	}
+
+	numEdges := shape.NumEdges()
+	removed := &removedShape{
+		shapeID:               id,
+		hasInterior:           shape.Dimension() == 2,
+		containsTrackerOrigin: shape.ReferencePoint().Contained,
+		edges:                 make([]Edge, numEdges),
+	}
+
+	for e := 0; e < numEdges; e++ {
+		removed.edges[e] = shape.Edge(e)
+	}
+
+	s.pendingRemovals = append(s.pendingRemovals, removed)
+	atomic.StoreInt32(&s.status, stale)
+}
+
+// IsFresh reports if there are no pending updates that need to be applied.
+// This can be useful to avoid building the index unnecessarily, or for
+// choosing between two different algorithms depending on whether the index
+// is available.
+//
+// The returned index status may be slightly out of date if the index was
+// built in a different thread. This is fine for the intended use (as an
+// efficiency hint), but it should not be used by internal methods.
+func (s *ShapeIndex) IsFresh() bool {
+	return atomic.LoadInt32(&s.status) == fresh
+}
+
+// isFirstUpdate reports if this is the first update to the index.
+func (s *ShapeIndex) isFirstUpdate() bool {
+	// Note that it is not sufficient to check whether cellMap is empty, since
+	// entries are added to it during the update process.
+	return s.pendingAdditionsPos == 0
+}
+
+// isShapeBeingRemoved reports if the shape with the given ID is currently slated for removal.
+func (s *ShapeIndex) isShapeBeingRemoved(shapeID int32) bool {
+	// All shape ids being removed fall below the index position of shapes being added.
+	return shapeID < s.pendingAdditionsPos
+}
+
+// maybeApplyUpdates checks if the index pieces have changed, and if so, applies pending updates.
+func (s *ShapeIndex) maybeApplyUpdates() {
+	// TODO(roberts): To avoid acquiring and releasing the mutex on every
+	// query, we should use atomic operations when testing whether the status
+	// is fresh and when updating the status to be fresh. This guarantees
+	// that any thread that sees a status of fresh will also see the
+	// corresponding index updates.
+	if atomic.LoadInt32(&s.status) != fresh {
+		s.mu.Lock()
+		s.applyUpdatesInternal()
+		atomic.StoreInt32(&s.status, fresh)
+		s.mu.Unlock()
+	}
+}
+
+// applyUpdatesInternal does the actual work of updating the index by applying all
+// pending additions and removals. It does *not* update the indexes status.
+func (s *ShapeIndex) applyUpdatesInternal() {
+	// TODO(roberts): Building the index can use up to 20x as much memory per
+	// edge as the final index memory size. If this causes issues, add in
+	// batched updating to limit the amount of items per batch to a
+	// configurable memory footprint overhead.
+	t := newTracker()
+
+	// allEdges maps a Face to a collection of faceEdges.
+	allEdges := make([][]faceEdge, 6)
+
+	for _, p := range s.pendingRemovals {
+		s.removeShapeInternal(p, allEdges, t)
+	}
+
+	for id := s.pendingAdditionsPos; id < int32(len(s.shapes)); id++ {
+		s.addShapeInternal(id, allEdges, t)
+	}
+
+	for face := 0; face < 6; face++ {
+		s.updateFaceEdges(face, allEdges[face], t)
+	}
+
+	s.pendingRemovals = s.pendingRemovals[:0]
+	s.pendingAdditionsPos = int32(len(s.shapes))
+	// It is the caller's responsibility to update the index status.
+}
+
+// addShapeInternal clips all edges of the given shape to the six cube faces,
+// adds the clipped edges to the set of allEdges, and starts tracking its
+// interior if necessary.
+func (s *ShapeIndex) addShapeInternal(shapeID int32, allEdges [][]faceEdge, t *tracker) {
+	shape, ok := s.shapes[shapeID]
+	if !ok {
+		// This shape has already been removed.
+		return
+	}
+
+	faceEdge := faceEdge{
+		shapeID:     shapeID,
+		hasInterior: shape.Dimension() == 2,
+	}
+
+	if faceEdge.hasInterior {
+		t.addShape(shapeID, containsBruteForce(shape, t.focus()))
+	}
+
+	numEdges := shape.NumEdges()
+	for e := 0; e < numEdges; e++ {
+		edge := shape.Edge(e)
+
+		faceEdge.edgeID = e
+		faceEdge.edge = edge
+		faceEdge.maxLevel = maxLevelForEdge(edge)
+		s.addFaceEdge(faceEdge, allEdges)
+	}
+}
+
+// addFaceEdge adds the given faceEdge into the collection of all edges.
+func (s *ShapeIndex) addFaceEdge(fe faceEdge, allEdges [][]faceEdge) {
+	aFace := face(fe.edge.V0.Vector)
+	// See if both endpoints are on the same face, and are far enough from
+	// the edge of the face that they don't intersect any (padded) adjacent face.
+	if aFace == face(fe.edge.V1.Vector) {
+		x, y := validFaceXYZToUV(aFace, fe.edge.V0.Vector)
+		fe.a = r2.Point{x, y}
+		x, y = validFaceXYZToUV(aFace, fe.edge.V1.Vector)
+		fe.b = r2.Point{x, y}
+
+		maxUV := 1 - cellPadding
+		if math.Abs(fe.a.X) <= maxUV && math.Abs(fe.a.Y) <= maxUV &&
+			math.Abs(fe.b.X) <= maxUV && math.Abs(fe.b.Y) <= maxUV {
+			allEdges[aFace] = append(allEdges[aFace], fe)
+			return
+		}
+	}
+
+	// Otherwise, we simply clip the edge to all six faces.
+	for face := 0; face < 6; face++ {
+		if aClip, bClip, intersects := ClipToPaddedFace(fe.edge.V0, fe.edge.V1, face, cellPadding); intersects {
+			fe.a = aClip
+			fe.b = bClip
+			allEdges[face] = append(allEdges[face], fe)
+		}
+	}
+}
+
+// updateFaceEdges adds or removes the various edges from the index.
+// An edge is added if shapes[id] is not nil, and removed otherwise.
+func (s *ShapeIndex) updateFaceEdges(face int, faceEdges []faceEdge, t *tracker) {
+	numEdges := len(faceEdges)
+	if numEdges == 0 && len(t.shapeIDs) == 0 {
+		return
+	}
+
+	// Create the initial clippedEdge for each faceEdge. Additional clipped
+	// edges are created when edges are split between child cells. We create
+	// two arrays, one containing the edge data and another containing pointers
+	// to those edges, so that during the recursion we only need to copy
+	// pointers in order to propagate an edge to the correct child.
+	clippedEdges := make([]*clippedEdge, numEdges)
+	bound := r2.EmptyRect()
+	for e := 0; e < numEdges; e++ {
+		clipped := &clippedEdge{
+			faceEdge: &faceEdges[e],
+		}
+		clipped.bound = r2.RectFromPoints(faceEdges[e].a, faceEdges[e].b)
+		clippedEdges[e] = clipped
+		bound = bound.AddRect(clipped.bound)
+	}
+
+	// Construct the initial face cell containing all the edges, and then update
+	// all the edges in the index recursively.
+	faceID := CellIDFromFace(face)
+	pcell := PaddedCellFromCellID(faceID, cellPadding)
+
+	disjointFromIndex := s.isFirstUpdate()
+	if numEdges > 0 {
+		shrunkID := s.shrinkToFit(pcell, bound)
+		if shrunkID != pcell.id {
+			// All the edges are contained by some descendant of the face cell. We
+			// can save a lot of work by starting directly with that cell, but if we
+			// are in the interior of at least one shape then we need to create
+			// index entries for the cells we are skipping over.
+			s.skipCellRange(faceID.RangeMin(), shrunkID.RangeMin(), t, disjointFromIndex)
+			pcell = PaddedCellFromCellID(shrunkID, cellPadding)
+			s.updateEdges(pcell, clippedEdges, t, disjointFromIndex)
+			s.skipCellRange(shrunkID.RangeMax().Next(), faceID.RangeMax().Next(), t, disjointFromIndex)
+			return
+		}
+	}
+
+	// Otherwise (no edges, or no shrinking is possible), subdivide normally.
+	s.updateEdges(pcell, clippedEdges, t, disjointFromIndex)
+}
+
+// shrinkToFit shrinks the PaddedCell to fit within the given bounds.
+func (s *ShapeIndex) shrinkToFit(pcell *PaddedCell, bound r2.Rect) CellID {
+	shrunkID := pcell.ShrinkToFit(bound)
+
+	if !s.isFirstUpdate() && shrunkID != pcell.CellID() {
+		// Don't shrink any smaller than the existing index cells, since we need
+		// to combine the new edges with those cells.
+		iter := s.Iterator()
+		if iter.LocateCellID(shrunkID) == Indexed {
+			shrunkID = iter.CellID()
+		}
+	}
+	return shrunkID
+}
+
+// skipCellRange skips over the cells in the given range, creating index cells if we are
+// currently in the interior of at least one shape.
+func (s *ShapeIndex) skipCellRange(begin, end CellID, t *tracker, disjointFromIndex bool) {
+	// If we aren't in the interior of a shape, then skipping over cells is easy.
+	if len(t.shapeIDs) == 0 {
+		return
+	}
+
+	// Otherwise generate the list of cell ids that we need to visit, and create
+	// an index entry for each one.
+	skipped := CellUnionFromRange(begin, end)
+	for _, cell := range skipped {
+		var clippedEdges []*clippedEdge
+		s.updateEdges(PaddedCellFromCellID(cell, cellPadding), clippedEdges, t, disjointFromIndex)
+	}
+}
+
+// updateEdges adds or removes the given edges whose bounding boxes intersect a
+// given cell. disjointFromIndex is an optimization hint indicating that cellMap
+// does not contain any entries that overlap the given cell.
+func (s *ShapeIndex) updateEdges(pcell *PaddedCell, edges []*clippedEdge, t *tracker, disjointFromIndex bool) {
+	// This function is recursive with a maximum recursion depth of 30 (maxLevel).
+
+	// Incremental updates are handled as follows. All edges being added or
+	// removed are combined together in edges, and all shapes with interiors
+	// are tracked using tracker. We subdivide recursively as usual until we
+	// encounter an existing index cell. At this point we absorb the index
+	// cell as follows:
+	//
+	//   - Edges and shapes that are being removed are deleted from edges and
+	//     tracker.
+	//   - All remaining edges and shapes from the index cell are added to
+	//     edges and tracker.
+	//   - Continue subdividing recursively, creating new index cells as needed.
+	//   - When the recursion gets back to the cell that was absorbed, we
+	//     restore edges and tracker to their previous state.
+	//
+	// Note that the only reason that we include removed shapes in the recursive
+	// subdivision process is so that we can find all of the index cells that
+	// contain those shapes efficiently, without maintaining an explicit list of
+	// index cells for each shape (which would be expensive in terms of memory).
+	indexCellAbsorbed := false
+	if !disjointFromIndex {
+		// There may be existing index cells contained inside pcell. If we
+		// encounter such a cell, we need to combine the edges being updated with
+		// the existing cell contents by absorbing the cell.
+		iter := s.Iterator()
+		r := iter.LocateCellID(pcell.id)
+		if r == Disjoint {
+			disjointFromIndex = true
+		} else if r == Indexed {
+			// Absorb the index cell by transferring its contents to edges and
+			// deleting it. We also start tracking the interior of any new shapes.
+			s.absorbIndexCell(pcell, iter, edges, t)
+			indexCellAbsorbed = true
+			disjointFromIndex = true
+		} else {
+			// DCHECK_EQ(SUBDIVIDED, r)
+		}
+	}
+
+	// If there are existing index cells below us, then we need to keep
+	// subdividing so that we can merge with those cells. Otherwise,
+	// makeIndexCell checks if the number of edges is small enough, and creates
+	// an index cell if possible (returning true when it does so).
+	if !disjointFromIndex || !s.makeIndexCell(pcell, edges, t) {
+		// TODO(roberts): If it turns out to have memory problems when there
+		// are 10M+ edges in the index, look into pre-allocating space so we
+		// are not always appending.
+		childEdges := [2][2][]*clippedEdge{} // [i][j]
+
+		// Compute the middle of the padded cell, defined as the rectangle in
+		// (u,v)-space that belongs to all four (padded) children. By comparing
+		// against the four boundaries of middle we can determine which children
+		// each edge needs to be propagated to.
+		middle := pcell.Middle()
+
+		// Build up a vector edges to be passed to each child cell. The (i,j)
+		// directions are left (i=0), right (i=1), lower (j=0), and upper (j=1).
+		// Note that the vast majority of edges are propagated to a single child.
+		for _, edge := range edges {
+			if edge.bound.X.Hi <= middle.X.Lo {
+				// Edge is entirely contained in the two left children.
+				a, b := s.clipVAxis(edge, middle.Y)
+				if a != nil {
+					childEdges[0][0] = append(childEdges[0][0], a)
+				}
+				if b != nil {
+					childEdges[0][1] = append(childEdges[0][1], b)
+				}
+			} else if edge.bound.X.Lo >= middle.X.Hi {
+				// Edge is entirely contained in the two right children.
+				a, b := s.clipVAxis(edge, middle.Y)
+				if a != nil {
+					childEdges[1][0] = append(childEdges[1][0], a)
+				}
+				if b != nil {
+					childEdges[1][1] = append(childEdges[1][1], b)
+				}
+			} else if edge.bound.Y.Hi <= middle.Y.Lo {
+				// Edge is entirely contained in the two lower children.
+				if a := s.clipUBound(edge, 1, middle.X.Hi); a != nil {
+					childEdges[0][0] = append(childEdges[0][0], a)
+				}
+				if b := s.clipUBound(edge, 0, middle.X.Lo); b != nil {
+					childEdges[1][0] = append(childEdges[1][0], b)
+				}
+			} else if edge.bound.Y.Lo >= middle.Y.Hi {
+				// Edge is entirely contained in the two upper children.
+				if a := s.clipUBound(edge, 1, middle.X.Hi); a != nil {
+					childEdges[0][1] = append(childEdges[0][1], a)
+				}
+				if b := s.clipUBound(edge, 0, middle.X.Lo); b != nil {
+					childEdges[1][1] = append(childEdges[1][1], b)
+				}
+			} else {
+				// The edge bound spans all four children. The edge
+				// itself intersects either three or four padded children.
+				left := s.clipUBound(edge, 1, middle.X.Hi)
+				a, b := s.clipVAxis(left, middle.Y)
+				if a != nil {
+					childEdges[0][0] = append(childEdges[0][0], a)
+				}
+				if b != nil {
+					childEdges[0][1] = append(childEdges[0][1], b)
+				}
+				right := s.clipUBound(edge, 0, middle.X.Lo)
+				a, b = s.clipVAxis(right, middle.Y)
+				if a != nil {
+					childEdges[1][0] = append(childEdges[1][0], a)
+				}
+				if b != nil {
+					childEdges[1][1] = append(childEdges[1][1], b)
+				}
+			}
+		}
+
+		// Now recursively update the edges in each child. We call the children in
+		// increasing order of CellID so that when the index is first constructed,
+		// all insertions into cellMap are at the end (which is much faster).
+		for pos := 0; pos < 4; pos++ {
+			i, j := pcell.ChildIJ(pos)
+			if len(childEdges[i][j]) > 0 || len(t.shapeIDs) > 0 {
+				s.updateEdges(PaddedCellFromParentIJ(pcell, i, j), childEdges[i][j],
+					t, disjointFromIndex)
+			}
+		}
+	}
+
+	if indexCellAbsorbed {
+		// Restore the state for any edges being removed that we are tracking.
+		t.restoreStateBefore(s.pendingAdditionsPos)
+	}
+}
+
+// makeIndexCell builds an indexCell from the given padded cell and set of edges and adds
+// it to the index. If the cell or edges are empty, no cell is added.
+func (s *ShapeIndex) makeIndexCell(p *PaddedCell, edges []*clippedEdge, t *tracker) bool {
+	// If the cell is empty, no index cell is needed. (In most cases this
+	// situation is detected before we get to this point, but this can happen
+	// when all shapes in a cell are removed.)
+	if len(edges) == 0 && len(t.shapeIDs) == 0 {
+		return true
+	}
+
+	// Count the number of edges that have not reached their maximum level yet.
+	// Return false if there are too many such edges.
+	count := 0
+	for _, ce := range edges {
+		if p.Level() < ce.faceEdge.maxLevel {
+			count++
+		}
+
+		if count > s.maxEdgesPerCell {
+			return false
+		}
+	}
+
+	// Possible optimization: Continue subdividing as long as exactly one child
+	// of the padded cell intersects the given edges. This can be done by finding
+	// the bounding box of all the edges and calling ShrinkToFit:
+	//
+	// cellID = p.ShrinkToFit(RectBound(edges));
+	//
+	// Currently this is not beneficial; it slows down construction by 4-25%
+	// (mainly computing the union of the bounding rectangles) and also slows
+	// down queries (since more recursive clipping is required to get down to
+	// the level of a spatial index cell). But it may be worth trying again
+	// once containsCenter is computed and all algorithms are modified to
+	// take advantage of it.
+
+	// We update the InteriorTracker as follows. For every Cell in the index
+	// we construct two edges: one edge from entry vertex of the cell to its
+	// center, and one from the cell center to its exit vertex. Here entry
+	// and exit refer the CellID ordering, i.e. the order in which points
+	// are encountered along the 2 space-filling curve. The exit vertex then
+	// becomes the entry vertex for the next cell in the index, unless there are
+	// one or more empty intervening cells, in which case the InteriorTracker
+	// state is unchanged because the intervening cells have no edges.
+
+	// Shift the InteriorTracker focus point to the center of the current cell.
+	if t.isActive && len(edges) != 0 {
+		if !t.atCellID(p.id) {
+			t.moveTo(p.EntryVertex())
+		}
+		t.drawTo(p.Center())
+		s.testAllEdges(edges, t)
+	}
+
+	// Allocate and fill a new index cell. To get the total number of shapes we
+	// need to merge the shapes associated with the intersecting edges together
+	// with the shapes that happen to contain the cell center.
+	cshapeIDs := t.shapeIDs
+	numShapes := s.countShapes(edges, cshapeIDs)
+	cell := NewShapeIndexCell(numShapes)
+
+	// To fill the index cell we merge the two sources of shapes: edge shapes
+	// (those that have at least one edge that intersects this cell), and
+	// containing shapes (those that contain the cell center). We keep track
+	// of the index of the next intersecting edge and the next containing shape
+	// as we go along. Both sets of shape ids are already sorted.
+	eNext := 0
+	cNextIdx := 0
+	for i := 0; i < numShapes; i++ {
+		var clipped *clippedShape
+		// advance to next value base + i
+		eshapeID := int32(s.Len())
+		cshapeID := eshapeID // Sentinels
+
+		if eNext != len(edges) {
+			eshapeID = edges[eNext].faceEdge.shapeID
+		}
+		if cNextIdx < len(cshapeIDs) {
+			cshapeID = cshapeIDs[cNextIdx]
+		}
+		eBegin := eNext
+		if cshapeID < eshapeID {
+			// The entire cell is in the shape interior.
+			clipped = newClippedShape(cshapeID, 0)
+			clipped.containsCenter = true
+			cNextIdx++
+		} else {
+			// Count the number of edges for this shape and allocate space for them.
+			for eNext < len(edges) && edges[eNext].faceEdge.shapeID == eshapeID {
+				eNext++
+			}
+			clipped = newClippedShape(eshapeID, eNext-eBegin)
+			for e := eBegin; e < eNext; e++ {
+				clipped.edges[e-eBegin] = edges[e].faceEdge.edgeID
+			}
+			if cshapeID == eshapeID {
+				clipped.containsCenter = true
+				cNextIdx++
+			}
+		}
+		cell.shapes[i] = clipped
+	}
+
+	// Add this cell to the map.
+	s.cellMap[p.id] = cell
+	s.cells = append(s.cells, p.id)
+
+	// Shift the tracker focus point to the exit vertex of this cell.
+	if t.isActive && len(edges) != 0 {
+		t.drawTo(p.ExitVertex())
+		s.testAllEdges(edges, t)
+		t.setNextCellID(p.id.Next())
+	}
+	return true
+}
+
+// updateBound updates the specified endpoint of the given clipped edge and returns the
+// resulting clipped edge.
+func (s *ShapeIndex) updateBound(edge *clippedEdge, uEnd int, u float64, vEnd int, v float64) *clippedEdge {
+	c := &clippedEdge{faceEdge: edge.faceEdge}
+	if uEnd == 0 {
+		c.bound.X.Lo = u
+		c.bound.X.Hi = edge.bound.X.Hi
+	} else {
+		c.bound.X.Lo = edge.bound.X.Lo
+		c.bound.X.Hi = u
+	}
+
+	if vEnd == 0 {
+		c.bound.Y.Lo = v
+		c.bound.Y.Hi = edge.bound.Y.Hi
+	} else {
+		c.bound.Y.Lo = edge.bound.Y.Lo
+		c.bound.Y.Hi = v
+	}
+
+	return c
+}
+
+// clipUBound clips the given endpoint (lo=0, hi=1) of the u-axis so that
+// it does not extend past the given value of the given edge.
+func (s *ShapeIndex) clipUBound(edge *clippedEdge, uEnd int, u float64) *clippedEdge {
+	// First check whether the edge actually requires any clipping. (Sometimes
+	// this method is called when clipping is not necessary, e.g. when one edge
+	// endpoint is in the overlap area between two padded child cells.)
+	if uEnd == 0 {
+		if edge.bound.X.Lo >= u {
+			return edge
+		}
+	} else {
+		if edge.bound.X.Hi <= u {
+			return edge
+		}
+	}
+	// We interpolate the new v-value from the endpoints of the original edge.
+	// This has two advantages: (1) we don't need to store the clipped endpoints
+	// at all, just their bounding box; and (2) it avoids the accumulation of
+	// roundoff errors due to repeated interpolations. The result needs to be
+	// clamped to ensure that it is in the appropriate range.
+	e := edge.faceEdge
+	v := edge.bound.Y.ClampPoint(interpolateFloat64(u, e.a.X, e.b.X, e.a.Y, e.b.Y))
+
+	// Determine which endpoint of the v-axis bound to update. If the edge
+	// slope is positive we update the same endpoint, otherwise we update the
+	// opposite endpoint.
+	var vEnd int
+	positiveSlope := (e.a.X > e.b.X) == (e.a.Y > e.b.Y)
+	if (uEnd == 1) == positiveSlope {
+		vEnd = 1
+	}
+	return s.updateBound(edge, uEnd, u, vEnd, v)
+}
+
+// clipVBound clips the given endpoint (lo=0, hi=1) of the v-axis so that
+// it does not extend past the given value of the given edge.
+func (s *ShapeIndex) clipVBound(edge *clippedEdge, vEnd int, v float64) *clippedEdge {
+	if vEnd == 0 {
+		if edge.bound.Y.Lo >= v {
+			return edge
+		}
+	} else {
+		if edge.bound.Y.Hi <= v {
+			return edge
+		}
+	}
+
+	// We interpolate the new v-value from the endpoints of the original edge.
+	// This has two advantages: (1) we don't need to store the clipped endpoints
+	// at all, just their bounding box; and (2) it avoids the accumulation of
+	// roundoff errors due to repeated interpolations. The result needs to be
+	// clamped to ensure that it is in the appropriate range.
+	e := edge.faceEdge
+	u := edge.bound.X.ClampPoint(interpolateFloat64(v, e.a.Y, e.b.Y, e.a.X, e.b.X))
+
+	// Determine which endpoint of the v-axis bound to update. If the edge
+	// slope is positive we update the same endpoint, otherwise we update the
+	// opposite endpoint.
+	var uEnd int
+	positiveSlope := (e.a.X > e.b.X) == (e.a.Y > e.b.Y)
+	if (vEnd == 1) == positiveSlope {
+		uEnd = 1
+	}
+	return s.updateBound(edge, uEnd, u, vEnd, v)
+}
+
+// cliupVAxis returns the given edge clipped to within the boundaries of the middle
+// interval along the v-axis, and adds the result to its children.
+func (s *ShapeIndex) clipVAxis(edge *clippedEdge, middle r1.Interval) (a, b *clippedEdge) {
+	if edge.bound.Y.Hi <= middle.Lo {
+		// Edge is entirely contained in the lower child.
+		return edge, nil
+	} else if edge.bound.Y.Lo >= middle.Hi {
+		// Edge is entirely contained in the upper child.
+		return nil, edge
+	}
+	// The edge bound spans both children.
+	return s.clipVBound(edge, 1, middle.Hi), s.clipVBound(edge, 0, middle.Lo)
+}
+
+// absorbIndexCell absorbs an index cell by transferring its contents to edges
+// and/or "tracker", and then delete this cell from the index. If edges includes
+// any edges that are being removed, this method also updates their
+// InteriorTracker state to correspond to the exit vertex of this cell.
+func (s *ShapeIndex) absorbIndexCell(p *PaddedCell, iter *ShapeIndexIterator, edges []*clippedEdge, t *tracker) {
+	// When we absorb a cell, we erase all the edges that are being removed.
+	// However when we are finished with this cell, we want to restore the state
+	// of those edges (since that is how we find all the index cells that need
+	// to be updated).  The edges themselves are restored automatically when
+	// UpdateEdges returns from its recursive call, but the InteriorTracker
+	// state needs to be restored explicitly.
+	//
+	// Here we first update the InteriorTracker state for removed edges to
+	// correspond to the exit vertex of this cell, and then save the
+	// InteriorTracker state.  This state will be restored by UpdateEdges when
+	// it is finished processing the contents of this cell.
+	if t.isActive && len(edges) != 0 && s.isShapeBeingRemoved(edges[0].faceEdge.shapeID) {
+		// We probably need to update the tracker. ("Probably" because
+		// it's possible that all shapes being removed do not have interiors.)
+		if !t.atCellID(p.id) {
+			t.moveTo(p.EntryVertex())
+		}
+		t.drawTo(p.ExitVertex())
+		t.setNextCellID(p.id.Next())
+		for _, edge := range edges {
+			fe := edge.faceEdge
+			if !s.isShapeBeingRemoved(fe.shapeID) {
+				break // All shapes being removed come first.
+			}
+			if fe.hasInterior {
+				t.testEdge(fe.shapeID, fe.edge)
+			}
+		}
+	}
+
+	// Save the state of the edges being removed, so that it can be restored
+	// when we are finished processing this cell and its children.  We don't
+	// need to save the state of the edges being added because they aren't being
+	// removed from "edges" and will therefore be updated normally as we visit
+	// this cell and its children.
+	t.saveAndClearStateBefore(s.pendingAdditionsPos)
+
+	// Create a faceEdge for each edge in this cell that isn't being removed.
+	var faceEdges []*faceEdge
+	trackerMoved := false
+
+	cell := iter.IndexCell()
+	for _, clipped := range cell.shapes {
+		shapeID := clipped.shapeID
+		shape := s.Shape(shapeID)
+		if shape == nil {
+			continue // This shape is being removed.
+		}
+
+		numClipped := clipped.numEdges()
+
+		// If this shape has an interior, start tracking whether we are inside the
+		// shape. updateEdges wants to know whether the entry vertex of this
+		// cell is inside the shape, but we only know whether the center of the
+		// cell is inside the shape, so we need to test all the edges against the
+		// line segment from the cell center to the entry vertex.
+		edge := &faceEdge{
+			shapeID:     shapeID,
+			hasInterior: shape.Dimension() == 2,
+		}
+
+		if edge.hasInterior {
+			t.addShape(shapeID, clipped.containsCenter)
+			// There might not be any edges in this entire cell (i.e., it might be
+			// in the interior of all shapes), so we delay updating the tracker
+			// until we see the first edge.
+			if !trackerMoved && numClipped > 0 {
+				t.moveTo(p.Center())
+				t.drawTo(p.EntryVertex())
+				t.setNextCellID(p.id)
+				trackerMoved = true
+			}
+		}
+		for i := 0; i < numClipped; i++ {
+			edgeID := clipped.edges[i]
+			edge.edgeID = edgeID
+			edge.edge = shape.Edge(edgeID)
+			edge.maxLevel = maxLevelForEdge(edge.edge)
+			if edge.hasInterior {
+				t.testEdge(shapeID, edge.edge)
+			}
+			var ok bool
+			edge.a, edge.b, ok = ClipToPaddedFace(edge.edge.V0, edge.edge.V1, p.id.Face(), cellPadding)
+			if !ok {
+				panic("invariant failure in ShapeIndex")
+			}
+			faceEdges = append(faceEdges, edge)
+		}
+	}
+	// Now create a clippedEdge for each faceEdge, and put them in "new_edges".
+	var newEdges []*clippedEdge
+	for _, faceEdge := range faceEdges {
+		clipped := &clippedEdge{
+			faceEdge: faceEdge,
+			bound:    clippedEdgeBound(faceEdge.a, faceEdge.b, p.bound),
+		}
+		newEdges = append(newEdges, clipped)
+	}
+
+	// Discard any edges from "edges" that are being removed, and append the
+	// remainder to "newEdges"  (This keeps the edges sorted by shape id.)
+	for i, clipped := range edges {
+		if !s.isShapeBeingRemoved(clipped.faceEdge.shapeID) {
+			newEdges = append(newEdges, edges[i:]...)
+			break
+		}
+	}
+
+	// Update the edge list and delete this cell from the index.
+	edges, newEdges = newEdges, edges
+	delete(s.cellMap, p.id)
+	// TODO(roberts): delete from s.Cells
+}
+
+// testAllEdges calls the trackers testEdge on all edges from shapes that have interiors.
+func (s *ShapeIndex) testAllEdges(edges []*clippedEdge, t *tracker) {
+	for _, edge := range edges {
+		if edge.faceEdge.hasInterior {
+			t.testEdge(edge.faceEdge.shapeID, edge.faceEdge.edge)
+		}
+	}
+}
+
+// countShapes reports the number of distinct shapes that are either associated with the
+// given edges, or that are currently stored in the InteriorTracker.
+func (s *ShapeIndex) countShapes(edges []*clippedEdge, shapeIDs []int32) int {
+	count := 0
+	lastShapeID := int32(-1)
+
+	// next clipped shape id in the shapeIDs list.
+	clippedNext := int32(0)
+	// index of the current element in the shapeIDs list.
+	shapeIDidx := 0
+	for _, edge := range edges {
+		if edge.faceEdge.shapeID == lastShapeID {
+			continue
+		}
+
+		count++
+		lastShapeID = edge.faceEdge.shapeID
+
+		// Skip over any containing shapes up to and including this one,
+		// updating count as appropriate.
+		for ; shapeIDidx < len(shapeIDs); shapeIDidx++ {
+			clippedNext = shapeIDs[shapeIDidx]
+			if clippedNext > lastShapeID {
+				break
+			}
+			if clippedNext < lastShapeID {
+				count++
+			}
+		}
+	}
+
+	// Count any remaining containing shapes.
+	count += len(shapeIDs) - shapeIDidx
+	return count
+}
+
+// maxLevelForEdge reports the maximum level for a given edge.
+func maxLevelForEdge(edge Edge) int {
+	// Compute the maximum cell size for which this edge is considered long.
+	// The calculation does not need to be perfectly accurate, so we use Norm
+	// rather than Angle for speed.
+	cellSize := edge.V0.Sub(edge.V1.Vector).Norm() * cellSizeToLongEdgeRatio
+	// Now return the first level encountered during subdivision where the
+	// average cell size is at most cellSize.
+	return AvgEdgeMetric.MinLevel(cellSize)
+}
+
+// removeShapeInternal does the actual work for removing a given shape from the index.
+func (s *ShapeIndex) removeShapeInternal(removed *removedShape, allEdges [][]faceEdge, t *tracker) {
+	// TODO(roberts): finish the implementation of this.
+}