Mercurial > gemma

annotate cmd/isoareas/algo.go @ 4551:b5b23b6d76f1 iso-areas

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Move own algorith to separate file.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Tue, 01 Oct 2019 11:07:33 +0200
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4551
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
1 // This is Free Software under GNU Affero General Public License v >= 3.0
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
2 // without warranty, see README.md and license for details.
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
3 //
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
4 // SPDX-License-Identifier: AGPL-3.0-or-later
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
5 // License-Filename: LICENSES/AGPL-3.0.txt
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
6 //
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
7 // Copyright (C) 2019 by via donau
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
8 // – Österreichische Wasserstraßen-Gesellschaft mbH
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
9 // Software engineering by Intevation GmbH
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
10 //
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
11 // Author(s):
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
13
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
14 package main
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
15
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
16 import (
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
17 "bufio"
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 "container/list"
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19 "log"
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20 "math"
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
21 "math/bits"
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22 "os"
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23 "runtime"
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
24 "sync"
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
26 "gemma.intevation.de/gemma/pkg/octree"
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27 )
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29 type indexedArc struct {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30 arc int32
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
31 index int32
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
33
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34 func glue(a, b octree.LineStringZ) octree.LineStringZ {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36 a1, a2 := a[0], a[len(a)-1]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37 b1, b2 := b[0], b[len(b)-1]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
38
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39 if a1.EpsEquals2D(b2) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
40 c := make(octree.LineStringZ, len(a)-1+len(b))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41 copy(c, b)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42 copy(c[len(b):], a[1:])
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43 return c
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
44 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
46 if a2.EpsEquals2D(b1) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
47 c := make(octree.LineStringZ, len(a)-1+len(b))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
48 copy(c, a)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
49 copy(c[len(a):], b[1:])
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
50 return c
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
51 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
52
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
53 if a1.EpsEquals2D(b1) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
54 c := make(octree.LineStringZ, len(a)-1+len(b))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
55 copy(c, b)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
56 c[:len(b)].Reverse()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
57 copy(c[len(b):], a[1:])
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
58 return c
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
59 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
60
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
61 if a2.EpsEquals2D(b2) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
62 c := make(octree.LineStringZ, len(a)-1+len(b))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
63 copy(c, a)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
64 copy(c[len(a):], b[:len(b)-1])
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
65 c[len(a):].Reverse()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
66 return c
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
67 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
68
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
69 return nil
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
70 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
71
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
72 func connectArcs(tri *octree.Triangulation, cuts []indexedArc, arcs *[]octree.LineStringZ) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
73
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
74 unique := map[int32]struct{}{}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
75 for i := range cuts {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
76 unique[cuts[i].arc] = struct{}{}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
77 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
78 before := len(unique)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
79
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
80 origLen := int32(len(*arcs))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
81
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
82 for i := range cuts {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
83 if cuts[i].arc >= origLen {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
84 // already has a connected arc assigned.
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
85 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
86 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
87
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
88 line := (*arcs)[cuts[i].arc]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
89
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
90 var modified []int
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
91 visited := map[int32]struct{}{}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
92
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
93 var recursive func(int32)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
94 recursive = func(idx int32) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
95 visited[idx] = struct{}{}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
96
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
97 ns := neighbors(tri, idx)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
98 for _, n := range ns {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
99 n /= 3
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
100 if _, already := visited[n]; already {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
101 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
102 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
103
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
104 arcIdx := findArc(n, cuts)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
105 if arcIdx == -1 {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
106 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
107 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
108 arc := cuts[arcIdx].arc
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
109 if arc >= origLen {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
110 // already a new arc.
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
111 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
112 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
113 oline := (*arcs)[arc]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
114
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
115 nline := glue(line, oline)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
116 if nline == nil {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
117 // not joinable
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
118 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
119 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
120 line = nline
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
121 modified = append(modified, arcIdx)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
122 recursive(cuts[arcIdx].index)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
123 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
124 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
125 recursive(cuts[i].index)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
126 if len(modified) > 0 {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
127 // alloc a new line an fix the references.
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
128 nidx := int32(len(*arcs))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
129 *arcs = append(*arcs, line)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
130 cuts[i].arc = nidx
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
131 for _, j := range modified {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
132 cuts[j].arc = nidx
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
133 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
134 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
135 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
136
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
137 unique = map[int32]struct{}{}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
138 for i := range cuts {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
139 unique[cuts[i].arc] = struct{}{}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
140 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
141 log.Printf("unique arcs: before: %d after %d\n",
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
142 before, len(unique))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
143 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
144
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
145 func intersectTriangles(
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
146 tri *octree.Triangulation,
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
147 heights []float64,
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
148 min, max octree.Vertex,
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
149 ) [][]octree.LineStringZ {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
150
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
151 cuts := make([][]indexedArc, len(heights))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
152
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
153 classes := make([][]int32, len(heights)+1)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
154
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
155 var arcs []octree.LineStringZ
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
156
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
157 all:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
158 for i := int32(0); i < int32(len(tri.Triangles)); i += 3 {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
159 ti := tri.Triangles[i : i+3]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
160 v0 := tri.Points[ti[0]]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
161 v1 := tri.Points[ti[1]]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
162 v2 := tri.Points[ti[2]]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
163 min := math.Min(v0.Z, math.Min(v1.Z, v2.Z))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
164
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
165 if min > heights[len(heights)-1] {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
166 classes[len(classes)-1] = append(classes[len(classes)-1], i/3)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
167 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
168 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
169 max := math.Max(v0.Z, math.Max(v1.Z, v2.Z))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
170
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
171 for j, h := range heights {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
172
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
173 var l float64
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
174 if j > 0 {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
175 l = heights[j-1]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
176 } else {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
177 l = -math.MaxFloat64
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
178 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
179
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
180 if l < min && max < h {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
181 classes[j] = append(classes[j], i/3)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
182 continue all
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
183 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
184 if min > h || max < h {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
185 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
186 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
187 t := octree.Triangle{v0, v1, v2}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
188 cut := t.IntersectHorizontal(h)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
189 if len(cut) >= 2 {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
190 arc := int32(len(arcs))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
191 arcs = append(arcs, cut)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
192 cuts[j] = append(cuts[j], indexedArc{arc: arc, index: i / 3})
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
193 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
194 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
195 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
196
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
197 // connect the arcs in a cut list to longer arcs.
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
198
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
199 for _, c := range cuts {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
200 connectArcs(tri, c, &arcs)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
201 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
202
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
203 func() {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
204 out, err := os.Create("arcs.svg")
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
205 if err != nil {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
206 log.Printf("err: %v\n", err)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
207 return
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
208 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
209 defer func() {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
210 out.Close()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
211 log.Println("writing arcs done")
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
212 }()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
213
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
214 buf := bufio.NewWriter(out)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
215
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
216 dumpArcsSVG(
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
217 buf,
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
218 min, max,
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
219 cuts,
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
220 arcs)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
221 buf.Flush()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
222 }()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
223
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
224 result := make([][]octree.LineStringZ, len(classes))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
225
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
226 jobs := make(chan int)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
227
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
228 var wg sync.WaitGroup
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
229
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
230 worker := func() {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
231 defer wg.Done()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
232
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
233 pb := polygonBuilder{open: list.New()}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
234
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
235 for i := range jobs {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
236 usedArcs := map[int32]struct{}{}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
237 var dupes int
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
238 var isolated, inside, found int
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
239 c := classes[i]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
240
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
241 allInClass:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
242 for _, idx := range c {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
243 ns := neighbors(tri, idx)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
244 mask := where(ns, c)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
245 switch bits.OnesCount8(mask) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
246 case 3:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
247 // Totally insides do not contribute to the geometries.
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
248 inside++
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
249 continue allInClass
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
250 case 0:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
251 // Isolated are areas w/o connections to the rest.
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
252 isolated++
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
253 ti := tri.Triangles[idx*3 : idx*3+3]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
254 pb.addTriangle(
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
255 tri.Points[ti[0]],
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
256 tri.Points[ti[1]],
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
257 tri.Points[ti[2]])
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
258 continue allInClass
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
259 default:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
260 ti := tri.Triangles[idx*3 : idx*3+3]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
261 for j := 0; j < 3; j++ {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
262 if (mask & (1 << j)) == 0 {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
263
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
264 var curr octree.LineStringZ
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
265
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
266 for l := i - 1; l <= i; l++ {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
267 if l < 0 || l >= len(cuts) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
268 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
269 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
270 arcIdx := findArc(ns[j]/3, cuts[l])
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
271 if arcIdx == -1 {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
272 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
273 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
274 found++
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
275 aIdx := cuts[l][arcIdx].arc
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
276 if _, already := usedArcs[aIdx]; already {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
277 dupes++
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
278 continue
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
279 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
280 usedArcs[aIdx] = struct{}{}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
281
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
282 curr = arcs[aIdx]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
283 break
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
284 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
285
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
286 if curr == nil {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
287 k := (j + 1) % 3
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
288 front := tri.Points[ti[j]]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
289 back := tri.Points[ti[k]]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
290 curr = octree.LineStringZ{front, back}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
291 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
292
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
293 segment:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
294 for e := pb.open.Front(); e != nil; e = e.Next() {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
295 line := e.Value.(octree.LineStringZ)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
296 if nline := glue(curr, line); nline != nil {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
297 curr = nline
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
298 pb.open.Remove(e)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
299 goto segment
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
300 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
301 } // all open
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
302
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
303 // check if closed
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
304 if curr[0].EpsEquals2D(curr[len(curr)-1]) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
305 if !curr.CCW() {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
306 curr.Reverse()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
307 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
308 pb.polygons = append(pb.polygons, curr)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
309 } else {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
310 pb.open.PushFront(curr)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
311 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
312 } // for all border parts
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
313 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
314 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
315 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
316
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
317 log.Printf("\t%d: inside: %d / isolated: %d open: %d closed: %d dupes: %d found: %d\n",
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
318 i, inside, isolated, pb.open.Len(), len(pb.polygons), dupes, found)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
319 /*
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
320 for e := pb.open.Front(); e != nil; e = e.Next() {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
321 line := e.Value.(octree.LineStringZ)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
322 if !line.CCW() {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
323 line.Reverse()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
324 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
325 pb.polygons = append(pb.polygons, line)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
326 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
327 */
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
328
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
329 result[i] = pb.polygons
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
330 pb.reset()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
331 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
332 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
333
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
334 for n := runtime.NumCPU(); n >= 0; n-- {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
335 wg.Add(1)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
336 go worker()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
337 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
338
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
339 log.Println("inside classes:")
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
340 for i := range classes {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
341 jobs <- i
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
342 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
343 close(jobs)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
344
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
345 wg.Wait()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
346
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
347 log.Println("cuts:")
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
348 for i, c := range cuts {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
349 log.Printf("\t%.3f: %d\n", heights[i], len(c))
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
350 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
351
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
352 return result
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
353
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
354 // TODO: sew segments together.
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
355
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
356 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
357
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
358 type polygonBuilder struct {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
359 polygons []octree.LineStringZ
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
360
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
361 open *list.List
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
362 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
363
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
364 func (pb *polygonBuilder) addTriangle(v0, v1, v2 octree.Vertex) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
365 polygon := octree.LineStringZ{v0, v1, v2, v0}
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
366 pb.polygons = append(pb.polygons, polygon)
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
367 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
368
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
369 func (pb *polygonBuilder) reset() {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
370 pb.polygons = pb.polygons[:0]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
371 pb.open.Init()
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
372 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
373
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
374 func neighbors(t *octree.Triangulation, idx int32) []int32 {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
375 idx *= 3
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
376 return t.Halfedges[idx : idx+3]
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
377 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
378
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
379 func findArc(needle int32, haystack []indexedArc) int {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
380 lo, hi := 0, len(haystack)-1
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
381 for lo <= hi {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
382 mid := (hi-lo)/2 + lo
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
383 switch v := haystack[mid].index; {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
384 case v < needle:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
385 lo = mid + 1
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
386 case v > needle:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
387 hi = mid - 1
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
388 default:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
389 return mid
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
390 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
391 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
392 return -1
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
393 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
394
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
395 func contains(needle int32, haystack []int32) bool {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
396 lo, hi := 0, len(haystack)-1
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
397 for lo <= hi {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
398 mid := (hi-lo)/2 + lo
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
399 switch v := haystack[mid]; {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
400 case v < needle:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
401 lo = mid + 1
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
402 case v > needle:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
403 hi = mid - 1
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
404 default:
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
405 return true
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
406 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
407 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
408 return false
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
409 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
410
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
411 func where(neighbors, indices []int32) byte {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
412 var mask byte
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
413 for i, n := range neighbors {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
414 if n >= 0 && contains(n/3, indices) {
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
415 mask |= 1 << i
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
416 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
417 }
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
418 return mask
b5b23b6d76f1 Move own algorith to separate file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
419 }