Mercurial > gemma
annotate pkg/octree/strtree.go @ 2515:6bcaa8bf2603 octree-diff
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Tue, 05 Mar 2019 15:55:14 +0100 |
parents | 1534df518201 |
children | 1ec4c5633eb6 |
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 { |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
24 tri *Triangulation |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
25 index []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
|
26 triangles [][]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
|
27 bboxes []Box2D |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
28 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
29 |
2768f74d54ab
Added an 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 func (s *STRTree) Build(t *Triangulation) { |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
31 |
2768f74d54ab
Added an 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 s.tri = t |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
33 |
2768f74d54ab
Added an 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 s.triangles = t.TriangleSlices() |
2768f74d54ab
Added an 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 |
2768f74d54ab
Added an 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 := make([]int32, len(s.triangles)) |
2768f74d54ab
Added an 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 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
|
39 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
|
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 |
2768f74d54ab
Added an 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 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
|
43 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
44 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
|
45 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
46 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
|
47 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
48 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
49 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
|
50 sort.Slice(items, func(i, j int) bool { |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
51 ti := s.triangles[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
|
52 tj := s.triangles[items[j]] |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
53 return s.tri.Points[ti[0]].X < s.tri.Points[tj[0]].X |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
54 }) |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
55 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
56 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
|
57 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
|
58 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
59 sm := S * numEntries |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
60 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
61 slices := make([][]int32, S) |
2513
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
62 rest := items |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
63 for i := range slices { |
2513
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
64 var n int |
2515
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
65 if l := len(rest); l < sm { |
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
66 n = l |
2513
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
67 } else { |
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
68 n = sm |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
69 } |
2513
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
70 slices[i] = rest[:n] |
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
71 rest = rest[n:] |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
72 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
73 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
74 leaves := make([]int32, 0, S*S) |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
75 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
76 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
|
77 sort.Slice(slice, func(i, j int) bool { |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
78 ti := s.triangles[slice[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
|
79 tj := s.triangles[slice[j]] |
2515
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
80 return s.tri.Points[ti[0]].Y < s.tri.Points[tj[0]].Y |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
81 }) |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
82 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
83 for len(slice) > 0 { |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
84 n := numEntries |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
85 if l := len(slice); l < numEntries { |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
86 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
|
87 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
88 leaves = append(leaves, s.allocLeaf(slice[:n])) |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
89 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
|
90 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
91 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
92 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
93 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
|
94 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
95 |
2515
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
96 func (s *STRTree) bbox(idx int32) Box2D { |
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
97 if idx < 0 { // Don't care if leaf or node. |
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
98 idx = -idx - 1 |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
99 } |
2515
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
100 return s.bboxes[s.index[idx]] |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
101 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
102 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
103 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
|
104 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
105 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
|
106 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
|
107 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
108 |
2768f74d54ab
Added an 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 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
|
110 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
|
111 }) |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
112 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
113 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
|
114 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
|
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 sm := S * numEntries |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
117 |
2768f74d54ab
Added an 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 slices := make([][]int32, S) |
2513
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
119 |
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
120 rest := items |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
121 for i := range slices { |
2513
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
122 var n int |
2515
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
123 if l := len(rest); l < sm { |
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
124 n = l |
2513
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
125 } else { |
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
126 n = sm |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
127 } |
2513
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
128 slices[i] = rest[:n] |
1534df518201
Called STT tree building.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2512
diff
changeset
|
129 rest = rest[n:] |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
130 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
131 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
132 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
|
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 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
|
135 sort.Slice(slice, func(i, j int) bool { |
2515
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
136 return s.bbox(slice[i]).Y1 < s.bbox(slice[j]).Y1 |
2512
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
137 }) |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
138 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
139 for len(slice) > 0 { |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
140 n := numEntries |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
141 if l := len(slice); l < numEntries { |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
142 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
|
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 nodes = append(nodes, s.allocNode(slice[:n])) |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
145 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
|
146 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
147 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
148 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
149 return s.buildNodes(nodes) |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
150 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
151 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
152 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
|
153 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
|
154 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
|
155 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
|
156 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
|
157 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
|
158 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
|
159 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
|
160 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
161 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
|
162 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
163 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
|
164 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
165 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
166 func (s *STRTree) 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
|
167 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
|
168 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
|
169 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
|
170 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
171 |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
172 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
|
173 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
|
174 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
|
175 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
|
176 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
|
177 vertices := s.tri.Points |
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
|
178 ti := s.triangles[items[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
|
179 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
|
180 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
|
181 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
|
182 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
|
183 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
184 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
|
185 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
|
186 it := 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
|
187 ti := s.triangles[it] |
2768f74d54ab
Added an 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 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
|
189 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
|
190 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
|
191 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
|
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 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
|
194 } |
2768f74d54ab
Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
195 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
|
196 } |
2515
6bcaa8bf2603
STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
2513
diff
changeset
|
197 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
|
198 } |