Mercurial > gemma

annotate pkg/mesh/strtree.go @ 4853:181c2c05b12a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
More golint fixes.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Tue, 19 Nov 2019 16:27:38 +0100
parents f4abfd0ee8ad
children 01b593ea2311
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
4827
f4abfd0ee8ad Renamed octree package to mesh as there is no octree any more.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4768
diff changeset
14 package mesh
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
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 (
4646
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
17 "bytes"
4652
f5492fda097c Use gzip best speed instead of lz4.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4650
diff changeset
18 "compress/gzip"
4646
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
19 "encoding/binary"
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
20 "io"
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
21 "log"
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22 "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
23 "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
24 )
2768f74d54ab Added an 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
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
26 const STRTreeDefaultEntries = 8
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
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 type STRTree struct {
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
29 Entries int
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
30 tin *Tin
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
31 index []int32
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
32 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
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
4658
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
35 // Vertical does a vertical cross cut from (x1, y1) to (x2, y2).
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
36 func (s *STRTree) Vertical(x1, y1, x2, y2 float64, fn func(*Triangle)) {
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
37 box := Box2D{
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
38 X1: math.Min(x1, x2),
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
39 Y1: math.Min(y1, y2),
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
40 X2: math.Max(x1, x2),
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
41 Y2: math.Max(y1, y2),
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
42 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
43
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
44 // out of bounding box
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
45 if box.X2 < s.tin.Min.X || s.tin.Max.X < box.X1 ||
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
46 box.Y2 < s.tin.Min.Y || s.tin.Max.Y < box.Y1 {
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
47 return
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
48 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
49
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
50 line := NewPlane2D(x1, y1, x2, y2)
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
51
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
52 vertices := s.tin.Vertices
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
53
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
54 stack := []int32{s.index[0]}
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
55
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
56 for len(stack) > 0 {
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
57 top := stack[len(stack)-1]
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
58 stack = stack[:len(stack)-1]
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
59
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
60 if top > 0 { // node
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
61 if b := s.bbox(top); b.Intersects(box) && b.IntersectsPlane(line) {
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
62 n := s.index[top+1]
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
63 stack = append(stack, s.index[top+2:top+2+n]...)
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
64 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
65 } else { // leaf
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
66 top = -top - 1
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
67 if b := s.bbox(top); !b.Intersects(box) || !b.IntersectsPlane(line) {
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
68 continue
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
69 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
70 n := s.index[top+1]
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
71 for _, idx := range s.index[top+2 : top+2+n] {
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
72 ti := s.tin.Triangles[idx]
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
73 t := Triangle{
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
74 vertices[ti[0]],
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
75 vertices[ti[1]],
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
76 vertices[ti[2]],
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
77 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
78 v0 := line.Eval(t[0].X, t[0].Y)
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
79 v1 := line.Eval(t[1].X, t[1].Y)
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
80 v2 := line.Eval(t[2].X, t[2].Y)
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
81
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
82 if onPlane(v0) || onPlane(v1) || onPlane(v2) ||
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
83 sides(sides(sides(0, v0), v1), v2) == 3 {
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
84 fn(&t)
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
85 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
86 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
87 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
88 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
89 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
90
4654
3eda5a7215ab Generate STRTrees instaead of Octree during sounding result imports.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4652
diff changeset
91 func (s *STRTree) Min() Vertex { return s.tin.Min }
3eda5a7215ab Generate STRTrees instaead of Octree during sounding result imports.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4652
diff changeset
92 func (s *STRTree) Max() Vertex { return s.tin.Max }
3eda5a7215ab Generate STRTrees instaead of Octree during sounding result imports.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4652
diff changeset
93 func (s *STRTree) EPSG() uint32 { return s.tin.EPSG }
3eda5a7215ab Generate STRTrees instaead of Octree during sounding result imports.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4652
diff changeset
94
4641
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
95 func (s *STRTree) Value(x, y float64) (float64, bool) {
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
96
4658
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
97 if len(s.index) == 0 {
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
98 return 0, false
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
99 }
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
100
4641
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
101 stack := []int32{s.index[0]}
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
102
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
103 vertices := s.tin.Vertices
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
104
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
105 for len(stack) > 0 {
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
106 top := stack[len(stack)-1]
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
107 stack = stack[:len(stack)-1]
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
108
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
109 if top > 0 { // node
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
110 if s.bbox(top).Contains(x, y) {
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
111 n := s.index[top+1]
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
112 stack = append(stack, s.index[top+2:top+2+n]...)
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
113 }
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
114 } else { // leaf
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
115 top = -top - 1
4645
946689a56fc2 Forgot a bbox check when evaluating STRTree speeding it significantly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
116 if !s.bbox(top).Contains(x, y) {
946689a56fc2 Forgot a bbox check when evaluating STRTree speeding it significantly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
117 continue
946689a56fc2 Forgot a bbox check when evaluating STRTree speeding it significantly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
118 }
4658
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
119 n := s.index[top+1]
4bbfe3dd2ab5 Completed usage of STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4654
diff changeset
120 for _, idx := range s.index[top+2 : top+2+n] {
4641
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
121 ti := s.tin.Triangles[idx]
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
122 t := Triangle{
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
123 vertices[ti[0]],
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
124 vertices[ti[1]],
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
125 vertices[ti[2]],
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
126 }
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
127 if t.Contains(x, y) {
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
128 return t.Plane3D().Z(x, y), true
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
129 }
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
130 }
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
131 }
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
132 }
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
133 return 0, false
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
134 }
5ef04ae34872 Used STRTree for caluculating the diff.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 4592
diff changeset
135
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
136 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
137
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
138 if s.Entries == 0 {
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
139 s.Entries = STRTreeDefaultEntries
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
140 }
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
141
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
142 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
143
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
144 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
145
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
146 for 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
147 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
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
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
150 s.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
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 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
153
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
154 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
155 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
156
4592
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
157 func (s *STRTree) BuildWithout(t *Tin, remove map[int32]struct{}) {
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
158
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
159 if s.Entries == 0 {
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
160 s.Entries = STRTreeDefaultEntries
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
161 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
162
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
163 s.tin = t
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
164
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
165 all := make([]int32, 0, len(t.Triangles)-len(remove))
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
166
4642
b5d9647c5bc1 Fixed construction of clipped STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4641
diff changeset
167 for i := 0; i < len(t.Triangles); i++ {
4592
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
168 idx := int32(i)
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
169 if _, found := remove[idx]; !found {
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
170 all = append(all, idx)
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
171 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
172 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
173
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
174 s.index = append(s.index, 0)
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
175
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
176 root := s.build(all)
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
177
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
178 s.index[0] = root
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
179 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4591
diff changeset
180
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
181 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
182
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
183 removed := make(map[int32]struct{})
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
184
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
185 stack := []int32{s.index[0]}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
186
2521
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
187 vertices := s.tin.Vertices
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
188
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
189 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
190 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
191 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
192
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
193 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
194 switch p.IntersectionBox2D(s.bbox(top)) {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
195 case IntersectionInside:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
196 // all triangles are inside polygon
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
197 case IntersectionOutSide:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
198 // all triangles are outside polygon
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
199 s.allTriangles(top, removed)
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
200 default:
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
201 // mixed bag
4643
a1a9b1eab57c Use append/slicing trick to simplify tree traversals.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4642
diff changeset
202 n := s.index[top+1]
a1a9b1eab57c Use append/slicing trick to simplify tree traversals.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4642
diff changeset
203 stack = append(stack, s.index[top+2:top+2+n]...)
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
204 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
205 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
206 top = -top - 1
4703
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
207 switch p.IntersectionBox2D(s.bbox(top)) {
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
208 case IntersectionInside:
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
209 // all triangles are inside polygon
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
210 case IntersectionOutSide:
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
211 // all triangles are outside polygon
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
212 n := s.index[top+1]
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
213 for _, idx := range s.index[top+2 : top+2+n] {
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
214 removed[idx] = struct{}{}
2521
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
215 }
4703
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
216 default:
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
217 n := s.index[top+1]
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
218 for _, idx := range s.index[top+2 : top+2+n] {
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
219 ti := s.tin.Triangles[idx]
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
220 t := Triangle{
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
221 vertices[ti[0]],
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
222 vertices[ti[1]],
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
223 vertices[ti[2]],
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
224 }
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
225 if p.IntersectionWithTriangle(&t) != IntersectionInside {
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
226 removed[idx] = struct{}{}
6e179b338f1a STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4658
diff changeset
227 }
2521
e26000628764 Clip triangle in STR tree leaves correctly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2516
diff changeset
228 }
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
229 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
230 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
231 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
232
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
233 return removed
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
234 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
235
4646
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
236 func (s *STRTree) serializeIndex(w io.Writer) error {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
237
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
238 if err := binary.Write(w, binary.LittleEndian, int32(len(s.index))); err != nil {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
239 return err
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
240 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
241
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
242 var buf [binary.MaxVarintLen32]byte
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
243
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
244 var last int32
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
245 var written int
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
246
4650
f5fce22184da Added a deserializer from STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4647
diff changeset
247 for _, x := range s.index {
4646
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
248 delta := x - last
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
249 n := binary.PutVarint(buf[:], int64(delta))
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
250 for p := buf[:n]; len(p) > 0; p = p[n:] {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
251 var err error
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
252 if n, err = w.Write(p); err != nil {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
253 return err
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
254 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
255 written += n
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
256 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
257 last = x
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
258 }
4650
f5fce22184da Added a deserializer from STRTrees.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4647
diff changeset
259
4646
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
260 log.Printf("info: compressed index in bytes: %d %.2f (%d %.2f)\n",
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
261 written,
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
262 float64(written)/(1024*1024),
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
263 4*len(s.index),
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
264 float64(4*len(s.index))/(1024*1024),
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
265 )
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
266
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
267 return nil
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
268 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
269
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
270 func (s *STRTree) serializeBBoxes(w io.Writer) (rr error) {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
271
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
272 if err := binary.Write(w, binary.LittleEndian, int32(len(s.bboxes))); err != nil {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
273 return err
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
274 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
275
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
276 var err error
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
277
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
278 write := func(v float64) {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
279 if err == nil {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
280 err = binary.Write(w, binary.LittleEndian, math.Float64bits(v))
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
281 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
282 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
283 for _, box := range s.bboxes {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
284 write(box.X1)
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
285 write(box.Y1)
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
286 write(box.X2)
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
287 write(box.Y2)
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
288 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
289
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
290 return err
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
291 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
292
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
293 func (s *STRTree) Bytes() ([]byte, error) {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
294
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
295 var buf bytes.Buffer
4652
f5492fda097c Use gzip best speed instead of lz4.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4650
diff changeset
296 w, err := gzip.NewWriterLevel(&buf, gzip.BestSpeed)
f5492fda097c Use gzip best speed instead of lz4.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4650
diff changeset
297 if err != nil {
f5492fda097c Use gzip best speed instead of lz4.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4650
diff changeset
298 return nil, err
f5492fda097c Use gzip best speed instead of lz4.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4650
diff changeset
299 }
4646
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
300
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
301 if err := s.tin.serialize(w); err != nil {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
302 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
303 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
304
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
305 if err := binary.Write(w, binary.LittleEndian, uint8(s.Entries)); err != nil {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
306 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
307 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
308
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
309 if err := s.serializeIndex(w); err != nil {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
310 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
311 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
312
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
313 if err := s.serializeBBoxes(w); err != nil {
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
314 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
315 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
316
4652
f5492fda097c Use gzip best speed instead of lz4.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4650
diff changeset
317 if err := w.Close(); err != nil {
4646
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
318 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
319 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
320
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
321 return buf.Bytes(), nil
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
322 }
89a72e0e2f9b Add a method to serialize an STRTree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4643
diff changeset
323
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
324 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
325 stack := []int32{pos}
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
326 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
327 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
328 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
329 if top > 0 { // node
4643
a1a9b1eab57c Use append/slicing trick to simplify tree traversals.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4642
diff changeset
330 n := s.index[top+1]
a1a9b1eab57c Use append/slicing trick to simplify tree traversals.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4642
diff changeset
331 stack = append(stack, s.index[top+2:top+2+n]...)
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
332 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
333 top = -top - 1
4704
9eb708176b43 STRTree: more efficent usage of slicing in collecting triangles during clipping.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4703
diff changeset
334 n := s.index[top+1]
9eb708176b43 STRTree: more efficent usage of slicing in collecting triangles during clipping.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4703
diff changeset
335 for _, idx := range s.index[top+2 : top+2+n] {
9eb708176b43 STRTree: more efficent usage of slicing in collecting triangles during clipping.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4703
diff changeset
336 tris[idx] = struct{}{}
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
337 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
338 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
339 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
340 }
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
341
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
342 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
343 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
344 ti := s.tin.Triangles[items[i]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
345 tj := s.tin.Triangles[items[j]]
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
346 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
347 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
348
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
349 P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
350 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
351
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
352 slices := s.strSplit(items, S)
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
353
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
354 leaves := s.strJoin(
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
355 slices, S,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
356 func(i, j int32) bool {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
357 ti := s.tin.Triangles[i]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
358 tj := s.tin.Triangles[j]
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
359 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
360 },
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
361 s.allocLeaf,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
362 )
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
363
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
364 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
365 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
366
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
367 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
368
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
369 if len(items) <= s.Entries {
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
370 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
371 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
372
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
373 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
374 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
375 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
376
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
377 P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
378 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
379
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
380 slices := s.strSplit(items, S)
2512
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
381
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
382 nodes := s.strJoin(
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
383 slices, S,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
384 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
385 s.allocNode,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
386 )
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
387
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
388 return s.buildNodes(nodes)
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
389 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
390
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
391 func (s *STRTree) bbox(idx int32) Box2D {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
392 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
393 idx = -idx - 1
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
394 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
395 return s.bboxes[s.index[idx]]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
396 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
397
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
398 func (s *STRTree) strSplit(items []int32, S int) [][]int32 {
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
399 sm := S * s.Entries
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
400 slices := make([][]int32, S)
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
401 for i := range slices {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
402 var n int
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
403 if l := len(items); l < sm {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
404 n = l
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
405 } else {
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
406 n = sm
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
407 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
408 slices[i] = items[:n]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
409 items = items[n:]
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
410 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
411 return slices
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
412 }
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
413
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
414 func (s *STRTree) strJoin(
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
415 slices [][]int32, S int,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
416 less func(int32, int32) bool,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
417 alloc func([]int32) int32,
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
418 ) []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
419 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
420
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
421 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
422 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
423 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
424 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
425
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
426 for len(slice) > 0 {
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
427 var n int
4591
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
428 if l := len(slice); l >= s.Entries {
f456ce0a6a0e STRTree: Made number of entries per node a parameter.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2565
diff changeset
429 n = s.Entries
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
430 } 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
431 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
432 }
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
433 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
434 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
435 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
436 }
2565
114979e97a6c STR tree: More code simplification.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2564
diff changeset
437 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
438 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
439
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
440 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
441 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
442 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
443 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
444 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
445 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
446 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
447 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
448 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
449 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
450 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
451 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
452 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
453
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
454 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
455 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
456 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
457 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
458 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
459
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
460 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
461 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
462 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
463 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
464 if len(items) > 0 {
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
465 vertices := s.tin.Vertices
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
466 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
467 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
468 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
469 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
470 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
471 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
472 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
473 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
474 it := items[i]
2516
1ec4c5633eb6 Clip STR tree and not Octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2515
diff changeset
475 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
476 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
477 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
478 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
479 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
480 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
481 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
482 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
483 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
484 }
2515
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2513
diff changeset
485 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
486 }