gemma: pkg/octree/strtree.go annotate

annotate pkg/octree/strtree.go @ 4642:b5d9647c5bc1 stree-experiment

Fixed construction of clipped STRTree.

author	Sascha L. Teichmann <sascha.teichmann@intevation.de>
date	Fri, 11 Oct 2019 23:36:28 +0200
parents	5ef04ae34872
children	a1a9b1eab57c

rev	line source
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	1 // This is Free Software under GNU Affero General Public License v >= 3.0
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	2 // without warranty, see README.md and license for details.
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	3 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	4 // SPDX-License-Identifier: AGPL-3.0-or-later
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	5 // License-Filename: LICENSES/AGPL-3.0.txt
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	6 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	7 // Copyright (C) 2018 by via donau
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	8 // – Österreichische Wasserstraßen-Gesellschaft mbH
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	9 // Software engineering by Intevation GmbH
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	10 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	11 // Author(s):
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	13
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	14 package octree
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	15
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	16 import (
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	17 "math"
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	18 "sort"
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	19 )
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	20
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	21 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	22
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	23 type STRTree struct {
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	24 Entries int
f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	25 tin *Tin
f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	26 index []int32
f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	27 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	28 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	29
4641 5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	30 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	31
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	32 stack := []int32{s.index[0]}
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	33
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	34 vertices := s.tin.Vertices
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	35
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	36 for len(stack) > 0 {
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	37 top := stack[len(stack)-1]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	38 stack = stack[:len(stack)-1]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	39
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	40 if top > 0 { // node
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	41 if s.bbox(top).Contains(x, y) {
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	42 n := s.index[top+1]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	43 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	44 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	45 } else { // leaf
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	46 top = -top - 1
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	47 for i, n := int32(0), s.index[top+1]; i < n; i++ {
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	48 idx := s.index[top+2+i]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	49 ti := s.tin.Triangles[idx]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	50 t := Triangle{
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	51 vertices[ti[0]],
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	52 vertices[ti[1]],
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	53 vertices[ti[2]],
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	54 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	55 if t.Contains(x, y) {
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	56 return t.Plane3D().Z(x, y), true
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	57 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	58 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	59 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	60 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	61 return 0, false
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	62 }
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	63
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	64 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	65
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	66 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	67 s.Entries = STRTreeDefaultEntries
f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	68 }
f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	69
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	70 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	71
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	72 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	73
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	74 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	75 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	76 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	77
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	78 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	79
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	80 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	81
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	82 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	83 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	84
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	85 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	86
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	87 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	88 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	89 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	90
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	91 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	92
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	93 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	94
4642 b5d9647c5bc1 Fixed construction of clipped STRTree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4641 diff changeset	95 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	96 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	97 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	98 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	99 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	100 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	101
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	102 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	103
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	104 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	105
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	106 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	107 }
680f1d8802f0 STRTree: Add a builder that ignores triangles which are filtered out before. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 4591 diff changeset	108
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	109 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	110
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	111 removed := make(map[int32]struct{})
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	112
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	113 stack := []int32{s.index[0]}
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	114
2521 e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	115 vertices := s.tin.Vertices
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	116
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	117 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	118 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	119 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	120
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	121 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	122 switch p.IntersectionBox2D(s.bbox(top)) {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	123 case IntersectionInside:
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	124 // all triangles are inside polygon
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	125 case IntersectionOutSide:
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	126 // all triangles are outside polygon
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	127 s.allTriangles(top, removed)
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	128 default:
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	129 // mixed bag
4641 5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	130 // TODO slicing like:
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	131 // n := s.index[top+1]
5ef04ae34872 Used STRTree for caluculating the diff. Sascha L. Teichmann <teichmann@intevation.de> parents: 4592 diff changeset	132 // 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	133 for i, n := int32(0), s.index[top+1]; i < n; i++ {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	134 stack = append(stack, s.index[top+2+i])
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	135 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	136 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	137 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	138 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	139 for i, n := int32(0), s.index[top+1]; i < n; i++ {
2521 e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	140 idx := s.index[top+2+i]
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	141 ti := s.tin.Triangles[idx]
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	142 t := Triangle{
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	143 vertices[ti[0]],
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	144 vertices[ti[1]],
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	145 vertices[ti[2]],
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	146 }
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	147 if p.IntersectionWithTriangle(&t) != IntersectionInside {
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	148 removed[idx] = struct{}{}
e26000628764 Clip triangle in STR tree leaves correctly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	149 }
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	150 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	151 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	152 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	153
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	154 return removed
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	155 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	156
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	157 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	158 stack := []int32{pos}
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	159 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	160 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	161 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	162 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	163 for i, n := int32(0), s.index[top+1]; i < n; i++ {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	164 stack = append(stack, s.index[top+2+i])
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	165 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	166 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	167 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	168 for i, n := int32(0), s.index[top+1]; i < n; i++ {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	169 tris[s.index[top+2+i]] = struct{}{}
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	170 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	171 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	172 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	173 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	174
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	175 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	176 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	177 ti := s.tin.Triangles[items[i]]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	178 tj := s.tin.Triangles[items[j]]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	179 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	180 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	181
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	182 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	183 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	184
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	185 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	186
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	187 leaves := s.strJoin(
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	188 slices, S,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	189 func(i, j int32) bool {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	190 ti := s.tin.Triangles[i]
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	191 tj := s.tin.Triangles[j]
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	192 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	193 },
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	194 s.allocLeaf,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	195 )
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	196
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	197 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	198 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	199
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	200 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	201
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	202 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	203 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	204 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	205
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	206 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	207 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	208 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	209
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	210 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	211 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	212
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	213 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	214
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	215 nodes := s.strJoin(
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	216 slices, S,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	217 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	218 s.allocNode,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	219 )
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	220
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	221 return s.buildNodes(nodes)
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	222 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	223
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	224 func (s *STRTree) bbox(idx int32) Box2D {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	225 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	226 idx = -idx - 1
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	227 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	228 return s.bboxes[s.index[idx]]
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	229 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	230
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	231 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	232 sm := S * s.Entries
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	233 slices := make([][]int32, S)
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	234 for i := range slices {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	235 var n int
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	236 if l := len(items); l < sm {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	237 n = l
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	238 } else {
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	239 n = sm
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	240 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	241 slices[i] = items[:n]
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	242 items = items[n:]
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	243 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	244 return slices
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	245 }
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	246
4591 f456ce0a6a0e STRTree: Made number of entries per node a parameter. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2565 diff changeset	247 func (s *STRTree) strJoin(
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	248 slices [][]int32, S int,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	249 less func(int32, int32) bool,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	250 alloc func([]int32) int32,
114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	251 ) []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	252 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	253
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	254 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	255 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	256 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	257 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	258
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	259 for len(slice) > 0 {
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	260 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	261 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	262 n = s.Entries
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	263 } 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	264 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	265 }
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	266 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	267 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	268 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	269 }
2565 114979e97a6c STR tree: More code simplification. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2564 diff changeset	270 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	271 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	272
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	273 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	274 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	275 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	276 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	277 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	278 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	279 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	280 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	281 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	282 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	283 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	284 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	285 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	286
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	287 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	288 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	289 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	290 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	291 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	292
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	293 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	294 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	295 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	296 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	297 if len(items) > 0 {
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	298 vertices := s.tin.Vertices
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	299 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	300 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	301 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	302 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	303 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	304 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	305 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	306 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	307 it := items[i]
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	308 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	309 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	310 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	311 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	312 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	313 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	314 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	315 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	316 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	317 }
2515 6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	318 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	319 }

Mercurial > gemma

annotate pkg/octree/strtree.go @ 4642:b5d9647c5bc1 stree-experiment