Mercurial > gemma
comparison pkg/octree/triangulator.go @ 4151:d12c2f4d3483
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 } |