Mercurial > gemma
annotate pkg/octree/strtree.go @ 4484:819eafe60f41
Merged
author | Sascha Wilde <wilde@intevation.de> |
---|---|
date | Thu, 26 Sep 2019 12:16:23 +0200 |
parents | 114979e97a6c |
children | f456ce0a6a0e |
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 } |