Mercurial > gemma

comparison pkg/octree/triangulator.go @ 4151:d12c2f4d3483

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Made 'golint' more happy with the octree package.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Fri, 02 Aug 2019 11:56:48 +0200
parents 4fa92d468164
children
comparison
equal deleted inserted replaced
4150:40bd6854a294 4151:d12c2f4d3483
18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
19 19
20 package octree 20 package octree
21 21
22 import ( 22 import (
23 "fmt" 23 "errors"
24 "math" 24 "math"
25 "sort" 25 "sort"
26 ) 26 )
27 27
28 type triangulator struct { 28 type triangulator struct {
41 return &triangulator{points: points} 41 return &triangulator{points: points}
42 } 42 }
43 43
44 // sorting a triangulator sorts the `ids` such that the referenced points 44 // sorting a triangulator sorts the `ids` such that the referenced points
45 // are in order by their distance to `center` 45 // are in order by their distance to `center`
46 func (a *triangulator) Len() int { 46 func (tri *triangulator) Len() int {
47 return len(a.points) 47 return len(tri.points)
48 } 48 }
49 49
50 func (a *triangulator) Swap(i, j int) { 50 func (tri *triangulator) Swap(i, j int) {
51 a.ids[i], a.ids[j] = a.ids[j], a.ids[i] 51 tri.ids[i], tri.ids[j] = tri.ids[j], tri.ids[i]
52 } 52 }
53 53
54 func (a *triangulator) Less(i, j int) bool { 54 func (tri *triangulator) Less(i, j int) bool {
55 d1 := a.squaredDistances[a.ids[i]] 55 d1 := tri.squaredDistances[tri.ids[i]]
56 d2 := a.squaredDistances[a.ids[j]] 56 d2 := tri.squaredDistances[tri.ids[j]]
57 if d1 != d2 { 57 if d1 != d2 {
58 return d1 < d2 58 return d1 < d2
59 } 59 }
60 p1 := a.points[a.ids[i]] 60 p1 := tri.points[tri.ids[i]]
61 p2 := a.points[a.ids[j]] 61 p2 := tri.points[tri.ids[j]]
62 if p1.X != p2.X { 62 if p1.X != p2.X {
63 return p1.X < p2.X 63 return p1.X < p2.X
64 } 64 }
65 return p1.Y < p2.Y 65 return p1.Y < p2.Y
66 } 66 }
133 i2 = int32(i) 133 i2 = int32(i)
134 minRadius = r 134 minRadius = r
135 } 135 }
136 } 136 }
137 if minRadius == infinity { 137 if minRadius == infinity {
138 return fmt.Errorf("No Delaunay triangulation exists for this input.") 138 return errors.New("no delaunay triangulation exists for this input")
139 } 139 }
140 140
141 // swap the order of the seed points for counter-clockwise orientation 141 // swap the order of the seed points for counter-clockwise orientation
142 if area(points[i0], points[i1], points[i2]) < 0 { 142 if area(points[i0], points[i1], points[i2]) < 0 {
143 i1, i2 = i2, i1 143 i1, i2 = i2, i1
262 tri.halfedges = tri.halfedges[:tri.trianglesLen] 262 tri.halfedges = tri.halfedges[:tri.trianglesLen]
263 263
264 return nil 264 return nil
265 } 265 }
266 266
267 func (t *triangulator) hashKey(point Vertex) int { 267 func (tri *triangulator) hashKey(point Vertex) int {
268 d := point.Sub2D(t.center) 268 d := point.Sub2D(tri.center)
269 return int(pseudoAngle(d.X, d.Y) * float64(len(t.hash))) 269 return int(pseudoAngle(d.X, d.Y) * float64(len(tri.hash)))
270 } 270 }
271 271
272 func (t *triangulator) hashEdge(e *node) { 272 func (tri *triangulator) hashEdge(e *node) {
273 t.hash[t.hashKey(t.points[e.i])] = e 273 tri.hash[tri.hashKey(tri.points[e.i])] = e
274 } 274 }
275 275
276 func (t *triangulator) addTriangle(i0, i1, i2, a, b, c int32) int32 { 276 func (tri *triangulator) addTriangle(i0, i1, i2, a, b, c int32) int32 {
277 i := int32(t.trianglesLen) 277 i := int32(tri.trianglesLen)
278 t.triangles[i] = i0 278 tri.triangles[i] = i0
279 t.triangles[i+1] = i1 279 tri.triangles[i+1] = i1
280 t.triangles[i+2] = i2 280 tri.triangles[i+2] = i2
281 t.link(i, a) 281 tri.link(i, a)
282 t.link(i+1, b) 282 tri.link(i+1, b)
283 t.link(i+2, c) 283 tri.link(i+2, c)
284 t.trianglesLen += 3 284 tri.trianglesLen += 3
285 return i 285 return i
286 } 286 }
287 287
288 func (t *triangulator) link(a, b int32) { 288 func (tri *triangulator) link(a, b int32) {
289 t.halfedges[a] = b 289 tri.halfedges[a] = b
290 if b >= 0 { 290 if b >= 0 {
291 t.halfedges[b] = a 291 tri.halfedges[b] = a
292 } 292 }
293 } 293 }
294 294
295 func (t *triangulator) legalize(a int32) int32 { 295 func (tri *triangulator) legalize(a int32) int32 {
296 // if the pair of triangles doesn't satisfy the Delaunay condition 296 // if the pair of triangles doesn't satisfy the Delaunay condition
297 // (p1 is inside the circumcircle of [p0, pl, pr]), flip them, 297 // (p1 is inside the circumcircle of [p0, pl, pr]), flip them,
298 // then do the same check/flip recursively for the new pair of triangles 298 // then do the same check/flip recursively for the new pair of triangles
299 // 299 //
300 // pl pl 300 // pl pl
306 // \ || / \ / 306 // \ || / \ /
307 // ar\ || /br b\ /br 307 // ar\ || /br b\ /br
308 // \||/ \ / 308 // \||/ \ /
309 // pr pr 309 // pr pr
310 310
311 b := t.halfedges[a] 311 b := tri.halfedges[a]
312 312
313 a0 := a - a%3 313 a0 := a - a%3
314 b0 := b - b%3 314 b0 := b - b%3
315 315
316 al := a0 + (a+1)%3 316 al := a0 + (a+1)%3
319 319
320 if b < 0 { 320 if b < 0 {
321 return ar 321 return ar
322 } 322 }
323 323
324 p0 := t.triangles[ar] 324 p0 := tri.triangles[ar]
325 pr := t.triangles[a] 325 pr := tri.triangles[a]
326 pl := t.triangles[al] 326 pl := tri.triangles[al]
327 p1 := t.triangles[bl] 327 p1 := tri.triangles[bl]
328 328
329 illegal := inCircle(t.points[p0], t.points[pr], t.points[pl], t.points[p1]) 329 illegal := inCircle(tri.points[p0], tri.points[pr], tri.points[pl], tri.points[p1])
330 330
331 if illegal { 331 if illegal {
332 t.triangles[a] = p1 332 tri.triangles[a] = p1
333 t.triangles[b] = p0 333 tri.triangles[b] = p0
334 334
335 // edge swapped on the other side of the hull (rare) 335 // edge swapped on the other side of the hull (rare)
336 // fix the halfedge reference 336 // fix the halfedge reference
337 if t.halfedges[bl] == -1 { 337 if tri.halfedges[bl] == -1 {
338 e := t.hull 338 e := tri.hull
339 for { 339 for {
340 if e.t == bl { 340 if e.t == bl {
341 e.t = a 341 e.t = a
342 break 342 break
343 } 343 }
344 e = e.next 344 e = e.next
345 if e == t.hull { 345 if e == tri.hull {
346 break 346 break
347 } 347 }
348 } 348 }
349 } 349 }
350 350
351 t.link(a, t.halfedges[bl]) 351 tri.link(a, tri.halfedges[bl])
352 t.link(b, t.halfedges[ar]) 352 tri.link(b, tri.halfedges[ar])
353 t.link(ar, bl) 353 tri.link(ar, bl)
354 354
355 br := b0 + (b+1)%3 355 br := b0 + (b+1)%3
356 356
357 t.legalize(a) 357 tri.legalize(a)
358 return t.legalize(br) 358 return tri.legalize(br)
359 } 359 }
360 360
361 return ar 361 return ar
362 } 362 }
363 363
364 func (t *triangulator) convexHull() []Vertex { 364 func (tri *triangulator) convexHull() []Vertex {
365 var result []Vertex 365 var result []Vertex
366 e := t.hull 366 e := tri.hull
367 for e != nil { 367 for e != nil {
368 result = append(result, t.points[e.i]) 368 result = append(result, tri.points[e.i])
369 e = e.prev 369 e = e.prev
370 if e == t.hull { 370 if e == tri.hull {
371 break 371 break
372 } 372 }
373 } 373 }
374 return result 374 return result
375 } 375 }