1 // Copyright 2017 Google Inc. All rights reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 package s2 16 17 // ContainsVertexQuery is used to track the edges entering and leaving the 18 // given vertex of a Polygon in order to be able to determine if the point is 19 // contained by the Polygon. 20 // 21 // Point containment is defined according to the semi-open boundary model 22 // which means that if several polygons tile the region around a vertex, 23 // then exactly one of those polygons contains that vertex. 24 type ContainsVertexQuery struct { 25 target Point 26 edgeMap map[Point]int 27 } 28 29 // NewContainsVertexQuery returns a new query for the given vertex whose 30 // containment will be determined. 31 func NewContainsVertexQuery(target Point) *ContainsVertexQuery { 32 return &ContainsVertexQuery{ 33 target: target, 34 edgeMap: make(map[Point]int), 35 } 36 } 37 38 // AddEdge adds the edge between target and v with the given direction. 39 // (+1 = outgoing, -1 = incoming, 0 = degenerate). 40 func (q *ContainsVertexQuery) AddEdge(v Point, direction int) { 41 q.edgeMap[v] += direction 42 } 43 44 // ContainsVertex reports a +1 if the target vertex is contained, -1 if it is 45 // not contained, and 0 if the incident edges consisted of matched sibling pairs. 46 func (q *ContainsVertexQuery) ContainsVertex() int { 47 // Find the unmatched edge that is immediately clockwise from Ortho(P). 48 refDir := q.target.referenceDir() 49 50 bestPoint := refDir 51 bestDir := 0 52 53 for k, v := range q.edgeMap { 54 if v == 0 { 55 continue // This is a "matched" edge. 56 } 57 if OrderedCCW(refDir, bestPoint, k, q.target) { 58 bestPoint = k 59 bestDir = v 60 } 61 } 62 return bestDir 63 } 64