diff options
Diffstat (limited to 'vendor/github.com/golang/geo/s2/shapeindex.go')
| -rw-r--r-- | vendor/github.com/golang/geo/s2/shapeindex.go | 1526 |
1 files changed, 0 insertions, 1526 deletions
diff --git a/vendor/github.com/golang/geo/s2/shapeindex.go b/vendor/github.com/golang/geo/s2/shapeindex.go deleted file mode 100644 index 6efa213ab..000000000 --- a/vendor/github.com/golang/geo/s2/shapeindex.go +++ /dev/null @@ -1,1526 +0,0 @@ -// 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 -} - -func (s *ShapeIndexIterator) clone() *ShapeIndexIterator { - return &ShapeIndexIterator{ - index: s.index, - position: s.position, - id: s.id, - cell: s.cell, - } -} - -// 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) -} - -// Build triggers the update of the index. Calls to Add and Release are normally -// queued and processed on the first subsequent query. This has many advantages, -// the most important of which is that sometimes there *is* no subsequent -// query, which lets us avoid building the index completely. -// -// This method forces any pending updates to be applied immediately. -func (s *ShapeIndex) Build() { - s.maybeApplyUpdates() -} - -// 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. -} |