Mercurial > gemma

comparison pkg/octree/strtree.go @ 2516:1ec4c5633eb6 octree-diff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Clip STR tree and not Octree.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Tue, 05 Mar 2019 17:08:16 +0100
parents 6bcaa8bf2603
children e26000628764
comparison
equal deleted inserted replaced
2515:6bcaa8bf2603 2516:1ec4c5633eb6
19 ) 19 )
20 20
21 const numEntries = 8 21 const numEntries = 8
22 22
23 type STRTree struct { 23 type STRTree struct {
24 tri *Triangulation 24 tin *Tin
25 index []int32 25 index []int32
26 triangles [][]int32 26 bboxes []Box2D
27 bboxes []Box2D 27 }
28 } 28
29 29 func (s *STRTree) Build(t *Tin) {
30 func (s *STRTree) Build(t *Triangulation) { 30
31 31 s.tin = t
32 s.tri = t 32
33 33 all := make([]int32, len(t.Triangles))
34 s.triangles = t.TriangleSlices()
35
36 all := make([]int32, len(s.triangles))
37 34
38 for i := range all { 35 for i := range all {
39 all[i] = int32(i) 36 all[i] = int32(i)
40 } 37 }
41 38
44 root := s.build(all) 41 root := s.build(all)
45 42
46 s.index[0] = root 43 s.index[0] = root
47 } 44 }
48 45
46 func (s *STRTree) Clip(p *Polygon) map[int32]struct{} {
47
48 removed := make(map[int32]struct{})
49
50 stack := []int32{s.index[0]}
51
52 for len(stack) > 0 {
53 top := stack[len(stack)-1]
54 stack = stack[:len(stack)-1]
55
56 if top > 0 { // node
57 switch p.IntersectionBox2D(s.bbox(top)) {
58 case IntersectionInside:
59 // all triangles are inside polygon
60 case IntersectionOutSide:
61 // all triangles are outside polygon
62 s.allTriangles(top, removed)
63 default:
64 // mixed bag
65 for i, n := int32(0), s.index[top+1]; i < n; i++ {
66 stack = append(stack, s.index[top+2+i])
67 }
68 }
69 } else { // leaf
70 top = -top - 1
71 for i, n := int32(0), s.index[top+1]; i < n; i++ {
72 removed[s.index[top+2+i]] = struct{}{}
73 }
74 }
75 }
76
77 return removed
78 }
79
80 func (s *STRTree) allTriangles(pos int32, tris map[int32]struct{}) {
81 stack := []int32{pos}
82 for len(stack) > 0 {
83 top := stack[len(stack)-1]
84 stack = stack[:len(stack)-1]
85 if top > 0 { // node
86 for i, n := int32(0), s.index[top+1]; i < n; i++ {
87 stack = append(stack, s.index[top+2+i])
88 }
89 } else { // leaf
90 top = -top - 1
91 for i, n := int32(0), s.index[top+1]; i < n; i++ {
92 tris[s.index[top+2+i]] = struct{}{}
93 }
94 }
95 }
96 }
97
49 func (s *STRTree) build(items []int32) int32 { 98 func (s *STRTree) build(items []int32) int32 {
50 sort.Slice(items, func(i, j int) bool { 99 sort.Slice(items, func(i, j int) bool {
51 ti := s.triangles[items[i]] 100 ti := s.tin.Triangles[items[i]]
52 tj := s.triangles[items[j]] 101 tj := s.tin.Triangles[items[j]]
53 return s.tri.Points[ti[0]].X < s.tri.Points[tj[0]].X 102 return s.tin.Vertices[ti[0]].X < s.tin.Vertices[tj[0]].X
54 }) 103 })
55 104
56 P := int(math.Ceil(float64(len(items)) / float64(numEntries))) 105 P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
57 S := int(math.Ceil(math.Sqrt(float64(P)))) 106 S := int(math.Ceil(math.Sqrt(float64(P))))
58 107
73 122
74 leaves := make([]int32, 0, S*S) 123 leaves := make([]int32, 0, S*S)
75 124
76 for _, slice := range slices { 125 for _, slice := range slices {
77 sort.Slice(slice, func(i, j int) bool { 126 sort.Slice(slice, func(i, j int) bool {
78 ti := s.triangles[slice[i]] 127 ti := s.tin.Triangles[slice[i]]
79 tj := s.triangles[slice[j]] 128 tj := s.tin.Triangles[slice[j]]
80 return s.tri.Points[ti[0]].Y < s.tri.Points[tj[0]].Y 129 return s.tin.Vertices[ti[0]].Y < s.tin.Vertices[tj[0]].Y
81 }) 130 })
82 131
83 for len(slice) > 0 { 132 for len(slice) > 0 {
84 n := numEntries 133 n := numEntries
85 if l := len(slice); l < numEntries { 134 if l := len(slice); l < numEntries {
172 func (s *STRTree) allocLeaf(items []int32) int32 { 221 func (s *STRTree) allocLeaf(items []int32) int32 {
173 pos := len(s.index) 222 pos := len(s.index)
174 s.index = append(s.index, 0, int32(len(items))) 223 s.index = append(s.index, 0, int32(len(items)))
175 s.index = append(s.index, items...) 224 s.index = append(s.index, items...)
176 if len(items) > 0 { 225 if len(items) > 0 {
177 vertices := s.tri.Points 226 vertices := s.tin.Vertices
178 ti := s.triangles[items[0]] 227 ti := s.tin.Triangles[items[0]]
179 t := Triangle{ 228 t := Triangle{
180 vertices[ti[0]], 229 vertices[ti[0]],
181 vertices[ti[1]], 230 vertices[ti[1]],
182 vertices[ti[2]], 231 vertices[ti[2]],
183 } 232 }
184 box := t.BBox() 233 box := t.BBox()
185 for i := 1; i < len(items); i++ { 234 for i := 1; i < len(items); i++ {
186 it := items[i] 235 it := items[i]
187 ti := s.triangles[it] 236 ti := s.tin.Triangles[it]
188 t := Triangle{ 237 t := Triangle{
189 vertices[ti[0]], 238 vertices[ti[0]],
190 vertices[ti[1]], 239 vertices[ti[1]],
191 vertices[ti[2]], 240 vertices[ti[2]],
192 } 241 }