Mercurial > gemma

annotate pkg/octree/slice.go @ 3624:3012d0b3badc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Allow same values for depth_reference in SR as in gauges The depth_reference in a sounding result references a depth_reference of the bottlenecks reference gauge. Therefor the same values must be accepted, which means the restriction to four chars is no good. In the real world this might be something as "LDC2010", which is obviously longer.
author Sascha Wilde <wilde@intevation.de>
date Wed, 05 Jun 2019 18:50:54 +0200
parents 7686c7c23506
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2572
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
1 // This is Free Software under GNU Affero General Public License v >= 3.0
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
2 // without warranty, see README.md and license for details.
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
3 //
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
4 // SPDX-License-Identifier: AGPL-3.0-or-later
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
5 // License-Filename: LICENSES/AGPL-3.0.txt
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
6 //
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
7 // Copyright (C) 2018, 2019 by via donau
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
8 // – Österreichische Wasserstraßen-Gesellschaft mbH
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
9 // Software engineering by Intevation GmbH
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
10 //
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
11 // Author(s):
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
13
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
14 package octree
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
15
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
16 import (
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
17 "runtime"
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 "sync"
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19 )
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
21 type PointMap map[Point]float64
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23 func (pm PointMap) Triangulate() (*Triangulation, error) {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
24 vertices := make([]Vertex, len(pm))
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25 var i int
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
26 for p, z := range pm {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27 vertices[i] = Vertex{X: p.X, Y: p.Y, Z: z}
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28 i++
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30 return Triangulate(vertices)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
31 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
33 func sliceWork(
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34 vs []Vertex,
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35 dst PointMap,
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36 fn func([]Vertex, func([]Vertex) []Vertex),
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37 ) {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
38 n := runtime.NumCPU()
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
40 wg := new(sync.WaitGroup)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42 slices := make(chan []Vertex)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43 out := make(chan []Vertex)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
44
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45 pool := make(chan []Vertex, n)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
46
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
47 const pageSize = 2048
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
48
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
49 turn := func(p []Vertex) []Vertex {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
50 if p != nil {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
51 out <- p
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
52 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
53 select {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
54 case p = <-pool:
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
55 default:
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
56 p = make([]Vertex, 0, pageSize)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
57 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
58 return p
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
59 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
60
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
61 for i := 0; i < n; i++ {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
62 wg.Add(1)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
63 go func() {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
64 defer wg.Done()
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
65 for slice := range slices {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
66 fn(slice, turn)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
67 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
68 }()
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
69 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
70 done := make(chan struct{})
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
71 go func() {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
72 defer close(done)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
73 for s := range out {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
74 for i := range s {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
75 v := &s[i]
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
76 key := Point{X: v.X, Y: v.Y}
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
77 if z, found := dst[key]; found {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
78 dst[key] = (z + v.Z) * 0.5
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
79 } else {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
80 dst[key] = v.Z
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
81 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
82 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
83 select {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
84 case pool <- s[:0:pageSize]:
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
85 default:
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
86 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
87 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
88 }()
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
89
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
90 size := len(vs)/n + 1
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
91 for len(vs) > 0 {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
92 var l int
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
93 if len(vs) < size {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
94 l = len(vs)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
95 } else {
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
96 l = size
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
97 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
98 slices <- vs[:l]
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
99 vs = vs[l:]
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
100 }
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
101 close(slices)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
102 wg.Wait()
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
103 close(out)
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
104 <-done
7686c7c23506 Morphological differences: Moved some code into octree package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
105 }