Mercurial > gemma

comparison pkg/octree/polygon.go @ 2490:c9164ff98871 octree-diff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Started with point in polygon check.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Sun, 03 Mar 2019 21:10:07 +0100
parents 4f292ff74d9e
children 10681749371d
comparison
equal deleted inserted replaced
2489:4f292ff74d9e 2490:c9164ff98871
20 "math" 20 "math"
21 21
22 "gemma.intevation.de/gemma/pkg/wkb" 22 "gemma.intevation.de/gemma/pkg/wkb"
23 ) 23 )
24 24
25 type ring []float64
26
25 type Polygon struct { 27 type Polygon struct {
26 // TODO: Implement me! 28 // TODO: Implement me!
27 rings [][]float64 29 rings []ring
28 } 30 }
29 31
30 type IntersectionType byte 32 type IntersectionType byte
31 33
32 const ( 34 const (
41 } 43 }
42 44
43 func (p *Polygon) IntersectionWithTriangle(t *Triangle) IntersectionType { 45 func (p *Polygon) IntersectionWithTriangle(t *Triangle) IntersectionType {
44 // TODO: Implement me 46 // TODO: Implement me
45 return IntersectionOutSide 47 return IntersectionOutSide
48 }
49
50 func (rng ring) isClosed() bool { return (len(rng) / 2) >= 3 }
51
52 func (rng ring) contains(point []float64) bool {
53 if !rng.isClosed() {
54 return false
55 }
56
57 contains := intersectsWithRaycast(point, rng[:2], rng[len(rng)-2:len(rng)])
58
59 for i := 2; i < len(rng); i += 2 {
60 if intersectsWithRaycast(point, rng[i-2:i], rng[i:i+2]) {
61 contains = !contains
62 }
63 }
64
65 return contains
66 }
67
68 // Using the raycast algorithm, this returns whether or not the passed in point
69 // Intersects with the edge drawn by the passed in start and end points.
70 // Original implementation: http://rosettacode.org/wiki/Ray-casting_algorithm#Go
71 func intersectsWithRaycast(point, start, end []float64) bool {
72
73 // Always ensure that the the first point
74 // has a y coordinate that is less than the second point
75 if start[1] > end[1] {
76 // Switch the points if otherwise.
77 start, end = end, start
78 }
79
80 // Move the point's y coordinate
81 // outside of the bounds of the testing region
82 // so we can start drawing a ray
83 for point[1] == start[1] || point[1] == end[1] {
84 y := math.Nextafter(point[1], math.Inf(1))
85 point = []float64{point[0], y}
86 }
87
88 // If we are outside of the polygon, indicate so.
89 if point[1] < start[1] || point[1] > end[1] {
90 return false
91 }
92
93 if start[0] > end[0] {
94 if point[0] > start[0] {
95 return false
96 }
97 if point[0] < end[0] {
98 return true
99 }
100 } else {
101 if point[0] > end[0] {
102 return false
103 }
104 if point[0] < start[0] {
105 return true
106 }
107 }
108
109 raySlope := (point[1] - start[1]) / (point[0] - start[0])
110 diagSlope := (end[1] - start[1]) / (end[0] - start[0])
111
112 return raySlope >= diagSlope
46 } 113 }
47 114
48 func (p *Polygon) FromWKB(data []byte) error { 115 func (p *Polygon) FromWKB(data []byte) error {
49 116
50 r := bytes.NewReader(data) 117 r := bytes.NewReader(data)
77 var numRings uint32 144 var numRings uint32
78 if err = binary.Read(r, order, &numRings); err != nil { 145 if err = binary.Read(r, order, &numRings); err != nil {
79 return err 146 return err
80 } 147 }
81 148
82 rings := make([][]float64, numRings) 149 rngs := make([]ring, numRings)
83 150
84 for ring := uint32(0); ring < numRings; ring++ { 151 for rng := uint32(0); rng < numRings; rng++ {
85 var numVertices uint32 152 var numVertices uint32
86 if err = binary.Read(r, order, &numVertices); err != nil { 153 if err = binary.Read(r, order, &numVertices); err != nil {
87 return err 154 return err
88 } 155 }
89 156
90 vertices := make([]float64, 2*numVertices) 157 numVertices *= 2
158 vertices := make([]float64, numVertices)
91 159
92 for v := uint32(0); v < numVertices; v++ { 160 for v := uint32(0); v < numVertices; v += 2 {
93 var lat, lon uint64 161 var lat, lon uint64
94 if err = binary.Read(r, order, &lat); err != nil { 162 if err = binary.Read(r, order, &lat); err != nil {
95 return err 163 return err
96 } 164 }
97 if err = binary.Read(r, order, &lon); err != nil { 165 if err = binary.Read(r, order, &lon); err != nil {
98 return err 166 return err
99 } 167 }
100 vertices[v*2] = math.Float64frombits(lat) 168 vertices[v] = math.Float64frombits(lat)
101 vertices[v*2+1] = math.Float64frombits(lon) 169 vertices[v+1] = math.Float64frombits(lon)
102 } 170 }
103 171
104 rings[ring] = vertices 172 rngs[rng] = vertices
105 } 173 }
106 174
107 p.rings = rings 175 p.rings = rngs
108 176
109 return nil 177 return nil
110 } 178 }