Mercurial > gemma

annotate pkg/octree/strtree.go @ 2549:9bf6b767a56a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
client: refactored and improved splitscreen for diagrams To make different diagrams possible, the splitscreen view needed to be decoupled from the cross profiles. Also the style has changed to make it more consistent with the rest of the app. The standard box header is now used and there are collapse and expand animations.
author Markus Kottlaender <markus@intevation.de>
date Fri, 08 Mar 2019 08:50:47 +0100
parents e26000628764
children 27501719e79b
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
1 // This is Free Software under GNU Affero General Public License v >= 3.0
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
2 // without warranty, see README.md and license for details.
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
3 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
4 // SPDX-License-Identifier: AGPL-3.0-or-later
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
5 // License-Filename: LICENSES/AGPL-3.0.txt
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
6 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
7 // Copyright (C) 2018 by via donau
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
8 // – Österreichische Wasserstraßen-Gesellschaft mbH
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
9 // Software engineering by Intevation GmbH
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
10 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
11 // Author(s):
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
13
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
14 package octree
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
15
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
16 import (
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
17 "math"
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 "sort"
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19 )
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
21 const numEntries = 8
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23 type STRTree struct {
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
24 tin *Tin
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
25 index []int32
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
26 bboxes []Box2D
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
29 func (s *STRTree) Build(t *Tin) {
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
31 s.tin = t
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
33 all := make([]int32, len(t.Triangles))
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35 for i := range all {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36 all[i] = int32(i)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
38
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39 s.index = append(s.index, 0)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
40
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41 root := s.build(all)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43 s.index[0] = root
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
44 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
46 func (s *STRTree) Clip(p *Polygon) map[int32]struct{} {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
47
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
48 removed := make(map[int32]struct{})
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
49
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
50 stack := []int32{s.index[0]}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
51
2521
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
52 vertices := s.tin.Vertices
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
53
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
54 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
55 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
56 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
57
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
58 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
59 switch p.IntersectionBox2D(s.bbox(top)) {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
60 case IntersectionInside:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
61 // all triangles are inside polygon
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
62 case IntersectionOutSide:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
63 // all triangles are outside polygon
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
64 s.allTriangles(top, removed)
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
65 default:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
66 // mixed bag
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
67 for i, n := int32(0), s.index[top+1]; i < n; i++ {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
68 stack = append(stack, s.index[top+2+i])
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
69 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
70 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
71 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
72 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
73 for i, n := int32(0), s.index[top+1]; i < n; i++ {
2521
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
74 idx := s.index[top+2+i]
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
75 ti := s.tin.Triangles[idx]
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
76 t := Triangle{
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
77 vertices[ti[0]],
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
78 vertices[ti[1]],
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
79 vertices[ti[2]],
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
80 }
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
81 if p.IntersectionWithTriangle(&t) != IntersectionInside {
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
82 removed[idx] = struct{}{}
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
83 }
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
84 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
85 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
86 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
87
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
88 return removed
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
89 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
90
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
91 func (s *STRTree) allTriangles(pos int32, tris map[int32]struct{}) {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
92 stack := []int32{pos}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
93 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
94 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
95 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
96 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
97 for i, n := int32(0), s.index[top+1]; i < n; i++ {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
98 stack = append(stack, s.index[top+2+i])
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
99 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
100 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
101 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
102 for i, n := int32(0), s.index[top+1]; i < n; i++ {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
103 tris[s.index[top+2+i]] = struct{}{}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
104 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
105 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
106 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
107 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
108
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
109 func (s *STRTree) build(items []int32) int32 {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
110 sort.Slice(items, func(i, j int) bool {
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
111 ti := s.tin.Triangles[items[i]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
112 tj := s.tin.Triangles[items[j]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
113 return s.tin.Vertices[ti[0]].X < s.tin.Vertices[tj[0]].X
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
114 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
115
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
116 P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
117 S := int(math.Ceil(math.Sqrt(float64(P))))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
118
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
119 sm := S * numEntries
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
120
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
121 slices := make([][]int32, S)
2513
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
122 rest := items
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
123 for i := range slices {
2513
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
124 var n int
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
125 if l := len(rest); l < sm {
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
126 n = l
2513
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
127 } else {
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
128 n = sm
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
129 }
2513
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
130 slices[i] = rest[:n]
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
131 rest = rest[n:]
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
132 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
133
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
134 leaves := make([]int32, 0, S*S)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
135
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
136 for _, slice := range slices {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
137 sort.Slice(slice, func(i, j int) bool {
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
138 ti := s.tin.Triangles[slice[i]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
139 tj := s.tin.Triangles[slice[j]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
140 return s.tin.Vertices[ti[0]].Y < s.tin.Vertices[tj[0]].Y
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
141 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
142
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
143 for len(slice) > 0 {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
144 n := numEntries
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
145 if l := len(slice); l < numEntries {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
146 n = l
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
147 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
148 leaves = append(leaves, s.allocLeaf(slice[:n]))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
149 slice = slice[n:]
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
150 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
151 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
152
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
153 return s.buildNodes(leaves)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
154 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
155
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
156 func (s *STRTree) bbox(idx int32) Box2D {
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
157 if idx < 0 { // Don't care if leaf or node.
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
158 idx = -idx - 1
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
159 }
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
160 return s.bboxes[s.index[idx]]
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
161 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
162
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
163 func (s *STRTree) buildNodes(items []int32) int32 {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
164
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
165 if len(items) <= numEntries {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
166 return s.allocNode(items)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
167 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
168
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
169 sort.Slice(items, func(i, j int) bool {
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
170 return s.bbox(items[i]).X1 < s.bbox(items[j]).X1
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
171 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
172
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
173 P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
174 S := int(math.Ceil(math.Sqrt(float64(P))))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
175
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
176 sm := S * numEntries
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
177
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
178 slices := make([][]int32, S)
2513
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
179
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
180 rest := items
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
181 for i := range slices {
2513
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
182 var n int
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
183 if l := len(rest); l < sm {
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
184 n = l
2513
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
185 } else {
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
186 n = sm
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
187 }
2513
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
188 slices[i] = rest[:n]
1534df518201 Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2512
diff changeset
189 rest = rest[n:]
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
190 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
191
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
192 nodes := make([]int32, 0, S*S)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
193
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
194 for _, slice := range slices {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
195 sort.Slice(slice, func(i, j int) bool {
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
196 return s.bbox(slice[i]).Y1 < s.bbox(slice[j]).Y1
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
197 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
198
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
199 for len(slice) > 0 {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
200 n := numEntries
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
201 if l := len(slice); l < numEntries {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
202 n = l
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
203 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
204 nodes = append(nodes, s.allocNode(slice[:n]))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
205 slice = slice[n:]
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
206 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
207 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
208
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
209 return s.buildNodes(nodes)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
210 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
211
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
212 func (s *STRTree) allocNode(items []int32) int32 {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
213 pos := len(s.index)
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
214 s.index = append(s.index, 0, int32(len(items)))
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
215 s.index = append(s.index, items...)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
216 if len(items) > 0 {
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
217 box := s.bbox(items[0])
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
218 for i := 1; i < len(items); i++ {
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
219 box = box.Union(s.bbox(items[i]))
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
220 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
221 s.index[pos] = int32(s.allocBBox(box))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
222 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
223 return int32(pos)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
224 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
225
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
226 func (s *STRTree) allocBBox(box Box2D) int {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
227 pos := len(s.bboxes)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
228 s.bboxes = append(s.bboxes, box)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
229 return pos
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
230 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
231
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
232 func (s *STRTree) allocLeaf(items []int32) int32 {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
233 pos := len(s.index)
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
234 s.index = append(s.index, 0, int32(len(items)))
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
235 s.index = append(s.index, items...)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
236 if len(items) > 0 {
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
237 vertices := s.tin.Vertices
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
238 ti := s.tin.Triangles[items[0]]
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
239 t := Triangle{
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
240 vertices[ti[0]],
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
241 vertices[ti[1]],
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
242 vertices[ti[2]],
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
243 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
244 box := t.BBox()
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
245 for i := 1; i < len(items); i++ {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
246 it := items[i]
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
247 ti := s.tin.Triangles[it]
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
248 t := Triangle{
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
249 vertices[ti[0]],
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
250 vertices[ti[1]],
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
251 vertices[ti[2]],
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
252 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
253 box = box.Union(t.BBox())
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
254 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
255 s.index[pos] = int32(s.allocBBox(box))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
256 }
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
257 return int32(-(pos + 1))
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
258 }