diff options
Diffstat (limited to 'vendor/github.com/golang/geo/s2/crossing_edge_query.go')
| -rw-r--r-- | vendor/github.com/golang/geo/s2/crossing_edge_query.go | 409 |
1 files changed, 0 insertions, 409 deletions
diff --git a/vendor/github.com/golang/geo/s2/crossing_edge_query.go b/vendor/github.com/golang/geo/s2/crossing_edge_query.go deleted file mode 100644 index 51852dab4..000000000 --- a/vendor/github.com/golang/geo/s2/crossing_edge_query.go +++ /dev/null @@ -1,409 +0,0 @@ -// Copyright 2017 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 ( - "sort" - - "github.com/golang/geo/r2" -) - -// CrossingEdgeQuery is used to find the Edge IDs of Shapes that are crossed by -// a given edge(s). -// -// Note that if you need to query many edges, it is more efficient to declare -// a single CrossingEdgeQuery instance and reuse it. -// -// If you want to find *all* the pairs of crossing edges, it is more efficient to -// use the not yet implemented VisitCrossings in shapeutil. -type CrossingEdgeQuery struct { - index *ShapeIndex - - // temporary values used while processing a query. - a, b r2.Point - iter *ShapeIndexIterator - - // candidate cells generated when finding crossings. - cells []*ShapeIndexCell -} - -// NewCrossingEdgeQuery creates a CrossingEdgeQuery for the given index. -func NewCrossingEdgeQuery(index *ShapeIndex) *CrossingEdgeQuery { - c := &CrossingEdgeQuery{ - index: index, - iter: index.Iterator(), - } - return c -} - -// Crossings returns the set of edge of the shape S that intersect the given edge AB. -// If the CrossingType is Interior, then only intersections at a point interior to both -// edges are reported, while if it is CrossingTypeAll then edges that share a vertex -// are also reported. -func (c *CrossingEdgeQuery) Crossings(a, b Point, shape Shape, crossType CrossingType) []int { - edges := c.candidates(a, b, shape) - if len(edges) == 0 { - return nil - } - - crosser := NewEdgeCrosser(a, b) - out := 0 - n := len(edges) - - for in := 0; in < n; in++ { - b := shape.Edge(edges[in]) - sign := crosser.CrossingSign(b.V0, b.V1) - if crossType == CrossingTypeAll && (sign == MaybeCross || sign == Cross) || crossType != CrossingTypeAll && sign == Cross { - edges[out] = edges[in] - out++ - } - } - - if out < n { - edges = edges[0:out] - } - return edges -} - -// EdgeMap stores a sorted set of edge ids for each shape. -type EdgeMap map[Shape][]int - -// CrossingsEdgeMap returns the set of all edges in the index that intersect the given -// edge AB. If crossType is CrossingTypeInterior, then only intersections at a -// point interior to both edges are reported, while if it is CrossingTypeAll -// then edges that share a vertex are also reported. -// -// The edges are returned as a mapping from shape to the edges of that shape -// that intersect AB. Every returned shape has at least one crossing edge. -func (c *CrossingEdgeQuery) CrossingsEdgeMap(a, b Point, crossType CrossingType) EdgeMap { - edgeMap := c.candidatesEdgeMap(a, b) - if len(edgeMap) == 0 { - return nil - } - - crosser := NewEdgeCrosser(a, b) - for shape, edges := range edgeMap { - out := 0 - n := len(edges) - for in := 0; in < n; in++ { - edge := shape.Edge(edges[in]) - sign := crosser.CrossingSign(edge.V0, edge.V1) - if (crossType == CrossingTypeAll && (sign == MaybeCross || sign == Cross)) || (crossType != CrossingTypeAll && sign == Cross) { - edgeMap[shape][out] = edges[in] - out++ - } - } - - if out == 0 { - delete(edgeMap, shape) - } else { - if out < n { - edgeMap[shape] = edgeMap[shape][0:out] - } - } - } - return edgeMap -} - -// candidates returns a superset of the edges of the given shape that intersect -// the edge AB. -func (c *CrossingEdgeQuery) candidates(a, b Point, shape Shape) []int { - var edges []int - - // For small loops it is faster to use brute force. The threshold below was - // determined using benchmarks. - const maxBruteForceEdges = 27 - maxEdges := shape.NumEdges() - if maxEdges <= maxBruteForceEdges { - edges = make([]int, maxEdges) - for i := 0; i < maxEdges; i++ { - edges[i] = i - } - return edges - } - - // Compute the set of index cells intersected by the query edge. - c.getCellsForEdge(a, b) - if len(c.cells) == 0 { - return nil - } - - // Gather all the edges that intersect those cells and sort them. - // TODO(roberts): Shapes don't track their ID, so we need to range over - // the index to find the ID manually. - var shapeID int32 - for k, v := range c.index.shapes { - if v == shape { - shapeID = k - } - } - - for _, cell := range c.cells { - if cell == nil { - continue - } - clipped := cell.findByShapeID(shapeID) - if clipped == nil { - continue - } - edges = append(edges, clipped.edges...) - } - - if len(c.cells) > 1 { - edges = uniqueInts(edges) - } - - return edges -} - -// uniqueInts returns the sorted uniqued values from the given input. -func uniqueInts(in []int) []int { - var edges []int - m := make(map[int]bool) - for _, i := range in { - if m[i] { - continue - } - m[i] = true - edges = append(edges, i) - } - sort.Ints(edges) - return edges -} - -// candidatesEdgeMap returns a map from shapes to the superse of edges for that -// shape that intersect the edge AB. -// -// CAVEAT: This method may return shapes that have an empty set of candidate edges. -// However the return value is non-empty only if at least one shape has a candidate edge. -func (c *CrossingEdgeQuery) candidatesEdgeMap(a, b Point) EdgeMap { - edgeMap := make(EdgeMap) - - // If there are only a few edges then it's faster to use brute force. We - // only bother with this optimization when there is a single shape. - if len(c.index.shapes) == 1 { - // Typically this method is called many times, so it is worth checking - // whether the edge map is empty or already consists of a single entry for - // this shape, and skip clearing edge map in that case. - shape := c.index.Shape(0) - - // Note that we leave the edge map non-empty even if there are no candidates - // (i.e., there is a single entry with an empty set of edges). - edgeMap[shape] = c.candidates(a, b, shape) - return edgeMap - } - - // Compute the set of index cells intersected by the query edge. - c.getCellsForEdge(a, b) - if len(c.cells) == 0 { - return edgeMap - } - - // Gather all the edges that intersect those cells and sort them. - for _, cell := range c.cells { - for _, clipped := range cell.shapes { - s := c.index.Shape(clipped.shapeID) - for j := 0; j < clipped.numEdges(); j++ { - edgeMap[s] = append(edgeMap[s], clipped.edges[j]) - } - } - } - - if len(c.cells) > 1 { - for s, edges := range edgeMap { - edgeMap[s] = uniqueInts(edges) - } - } - - return edgeMap -} - -// getCells returns the set of ShapeIndexCells that might contain edges intersecting -// the edge AB in the given cell root. This method is used primarily by loop and shapeutil. -func (c *CrossingEdgeQuery) getCells(a, b Point, root *PaddedCell) []*ShapeIndexCell { - aUV, bUV, ok := ClipToFace(a, b, root.id.Face()) - if ok { - c.a = aUV - c.b = bUV - edgeBound := r2.RectFromPoints(c.a, c.b) - if root.Bound().Intersects(edgeBound) { - c.computeCellsIntersected(root, edgeBound) - } - } - - if len(c.cells) == 0 { - return nil - } - - return c.cells -} - -// getCellsForEdge populates the cells field to the set of index cells intersected by an edge AB. -func (c *CrossingEdgeQuery) getCellsForEdge(a, b Point) { - c.cells = nil - - segments := FaceSegments(a, b) - for _, segment := range segments { - c.a = segment.a - c.b = segment.b - - // Optimization: rather than always starting the recursive subdivision at - // the top level face cell, instead we start at the smallest S2CellId that - // contains the edge (the edge root cell). This typically lets us skip - // quite a few levels of recursion since most edges are short. - edgeBound := r2.RectFromPoints(c.a, c.b) - pcell := PaddedCellFromCellID(CellIDFromFace(segment.face), 0) - edgeRoot := pcell.ShrinkToFit(edgeBound) - - // Now we need to determine how the edge root cell is related to the cells - // in the spatial index (cellMap). There are three cases: - // - // 1. edgeRoot is an index cell or is contained within an index cell. - // In this case we only need to look at the contents of that cell. - // 2. edgeRoot is subdivided into one or more index cells. In this case - // we recursively subdivide to find the cells intersected by AB. - // 3. edgeRoot does not intersect any index cells. In this case there - // is nothing to do. - relation := c.iter.LocateCellID(edgeRoot) - if relation == Indexed { - // edgeRoot is an index cell or is contained by an index cell (case 1). - c.cells = append(c.cells, c.iter.IndexCell()) - } else if relation == Subdivided { - // edgeRoot is subdivided into one or more index cells (case 2). We - // find the cells intersected by AB using recursive subdivision. - if !edgeRoot.isFace() { - pcell = PaddedCellFromCellID(edgeRoot, 0) - } - c.computeCellsIntersected(pcell, edgeBound) - } - } -} - -// computeCellsIntersected computes the index cells intersected by the current -// edge that are descendants of pcell and adds them to this queries set of cells. -func (c *CrossingEdgeQuery) computeCellsIntersected(pcell *PaddedCell, edgeBound r2.Rect) { - - c.iter.seek(pcell.id.RangeMin()) - if c.iter.Done() || c.iter.CellID() > pcell.id.RangeMax() { - // The index does not contain pcell or any of its descendants. - return - } - if c.iter.CellID() == pcell.id { - // The index contains this cell exactly. - c.cells = append(c.cells, c.iter.IndexCell()) - return - } - - // Otherwise, split the edge among the four children of pcell. - center := pcell.Middle().Lo() - - if edgeBound.X.Hi < center.X { - // Edge is entirely contained in the two left children. - c.clipVAxis(edgeBound, center.Y, 0, pcell) - return - } else if edgeBound.X.Lo >= center.X { - // Edge is entirely contained in the two right children. - c.clipVAxis(edgeBound, center.Y, 1, pcell) - return - } - - childBounds := c.splitUBound(edgeBound, center.X) - if edgeBound.Y.Hi < center.Y { - // Edge is entirely contained in the two lower children. - c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 0, 0), childBounds[0]) - c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 1, 0), childBounds[1]) - } else if edgeBound.Y.Lo >= center.Y { - // Edge is entirely contained in the two upper children. - c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 0, 1), childBounds[0]) - c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 1, 1), childBounds[1]) - } else { - // The edge bound spans all four children. The edge itself intersects - // at most three children (since no padding is being used). - c.clipVAxis(childBounds[0], center.Y, 0, pcell) - c.clipVAxis(childBounds[1], center.Y, 1, pcell) - } -} - -// clipVAxis computes the intersected cells recursively for a given padded cell. -// Given either the left (i=0) or right (i=1) side of a padded cell pcell, -// determine whether the current edge intersects the lower child, upper child, -// or both children, and call c.computeCellsIntersected recursively on those children. -// The center is the v-coordinate at the center of pcell. -func (c *CrossingEdgeQuery) clipVAxis(edgeBound r2.Rect, center float64, i int, pcell *PaddedCell) { - if edgeBound.Y.Hi < center { - // Edge is entirely contained in the lower child. - c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, i, 0), edgeBound) - } else if edgeBound.Y.Lo >= center { - // Edge is entirely contained in the upper child. - c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, i, 1), edgeBound) - } else { - // The edge intersects both children. - childBounds := c.splitVBound(edgeBound, center) - c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, i, 0), childBounds[0]) - c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, i, 1), childBounds[1]) - } -} - -// splitUBound returns the bound for two children as a result of spliting the -// current edge at the given value U. -func (c *CrossingEdgeQuery) splitUBound(edgeBound r2.Rect, u float64) [2]r2.Rect { - v := edgeBound.Y.ClampPoint(interpolateFloat64(u, c.a.X, c.b.X, c.a.Y, c.b.Y)) - // diag indicates which diagonal of the bounding box is spanned by AB: - // it is 0 if AB has positive slope, and 1 if AB has negative slope. - var diag int - if (c.a.X > c.b.X) != (c.a.Y > c.b.Y) { - diag = 1 - } - return splitBound(edgeBound, 0, diag, u, v) -} - -// splitVBound returns the bound for two children as a result of spliting the -// current edge into two child edges at the given value V. -func (c *CrossingEdgeQuery) splitVBound(edgeBound r2.Rect, v float64) [2]r2.Rect { - u := edgeBound.X.ClampPoint(interpolateFloat64(v, c.a.Y, c.b.Y, c.a.X, c.b.X)) - var diag int - if (c.a.X > c.b.X) != (c.a.Y > c.b.Y) { - diag = 1 - } - return splitBound(edgeBound, diag, 0, u, v) -} - -// splitBound returns the bounds for the two childrenn as a result of spliting -// the current edge into two child edges at the given point (u,v). uEnd and vEnd -// indicate which bound endpoints of the first child will be updated. -func splitBound(edgeBound r2.Rect, uEnd, vEnd int, u, v float64) [2]r2.Rect { - var childBounds = [2]r2.Rect{ - edgeBound, - edgeBound, - } - - if uEnd == 1 { - childBounds[0].X.Lo = u - childBounds[1].X.Hi = u - } else { - childBounds[0].X.Hi = u - childBounds[1].X.Lo = u - } - - if vEnd == 1 { - childBounds[0].Y.Lo = v - childBounds[1].Y.Hi = v - } else { - childBounds[0].Y.Hi = v - childBounds[1].Y.Lo = v - } - - return childBounds -} |