gemma: pkg/octree/strtree.go annotate

annotate pkg/octree/strtree.go @ 2516:1ec4c5633eb6 octree-diff

Clip STR tree and not Octree.

author	Sascha L. Teichmann <sascha.teichmann@intevation.de>
date	Tue, 05 Mar 2019 17:08:16 +0100
parents	6bcaa8bf2603
children	e26000628764

rev	line source
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	1 // This is Free Software under GNU Affero General Public License v >= 3.0
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	2 // without warranty, see README.md and license for details.
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	3 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	4 // SPDX-License-Identifier: AGPL-3.0-or-later
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	5 // License-Filename: LICENSES/AGPL-3.0.txt
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	6 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	7 // Copyright (C) 2018 by via donau
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	8 // – Österreichische Wasserstraßen-Gesellschaft mbH
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	9 // Software engineering by Intevation GmbH
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	10 //
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	11 // Author(s):
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	13
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	14 package octree
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	15
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	16 import (
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	17 "math"
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	18 "sort"
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	19 )
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	20
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	21 const numEntries = 8
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	22
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	23 type STRTree struct {
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	24 tin *Tin
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	25 index []int32
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	26 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	27 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	28
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	29 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	30
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	31 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	32
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	33 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	34
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	35 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	36 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	37 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	38
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	39 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	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 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	42
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	43 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	44 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	45
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	46 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	47
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	48 removed := make(map[int32]struct{})
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	49
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	50 stack := []int32{s.index[0]}
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	51
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	52 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	53 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	54 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	55
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	56 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	57 switch p.IntersectionBox2D(s.bbox(top)) {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	58 case IntersectionInside:
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	59 // all triangles are inside polygon
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	60 case IntersectionOutSide:
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	61 // all triangles are outside polygon
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	62 s.allTriangles(top, removed)
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	63 default:
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	64 // mixed bag
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	65 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	66 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	67 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	68 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	69 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	70 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	71 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	72 removed[s.index[top+2+i]] = struct{}{}
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	73 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	74 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	75 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	76
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	77 return removed
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	78 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	79
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	80 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	81 stack := []int32{pos}
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	82 for len(stack) > 0 {
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	83 top := stack[len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	84 stack = stack[:len(stack)-1]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	85 if top > 0 { // node
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	86 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	87 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	88 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	89 } else { // leaf
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	90 top = -top - 1
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	91 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	92 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	93 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	94 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	95 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	96 }
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	97
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	98 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	99 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	100 ti := s.tin.Triangles[items[i]]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	101 tj := s.tin.Triangles[items[j]]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	102 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	103 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	104
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	105 P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	106 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	107
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	108 sm := S * numEntries
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	109
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	110 slices := make([][]int32, S)
2513 1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	111 rest := items
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	112 for i := range slices {
2513 1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	113 var n int
2515 6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	114 if l := len(rest); l < sm {
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	115 n = l
2513 1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	116 } else {
1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	117 n = sm
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	118 }
2513 1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	119 slices[i] = rest[:n]
1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	120 rest = rest[n:]
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	121 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	122
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	123 leaves := make([]int32, 0, S*S)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	124
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	125 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	126 sort.Slice(slice, func(i, j int) bool {
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	127 ti := s.tin.Triangles[slice[i]]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	128 tj := s.tin.Triangles[slice[j]]
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	129 return s.tin.Vertices[ti[0]].Y < s.tin.Vertices[tj[0]].Y
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	130 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	131
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	132 for len(slice) > 0 {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	133 n := numEntries
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	134 if l := len(slice); l < numEntries {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	135 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	136 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	137 leaves = append(leaves, s.allocLeaf(slice[:n]))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	138 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	139 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	140 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	141
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	142 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	143 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	144
2515 6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	145 func (s *STRTree) bbox(idx int32) Box2D {
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	146 if idx < 0 { // Don't care if leaf or node.
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	147 idx = -idx - 1
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	148 }
2515 6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	149 return s.bboxes[s.index[idx]]
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	150 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	151
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	152 func (s *STRTree) 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	153
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	154 if len(items) <= numEntries {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	155 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	156 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	157
2768f74d54ab Added an 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 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	159 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	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
2768f74d54ab Added an 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 P := int(math.Ceil(float64(len(items)) / float64(numEntries)))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	163 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	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 sm := S * numEntries
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	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 slices := make([][]int32, S)
2513 1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	168
1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	169 rest := items
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	170 for i := range slices {
2513 1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	171 var n int
2515 6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	172 if l := len(rest); l < sm {
6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	173 n = l
2513 1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	174 } else {
1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	175 n = sm
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	176 }
2513 1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	177 slices[i] = rest[:n]
1534df518201 Called STT tree building. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2512 diff changeset	178 rest = rest[n:]
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	179 }
2768f74d54ab Added an 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 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	182
2768f74d54ab Added an 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 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	184 sort.Slice(slice, func(i, j int) bool {
2515 6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	185 return s.bbox(slice[i]).Y1 < s.bbox(slice[j]).Y1
2512 2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	186 })
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	187
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	188 for len(slice) > 0 {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	189 n := numEntries
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	190 if l := len(slice); l < numEntries {
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	191 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	192 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	193 nodes = append(nodes, s.allocNode(slice[:n]))
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	194 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	195 }
2768f74d54ab Added an 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
2768f74d54ab Added an 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 return s.buildNodes(nodes)
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	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
2768f74d54ab Added an 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 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	202 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	203 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	204 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	205 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	206 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	207 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	208 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	209 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	210 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	211 }
2768f74d54ab Added an 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 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	213 }
2768f74d54ab Added an 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
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	215 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	216 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	217 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	218 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	219 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	220
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	221 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	222 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	223 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	224 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	225 if len(items) > 0 {
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	226 vertices := s.tin.Vertices
1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	227 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	228 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	229 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	230 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	231 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	232 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	233 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	234 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	235 it := items[i]
2516 1ec4c5633eb6 Clip STR tree and not Octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2515 diff changeset	236 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	237 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	238 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	239 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	240 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	241 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	242 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	243 }
2768f74d54ab Added an STRTree for the triangulation. Should be better suited for filtering out the clipped triangles. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	244 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	245 }
2515 6bcaa8bf2603 STR tree: Fixed sorting. Stored num items per nodes. Simpified code. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2513 diff changeset	246 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	247 }

Mercurial > gemma

annotate pkg/octree/strtree.go @ 2516:1ec4c5633eb6 octree-diff