gemma: pkg/mesh/strtree.go annotate

annotate pkg/mesh/strtree.go @ 5591:0011f50cf216 surveysperbottleneckid

Removed no longer used alternative api for surveys/ endpoint. As bottlenecks in the summary for SR imports are now identified by their id and no longer by the (not guarantied to be unique!) name, there is no longer the need to request survey data by the name+date tuple (which isn't reliable anyway). So the workaround was now reversed.

author	Sascha Wilde <wilde@sha-bang.de>
date	Wed, 06 Apr 2022 13:30:29 +0200
parents	5f47eeea988d
children	b8da63027b48

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"
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	21 "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	22 "sort"
5490 5f47eeea988d Use own logging package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4855 diff changeset	23
5f47eeea988d Use own logging package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4855 diff changeset	24 "gemma.intevation.de/gemma/pkg/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	25 )
2768f74d54ab Added an 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
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	27 // STRTreeDefaultEntries is the default number of children per node and leaf.
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	28 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	29
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	30 // STRTree is a Sort Tile Recurse tree.
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	31 type STRTree struct {
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	32 // Entries is the total number of entries.
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	33 Entries int
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	34 // tin is a reference to the TIN this tree is build from.
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	35 tin *Tin
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	36 // index is the internal tree representation.
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	37 index []int32
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	38 // bboxes are the bounding boxes used in nodes and leaves.
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	39 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	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
4658 4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	42 // 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	43 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	44 box := Box2D{
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	45 X1: math.Min(x1, x2),
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	46 Y1: math.Min(y1, y2),
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	47 X2: math.Max(x1, x2),
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	48 Y2: math.Max(y1, y2),
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
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	51 // out of bounding box
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	52 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	53 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	54 return
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
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	57 line := NewPlane2D(x1, y1, x2, y2)
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	58
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	59 vertices := s.tin.Vertices
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	60
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	61 stack := []int32{s.index[0]}
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	62
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	63 for len(stack) > 0 {
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	64 top := stack[len(stack)-1]
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	65 stack = stack[:len(stack)-1]
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	66
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	67 if top > 0 { // node
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	68 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	69 n := s.index[top+1]
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	70 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	71 }
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	72 } else { // leaf
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	73 top = -top - 1
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	74 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	75 continue
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	76 }
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	77 n := s.index[top+1]
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	78 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	79 ti := s.tin.Triangles[idx]
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	80 t := Triangle{
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	81 vertices[ti[0]],
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	82 vertices[ti[1]],
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	83 vertices[ti[2]],
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	84 }
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	85 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	86 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	87 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	88
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	89 if onPlane(v0) \|\| onPlane(v1) \|\| onPlane(v2) \|\|
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	90 sides(sides(sides(0, v0), v1), v2) == 3 {
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	91 fn(&t)
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	92 }
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	93 }
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	94 }
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	95 }
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	96 }
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	97
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	98 // Min return the minimum vertex of the TIN this tree is build from.
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	99 func (s *STRTree) Min() Vertex { return s.tin.Min }
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	100
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	101 // Max return the maximum vertex of the TIN this tree is build from.
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	102 func (s *STRTree) Max() Vertex { return s.tin.Max }
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	103
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	104 // EPSG return the EPSF code of the TIN this tree is build from.
4654 3eda5a7215ab Generate STRTrees instaead of Octree during sounding result imports. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4652 diff changeset	105 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	106
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	107 // Value returns the Z Value for a given X/Y point.
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	108 // Second return value is false if the point is out of bound.
4641 5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	109 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	110
4658 4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	111 if len(s.index) == 0 {
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	112 return 0, false
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	113 }
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	114
4641 5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	115 stack := []int32{s.index[0]}
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	116
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	117 vertices := s.tin.Vertices
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	118
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	119 for len(stack) > 0 {
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	120 top := stack[len(stack)-1]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	121 stack = stack[:len(stack)-1]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	122
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	123 if top > 0 { // node
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	124 if s.bbox(top).Contains(x, y) {
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	125 n := s.index[top+1]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	126 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	127 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	128 } else { // leaf
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	129 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	130 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	131 continue
946689a56fc2 Forgot a bbox check when evaluating STRTree speeding it significantly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	132 }
4658 4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	133 n := s.index[top+1]
4bbfe3dd2ab5 Completed usage of STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4654 diff changeset	134 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	135 ti := s.tin.Triangles[idx]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	136 t := Triangle{
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	137 vertices[ti[0]],
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	138 vertices[ti[1]],
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	139 vertices[ti[2]],
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	140 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	141 if t.Contains(x, y) {
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	142 return t.Plane3D().Z(x, y), true
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	143 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	144 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	145 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	146 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	147 return 0, false
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	148 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	149
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	150 // Build builds a tree for a given TIN.
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	151 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	152
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	153 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	154 s.Entries = STRTreeDefaultEntries
f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	155 }
f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	156
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	157 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	158
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	159 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	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 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	162 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	163 }
2768f74d54ab Added an 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 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	166
2768f74d54ab Added an 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 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	168
2768f74d54ab Added an 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 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	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
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	172 // BuildWithout builds a tree for a given TIN ignoring the triangles
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	173 // with the indices given in the remove map.
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	174 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	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 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	177 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	178 }
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 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	181
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	182 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	183
4642 b5d9647c5bc1 Fixed construction of clipped STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4641 diff changeset	184 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	185 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	186 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	187 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	188 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	189 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	190
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	191 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	192
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	193 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	194
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	195 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	196 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	197
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	198 // Clip returns the indices of the triangles of the TIN
01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	199 // which are not fully covered by the given polygon.
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	200 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	201
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	202 removed := make(map[int32]struct{})
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	203
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	204 stack := []int32{s.index[0]}
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	205
2521 e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	206 vertices := s.tin.Vertices
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	207
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	208 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	209 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	210 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	211
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	212 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	213 switch p.IntersectionBox2D(s.bbox(top)) {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	214 case IntersectionInside:
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	215 // all triangles are inside polygon
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	216 case IntersectionOutSide:
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	217 // all triangles are outside polygon
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	218 s.allTriangles(top, removed)
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	219 default:
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	220 // mixed bag
4643 a1a9b1eab57c Use append/slicing trick to simplify tree traversals. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4642 diff changeset	221 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	222 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	223 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	224 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	225 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	226 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	227 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	228 // 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	229 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	230 // 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	231 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	232 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	233 removed[idx] = struct{}{}
2521 e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	234 }
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	235 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	236 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	237 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	238 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	239 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	240 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	241 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	242 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	243 }
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	244 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	245 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	246 }
2521 e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	247 }
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	248 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	249 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	250 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	251
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	252 return removed
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	253 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	254
4646 89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	255 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	256
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	257 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	258 return err
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	259 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	260
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	261 var buf [binary.MaxVarintLen32]byte
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	262
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	263 var last int32
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	264 var written int
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	265
4650 f5fce22184da Added a deserializer from STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4647 diff changeset	266 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	267 delta := x - last
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	268 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	269 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	270 var err error
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	271 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	272 return err
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	273 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	274 written += n
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 last = x
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	277 }
4650 f5fce22184da Added a deserializer from STRTrees. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4647 diff changeset	278
5490 5f47eeea988d Use own logging package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4855 diff changeset	279 log.Infof("compressed index in bytes: %d %.2f (%d %.2f)\n",
4646 89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	280 written,
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	281 float64(written)/(1024*1024),
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	282 4*len(s.index),
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	283 float64(4len(s.index))/(10241024),
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	284 )
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	285
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	286 return nil
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	287 }
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 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	290
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	291 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	292 return err
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	293 }
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 err error
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	296
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	297 write := func(v float64) {
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	298 if err == nil {
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	299 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	300 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	301 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	302 for _, box := range s.bboxes {
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	303 write(box.X1)
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	304 write(box.Y1)
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	305 write(box.X2)
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	306 write(box.Y2)
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 return err
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	310 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	311
4855 01b593ea2311 Added missing doc strings for the STR tree in the mesh package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4827 diff changeset	312 // Bytes serializes this tree to a byte slice.
4646 89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	313 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	314
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	315 var buf bytes.Buffer
4652 f5492fda097c Use gzip best speed instead of lz4. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4650 diff changeset	316 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	317 if err != nil {
f5492fda097c Use gzip best speed instead of lz4. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4650 diff changeset	318 return nil, err
f5492fda097c Use gzip best speed instead of lz4. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4650 diff changeset	319 }
4646 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 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	322 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	323 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	324
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	325 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	326 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	327 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	328
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	329 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	330 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	331 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	332
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	333 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	334 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	335 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	336
4652 f5492fda097c Use gzip best speed instead of lz4. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4650 diff changeset	337 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	338 return nil, err
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	339 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	340
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	341 return buf.Bytes(), nil
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	342 }
89a72e0e2f9b Add a method to serialize an STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4643 diff changeset	343
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	344 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	345 stack := []int32{pos}
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	346 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	347 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	348 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	349 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	350 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	351 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	352 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	353 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	354 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	355 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	356 tris[idx] = struct{}{}
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	357 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	358 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	359 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	360 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	361
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	362 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	363 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	364 ti := s.tin.Triangles[items[i]]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	365 tj := s.tin.Triangles[items[j]]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	366 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	367 })
2768f74d54ab Added an 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 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	370 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	371
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	372 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	373
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	374 leaves := s.strJoin(
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	375 slices, S,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	376 func(i, j int32) bool {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	377 ti := s.tin.Triangles[i]
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	378 tj := s.tin.Triangles[j]
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	379 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	380 },
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	381 s.allocLeaf,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	382 )
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	383
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	384 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	385 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	386
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	387 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	388
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	389 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	390 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	391 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	392
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	393 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	394 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	395 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	396
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	397 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	398 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	399
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	400 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	401
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	402 nodes := s.strJoin(
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	403 slices, S,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	404 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	405 s.allocNode,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	406 )
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 return s.buildNodes(nodes)
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	409 }
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 func (s *STRTree) bbox(idx int32) Box2D {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	412 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	413 idx = -idx - 1
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	414 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	415 return s.bboxes[s.index[idx]]
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	416 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	417
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	418 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	419 sm := S * s.Entries
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	420 slices := make([][]int32, S)
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	421 for i := range slices {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	422 var n int
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	423 if l := len(items); l < sm {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	424 n = l
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	425 } else {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	426 n = sm
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	427 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	428 slices[i] = items[:n]
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	429 items = items[n:]
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	430 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	431 return slices
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	432 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	433
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	434 func (s *STRTree) strJoin(
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	435 slices [][]int32, S int,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	436 less func(int32, int32) bool,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	437 alloc func([]int32) int32,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	438 ) []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	439 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	440
2768f74d54ab Added an 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 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	442 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	443 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	444 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	445
2768f74d54ab Added an 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 len(slice) > 0 {
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	447 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	448 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	449 n = s.Entries
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	450 } 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	451 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	452 }
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	453 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	454 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	455 }
2768f74d54ab Added an 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 }
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	457 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	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) 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	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 {
2515 6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	465 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	466 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	467 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	468 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	469 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	470 }
2768f74d54ab Added an 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 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	472 }
2768f74d54ab Added an 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
2768f74d54ab Added an 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 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	475 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	476 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	477 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	478 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	479
2768f74d54ab Added an 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 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	481 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	482 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	483 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	484 if len(items) > 0 {
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	485 vertices := s.tin.Vertices
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	486 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	487 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	488 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	489 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	490 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	491 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	492 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	493 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	494 it := items[i]
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	495 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	496 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	497 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	498 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	499 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	500 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	501 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	502 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	503 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	504 }
2515 6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	505 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	506 }

Mercurial > gemma

annotate pkg/mesh/strtree.go @ 5591:0011f50cf216 surveysperbottleneckid