Mercurial > gemma

annotate pkg/octree/strtree.go @ 4017:639bdb17c3f2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed offset for fairway box This was broken by changeset: 4080:bf86f9a08733 user: Thomas Junk <thomas.junk@intevation.de> Date: Thu Jul 18 15:04:30 2019 +0200 summary: improve fairwaydiagram printing positioning For the record: I think the current implementation exceptionally flawed. Instead of adding extra offset parameters to the diagram elements the whole building block with all contained elements should be translated in one step, that would be less cluttered and less error prone...
author Sascha Wilde <wilde@intevation.de>
date Fri, 19 Jul 2019 16:59:25 +0200
parents 114979e97a6c
children f456ce0a6a0e
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
1 // This is Free Software under GNU Affero General Public License v >= 3.0
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
2 // without warranty, see README.md and license for details.
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
3 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
4 // SPDX-License-Identifier: AGPL-3.0-or-later
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
5 // License-Filename: LICENSES/AGPL-3.0.txt
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
6 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
7 // Copyright (C) 2018 by via donau
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
8 // – Österreichische Wasserstraßen-Gesellschaft mbH
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
9 // Software engineering by Intevation GmbH
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
10 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
11 // Author(s):
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
13
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
14 package octree
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
15
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
16 import (
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
17 "math"
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 "sort"
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19 )
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
21 const numEntries = 8
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23 type STRTree struct {
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
24 tin *Tin
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
25 index []int32
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
26 bboxes []Box2D
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
29 func (s *STRTree) Build(t *Tin) {
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
31 s.tin = t
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
33 all := make([]int32, len(t.Triangles))
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35 for i := range all {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36 all[i] = int32(i)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
38
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39 s.index = append(s.index, 0)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
40
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41 root := s.build(all)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43 s.index[0] = root
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
44 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
46 func (s *STRTree) Clip(p *Polygon) map[int32]struct{} {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
47
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
48 removed := make(map[int32]struct{})
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
49
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
50 stack := []int32{s.index[0]}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
51
2521
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
52 vertices := s.tin.Vertices
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
53
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
54 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
55 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
56 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
57
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
58 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
59 switch p.IntersectionBox2D(s.bbox(top)) {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
60 case IntersectionInside:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
61 // all triangles are inside polygon
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
62 case IntersectionOutSide:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
63 // all triangles are outside polygon
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
64 s.allTriangles(top, removed)
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
65 default:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
66 // mixed bag
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
67 for i, n := int32(0), s.index[top+1]; i < n; i++ {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
68 stack = append(stack, s.index[top+2+i])
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
69 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
70 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
71 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
72 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
73 for i, n := int32(0), s.index[top+1]; i < n; i++ {
2521
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
74 idx := s.index[top+2+i]
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
75 ti := s.tin.Triangles[idx]
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
76 t := Triangle{
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
77 vertices[ti[0]],
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
78 vertices[ti[1]],
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
79 vertices[ti[2]],
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
80 }
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
81 if p.IntersectionWithTriangle(&t) != IntersectionInside {
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
82 removed[idx] = struct{}{}
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
83 }
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
84 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
85 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
86 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
87
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
88 return removed
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
89 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
90
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
91 func (s *STRTree) allTriangles(pos int32, tris map[int32]struct{}) {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
92 stack := []int32{pos}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
93 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
94 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
95 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
96 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
97 for i, n := int32(0), s.index[top+1]; i < n; i++ {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
98 stack = append(stack, s.index[top+2+i])
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
99 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
100 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
101 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
102 for i, n := int32(0), s.index[top+1]; i < n; i++ {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
103 tris[s.index[top+2+i]] = struct{}{}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
104 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
105 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
106 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
107 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
108
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
109 func (s *STRTree) build(items []int32) int32 {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
110 sort.Slice(items, func(i, j int) bool {
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
111 ti := s.tin.Triangles[items[i]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
112 tj := s.tin.Triangles[items[j]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
113 return s.tin.Vertices[ti[0]].X < s.tin.Vertices[tj[0]].X
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
114 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
115
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
116 P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
117 S := int(math.Ceil(math.Sqrt(float64(P))))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
118
2564
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
119 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
120
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
121 leaves := strJoin(
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
122 slices, S,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
123 func(i, j int32) bool {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
124 ti := s.tin.Triangles[i]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
125 tj := s.tin.Triangles[j]
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
126 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
127 },
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
128 s.allocLeaf,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
129 )
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 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
132 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
133
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
134 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
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 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
137 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
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
2768f74d54ab Added an 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(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
141 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
142 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
143
2768f74d54ab Added an 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 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
145 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
146
2564
27501719e79b STT tree: deduplicated som code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2521
diff changeset
147 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
148
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
149 nodes := strJoin(
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
150 slices, S,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
151 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
152 s.allocNode,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
153 )
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
154
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
155 return s.buildNodes(nodes)
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
156 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
157
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
158 func (s *STRTree) bbox(idx int32) Box2D {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
159 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
160 idx = -idx - 1
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 return s.bboxes[s.index[idx]]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
163 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
164
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
165 func strSplit(items []int32, S int) [][]int32 {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
166 sm := S * numEntries
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
167 slices := make([][]int32, S)
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
168 for i := range slices {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
169 var n int
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
170 if l := len(items); l < sm {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
171 n = l
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
172 } else {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
173 n = sm
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
174 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
175 slices[i] = items[:n]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
176 items = items[n:]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
177 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
178 return slices
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
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
181 func strJoin(
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
182 slices [][]int32, S int,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
183 less func(int32, int32) bool,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
184 alloc func([]int32) int32,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
185 ) []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
186 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
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 _, 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
189 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
190 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
191 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
192
2768f74d54ab Added an 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 len(slice) > 0 {
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
194 var n int
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
195 if l := len(slice); l >= numEntries {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
196 n = numEntries
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
197 } 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
198 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
199 }
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
200 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
201 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
202 }
2768f74d54ab Added an 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 }
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
204 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
205 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
206
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
207 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
208 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
209 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
210 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
211 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
212 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
213 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
214 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
215 }
2768f74d54ab Added an 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 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
217 }
2768f74d54ab Added an 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 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
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) 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
222 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
223 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
224 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
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
2768f74d54ab Added an 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 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
228 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
229 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
230 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
231 if len(items) > 0 {
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
232 vertices := s.tin.Vertices
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
233 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
234 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
235 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
236 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
237 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
238 }
2768f74d54ab Added an 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 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
240 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
241 it := items[i]
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
242 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
243 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
244 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
245 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
246 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
247 }
2768f74d54ab Added an 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 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
249 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
250 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
251 }
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
252 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
253 }