Mercurial > gemma

annotate pkg/octree/slice.go @ 4647:18331577a251 stree-experiment

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged default into stree-experiment branch.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Sun, 13 Oct 2019 16:02:16 +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 }