gemma: pkg/mesh/strtree.go annotate

annotate pkg/mesh/strtree.go @ 5670:b75d0b303328

Various fixes and improvements of gauges import: - Allow update of erased data (and thereby set erased to false) - Fix source_organization to work with ERDMS2 - Give ISRS of new and updated gauges in summary - Fixed reference of null pointers if revlevels are missing - Fixed reference of null pointer on update errors - Added ISRS to reference_code warning

author	Sascha Wilde <wilde@sha-bang.de>
date	Fri, 08 Dec 2023 17:29:56 +0100
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 @ 5670:b75d0b303328