Mercurial > gemma

annotate pkg/octree/strtree.go @ 4591:f456ce0a6a0e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
STRTree: Made number of entries per node a parameter.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Wed, 09 Oct 2019 11:40:11 +0200
parents 114979e97a6c
children 680f1d8802f0
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
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
21 const STRTreeDefaultEntries = 8
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
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 {
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
24 Entries int
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
25 tin *Tin
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
26 index []int32
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
27 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
28 }
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
29
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
30 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
31
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
32 if s.Entries == 0 {
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
33 s.Entries = STRTreeDefaultEntries
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
34 }
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
35
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
36 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
37
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
38 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
39
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 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
41 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
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
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 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
45
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
46 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
47
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
48 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
49 }
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
50
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
51 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
52
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
53 removed := make(map[int32]struct{})
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
54
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
55 stack := []int32{s.index[0]}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
56
2521
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
57 vertices := s.tin.Vertices
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
58
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
59 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
60 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
61 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
62
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
63 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
64 switch p.IntersectionBox2D(s.bbox(top)) {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
65 case IntersectionInside:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
66 // all triangles are inside polygon
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
67 case IntersectionOutSide:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
68 // all triangles are outside polygon
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
69 s.allTriangles(top, removed)
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
70 default:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
71 // mixed bag
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
72 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
73 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
74 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
75 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
76 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
77 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
78 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
79 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
80 ti := s.tin.Triangles[idx]
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
81 t := Triangle{
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
82 vertices[ti[0]],
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
83 vertices[ti[1]],
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
84 vertices[ti[2]],
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
85 }
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
86 if p.IntersectionWithTriangle(&t) != IntersectionInside {
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
87 removed[idx] = struct{}{}
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
88 }
2516
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 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
92
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
93 return removed
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
94 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
95
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
96 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
97 stack := []int32{pos}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
98 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
99 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
100 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
101 if top > 0 { // node
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 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
104 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
105 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
106 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
107 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
108 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
109 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
110 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
111 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
112 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
113
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 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
115 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
116 ti := s.tin.Triangles[items[i]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
117 tj := s.tin.Triangles[items[j]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
118 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
119 })
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
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
121 P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
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
122 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
123
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
124 slices := s.strSplit(items, S)
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
125
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
126 leaves := s.strJoin(
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
127 slices, S,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
128 func(i, j int32) bool {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
129 ti := s.tin.Triangles[i]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
130 tj := s.tin.Triangles[j]
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
131 return s.tin.Vertices[ti[0]].Y < s.tin.Vertices[tj[0]].Y
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
132 },
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
133 s.allocLeaf,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
134 )
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
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 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
137 }
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
138
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
139 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
140
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
141 if len(items) <= s.Entries {
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
142 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
143 }
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
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 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
146 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
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
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
149 P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
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
150 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
151
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
152 slices := s.strSplit(items, S)
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
153
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
154 nodes := s.strJoin(
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
155 slices, S,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
156 func(i, j int32) bool { return s.bbox(i).Y1 < s.bbox(j).Y1 },
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
157 s.allocNode,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
158 )
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
159
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
160 return s.buildNodes(nodes)
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
161 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
162
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
163 func (s *STRTree) bbox(idx int32) Box2D {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
164 if idx < 0 { // Don't care if leaf or node.
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
165 idx = -idx - 1
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
166 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
167 return s.bboxes[s.index[idx]]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
168 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
169
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
170 func (s *STRTree) strSplit(items []int32, S int) [][]int32 {
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
171 sm := S * s.Entries
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
172 slices := make([][]int32, S)
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
173 for i := range slices {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
174 var n int
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
175 if l := len(items); l < sm {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
176 n = l
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
177 } else {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
178 n = sm
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
179 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
180 slices[i] = items[:n]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
181 items = items[n:]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
182 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
183 return slices
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
184 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
185
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
186 func (s *STRTree) strJoin(
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
187 slices [][]int32, S int,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
188 less func(int32, int32) bool,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
189 alloc func([]int32) int32,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
190 ) []int32 {
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
191 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
192
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 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
194 sort.Slice(slice, func(i, j int) bool {
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
195 return less(slice[i], slice[j])
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
196 })
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 for len(slice) > 0 {
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
199 var n int
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
200 if l := len(slice); l >= s.Entries {
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
201 n = s.Entries
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
202 } else {
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
203 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
204 }
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
205 nodes = append(nodes, alloc(slice[: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
206 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
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 }
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
209 return nodes
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
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 }