Mercurial > gemma

annotate pkg/octree/strtree.go @ 2564:27501719e79b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
STT tree: deduplicated som code.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 11 Mar 2019 10:49:16 +0100
parents e26000628764
children 114979e97a6c
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
2564
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
109 func strSplit(items []int32, S int) [][]int32 {
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
110 sm := S * numEntries
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
111 slices := make([][]int32, S)
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
112 for i := range slices {
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
113 var n int
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
114 if l := len(items); l < sm {
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
115 n = l
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
116 } else {
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
117 n = sm
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
118 }
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
119 slices[i] = items[:n]
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
120 items = items[n:]
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
121 }
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
122 return slices
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
123 }
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
124
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 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
126 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
127 ti := s.tin.Triangles[items[i]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
128 tj := s.tin.Triangles[items[j]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
129 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
130 })
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
131
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 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
133 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
134
2564
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
135 slices := 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
136
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 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
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 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
140 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
141 ti := s.tin.Triangles[slice[i]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
142 tj := s.tin.Triangles[slice[j]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
143 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
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
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 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
147 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
148 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
149 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
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 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
152 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
153 }
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
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
156 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
157 }
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
158
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
159 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
160 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
161 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
162 }
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
163 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
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
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 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
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 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
169 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
170 }
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 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
173 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
174 })
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 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
177 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
178
2564
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
179 slices := 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
180
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 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
182
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
183 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
184 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
185 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
186 })
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
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
188 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
189 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
190 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
191 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
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 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
194 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
195 }
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 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
199 }
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
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 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
202 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
203 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
204 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
205 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
206 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
207 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
208 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
209 }
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 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
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 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
213 }
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
214
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 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
216 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
217 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
218 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
219 }
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 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
222 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
223 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
224 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
225 if len(items) > 0 {
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
226 vertices := s.tin.Vertices
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
227 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
228 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
229 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
230 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
231 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
232 }
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 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
234 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
235 it := items[i]
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
236 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
237 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
238 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
239 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
240 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
241 }
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
242 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
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 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
245 }
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
246 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
247 }