gemma: pkg/octree/tree.go annotate

annotate pkg/octree/tree.go @ 4488:bff6c5c1db4f

client: pdf-gen: improve adding bottleneck info to pdf * Check if the bottleneck is in the current view to add its info to the exported pdf and the pdf filename, this avoid wrong filename and wrong info in pdf in case view has been changed to another location. * Set the bottleneck to print after moving to it in map.

author	Fadi Abbud <fadi.abbud@intevation.de>
date	Fri, 27 Sep 2019 11:15:02 +0200
parents	d12c2f4d3483
children	8f745c353784

rev	line source
1017 a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	1 // This is Free Software under GNU Affero General Public License v >= 3.0
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	2 // without warranty, see README.md and license for details.
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	3 //
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	4 // SPDX-License-Identifier: AGPL-3.0-or-later
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	5 // License-Filename: LICENSES/AGPL-3.0.txt
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	6 //
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	7 // Copyright (C) 2018 by via donau
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	8 // – Österreichische Wasserstraßen-Gesellschaft mbH
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	9 // Software engineering by Intevation GmbH
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	10 //
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	11 // Author(s):
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
a244b18cb916 Added GNU Affero General Public License. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 787 diff changeset	13
727 41c8dc61f38f Moved octree loading stuff to octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 726 diff changeset	14 package octree
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	15
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	16 import (
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	17 "math"
3655 a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	18 "runtime"
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	19 "sync"
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	20
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	21 "gemma.intevation.de/gemma/pkg/common"
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	22 )
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	23
1692 f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1017 diff changeset	24 // Tree is an Octree holding triangles.
727 41c8dc61f38f Moved octree loading stuff to octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 726 diff changeset	25 type Tree struct {
1692 f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1017 diff changeset	26 // EPSG is the projection.
726 5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 707 diff changeset	27 EPSG uint32
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	28
726 5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 707 diff changeset	29 vertices []Vertex
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	30 triangles [][]int32
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	31 index []int32
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	32
1692 f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1017 diff changeset	33 // Min is the lower left corner of the bbox.
726 5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 707 diff changeset	34 Min Vertex
1692 f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1017 diff changeset	35 // Max is the upper right corner of the bbox.
726 5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 707 diff changeset	36 Max Vertex
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	37 }
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	38
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	39 type boxFrame struct {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	40 pos int32
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	41 Box2D
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	42 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	43
2466 a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	44 func (ot *Tree) Vertices() []Vertex {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	45 return ot.vertices
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	46 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	47
759 46fe2ae761e8 Check bounding boxes against plane, too. WIP Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 758 diff changeset	48 var scale = [4][4]float64{
46fe2ae761e8 Check bounding boxes against plane, too. WIP Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 758 diff changeset	49 {0.0, 0.0, 0.5, 0.5},
46fe2ae761e8 Check bounding boxes against plane, too. WIP Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 758 diff changeset	50 {0.5, 0.0, 1.0, 0.5},
46fe2ae761e8 Check bounding boxes against plane, too. WIP Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 758 diff changeset	51 {0.0, 0.5, 0.5, 1.0},
46fe2ae761e8 Check bounding boxes against plane, too. WIP Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 758 diff changeset	52 {0.5, 0.5, 1.0, 1.0},
46fe2ae761e8 Check bounding boxes against plane, too. WIP Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 758 diff changeset	53 }
46fe2ae761e8 Check bounding boxes against plane, too. WIP Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 758 diff changeset	54
2466 a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	55 func (ot *Tree) Value(x, y float64) (float64, bool) {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	56
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	57 // out of bounding box
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	58 if x < ot.Min.X \|\| ot.Max.X < x \|\|
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	59 y < ot.Min.Y \|\| ot.Max.Y < y {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	60 return 0, false
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	61 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	62
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	63 all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	64
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	65 stack := []boxFrame{{1, all}}
2466 a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	66
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	67 for len(stack) > 0 {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	68 top := stack[len(stack)-1]
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	69 stack = stack[:len(stack)-1]
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	70
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	71 if top.pos > 0 { // node
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	72 if index := ot.index[top.pos:]; len(index) > 7 {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	73 for i := 0; i < 4; i++ {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	74 a := index[i]
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	75 b := index[i+4]
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	76 if a == 0 && b == 0 {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	77 continue
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	78 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	79 dx := top.X2 - top.X1
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	80 dy := top.Y2 - top.Y1
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	81 nbox := Box2D{
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	82 dx*scale[i][0] + top.X1,
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	83 dy*scale[i][1] + top.Y1,
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	84 dx*scale[i][2] + top.X1,
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	85 dy*scale[i][3] + top.Y1,
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	86 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	87 if nbox.Contains(x, y) {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	88 if a != 0 {
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	89 stack = append(stack, boxFrame{a, nbox})
2466 a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	90 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	91 if b != 0 {
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	92 stack = append(stack, boxFrame{b, nbox})
2466 a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	93 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	94 break
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	95 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	96 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	97 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	98 } else { // leaf
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	99 pos := -top.pos - 1
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	100 n := ot.index[pos]
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	101 indices := ot.index[pos+1 : pos+1+n]
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	102
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	103 for _, idx := range indices {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	104 tri := ot.triangles[idx]
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	105 t := Triangle{
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	106 ot.vertices[tri[0]],
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	107 ot.vertices[tri[1]],
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	108 ot.vertices[tri[2]],
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	109 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	110 if t.Contains(x, y) {
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	111 return t.Plane3D().Z(x, y), true
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	112 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	113 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	114 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	115 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	116
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	117 return 0, false
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	118 }
a1e751c08c56 Calculate difference on single core. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1790 diff changeset	119
1692 f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1017 diff changeset	120 // Vertical does a vertical cross cut from (x1, y1) to (x2, y2).
755 1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	121 func (ot Tree) Vertical(x1, y1, x2, y2 float64, fn func(Triangle)) {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	122
774 c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	123 box := Box2D{
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	124 X1: math.Min(x1, x2),
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	125 Y1: math.Min(y1, y2),
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	126 X2: math.Max(x1, x2),
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	127 Y2: math.Max(y1, y2),
755 1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	128 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	129
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	130 // out of bounding box
774 c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	131 if box.X2 < ot.Min.X \|\| ot.Max.X < box.X1 \|\|
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	132 box.Y2 < ot.Min.Y \|\| ot.Max.Y < box.Y1 {
755 1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	133 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	134 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	135
774 c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	136 line := NewPlane2D(x1, y1, x2, y2)
756 5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	137
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	138 dupes := map[int32]struct{}{}
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	139
774 c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	140 all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}
761 033975d49c90 Removed a bit debug output on vertical traversal of octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 760 diff changeset	141 //log.Printf("area: %f\n", (box.x2-box.x1)*(box.y2-box.y1))
033975d49c90 Removed a bit debug output on vertical traversal of octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 760 diff changeset	142 //log.Printf("all: %f\n", (all.x2-all.x1)*(all.y2-all.y1))
758 0f3ba8bfa641 Simplified vertical traversal of octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 757 diff changeset	143
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	144 stack := []boxFrame{{1, all}}
755 1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	145
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	146 for len(stack) > 0 {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	147 top := stack[len(stack)-1]
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	148 stack = stack[:len(stack)-1]
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	149
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	150 if top.pos > 0 { // node
1790 fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	151 if index := ot.index[top.pos:]; len(index) > 7 {
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	152 for i := 0; i < 4; i++ {
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	153 a := index[i]
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	154 b := index[i+4]
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	155 if a == 0 && b == 0 {
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	156 continue
758 0f3ba8bfa641 Simplified vertical traversal of octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 757 diff changeset	157 }
1790 fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	158 dx := top.X2 - top.X1
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	159 dy := top.Y2 - top.Y1
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	160 nbox := Box2D{
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	161 dx*scale[i][0] + top.X1,
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	162 dy*scale[i][1] + top.Y1,
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	163 dx*scale[i][2] + top.X1,
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	164 dy*scale[i][3] + top.Y1,
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	165 }
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	166 if nbox.Intersects(box) && nbox.IntersectsPlane(line) {
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	167 if a != 0 {
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	168 stack = append(stack, boxFrame{a, nbox})
1790 fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	169 }
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	170 if b != 0 {
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2479 diff changeset	171 stack = append(stack, boxFrame{b, nbox})
1790 fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1788 diff changeset	172 }
755 1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	173 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	174 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	175 }
756 5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	176 } else { // leaf
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	177 pos := -top.pos - 1
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	178 n := ot.index[pos]
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	179 indices := ot.index[pos+1 : pos+1+n]
755 1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	180
756 5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	181 for _, idx := range indices {
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	182 if _, found := dupes[idx]; found {
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	183 continue
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	184 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	185 tri := ot.triangles[idx]
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	186 t := Triangle{
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	187 ot.vertices[tri[0]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	188 ot.vertices[tri[1]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	189 ot.vertices[tri[2]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	190 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	191
774 c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	192 v0 := line.Eval(t[0].X, t[0].Y)
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	193 v1 := line.Eval(t[1].X, t[1].Y)
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 761 diff changeset	194 v2 := line.Eval(t[2].X, t[2].Y)
756 5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	195
787 3d927e06b92c Triangle intersection. WIP. Currently interpolation is messed up. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 778 diff changeset	196 if onPlane(v0) \|\| onPlane(v1) \|\| onPlane(v2) \|\|
759 46fe2ae761e8 Check bounding boxes against plane, too. WIP Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 758 diff changeset	197 sides(sides(sides(0, v0), v1), v2) == 3 {
756 5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	198 fn(&t)
5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	199 }
758 0f3ba8bfa641 Simplified vertical traversal of octree. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 757 diff changeset	200 dupes[idx] = struct{}{}
756 5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	201 }
755 1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	202 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	203 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	204 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	205
1692 f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1017 diff changeset	206 // Horizontal does a horizontal cross cut.
727 41c8dc61f38f Moved octree loading stuff to octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 726 diff changeset	207 func (ot Tree) Horizontal(h float64, fn func(Triangle)) {
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	208
755 1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	209 if h < ot.Min.Z \|\| ot.Max.Z < h {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	210 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	211 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 728 diff changeset	212
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	213 type frame struct {
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	214 pos int32
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	215 min float64
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	216 max float64
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	217 }
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	218
756 5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	219 dupes := map[int32]struct{}{}
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	220
756 5e14000829d1 Complete vertical octree traversal. Seems not very selective. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 755 diff changeset	221 stack := []frame{{1, ot.Min.Z, ot.Max.Z}}
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	222
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	223 for len(stack) > 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	224 top := stack[len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	225 stack = stack[:len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	226
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	227 pos := top.pos
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	228 if pos == 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	229 continue
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	230 }
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	231 min, max := top.min, top.max
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	232
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	233 if pos > 0 { // node
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	234 if mid := (max-min)*0.5 + min; h >= mid {
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	235 pos += 4 // nodes with z-bit set
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	236 min = mid
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	237 } else {
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	238 max = mid
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	239 }
2479 c85b16db8a02 Calculate better triangulation and store it into database. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2466 diff changeset	240 if pos < int32(len(ot.index)) {
c85b16db8a02 Calculate better triangulation and store it into database. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2466 diff changeset	241 if index := ot.index[pos:]; len(index) > 3 {
c85b16db8a02 Calculate better triangulation and store it into database. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2466 diff changeset	242 stack = append(stack,
c85b16db8a02 Calculate better triangulation and store it into database. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2466 diff changeset	243 frame{index[0], min, max},
c85b16db8a02 Calculate better triangulation and store it into database. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2466 diff changeset	244 frame{index[1], min, max},
c85b16db8a02 Calculate better triangulation and store it into database. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2466 diff changeset	245 frame{index[2], min, max},
c85b16db8a02 Calculate better triangulation and store it into database. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2466 diff changeset	246 frame{index[3], min, max})
c85b16db8a02 Calculate better triangulation and store it into database. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2466 diff changeset	247 }
1788 00f34a00e6d5 Octree: Don't crash in horizontal traversal if the tree is empty. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 1692 diff changeset	248 }
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	249 } else { // leaf
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	250 pos = -pos - 1
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	251 n := ot.index[pos]
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	252 //log.Printf("%d %d %d\n", pos, n, len(ot.index))
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	253 indices := ot.index[pos+1 : pos+1+n]
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	254
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	255 for _, idx := range indices {
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	256 if _, found := dupes[idx]; found {
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	257 continue
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	258 }
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	259 tri := ot.triangles[idx]
726 5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 707 diff changeset	260 t := Triangle{
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	261 ot.vertices[tri[0]],
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	262 ot.vertices[tri[1]],
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	263 ot.vertices[tri[2]],
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	264 }
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	265
727 41c8dc61f38f Moved octree loading stuff to octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 726 diff changeset	266 if !(math.Min(t[0].Z, math.Min(t[1].Z, t[2].Z)) > h \|\|
41c8dc61f38f Moved octree loading stuff to octree package. Sascha L. Teichmann <teichmann@intevation.de> parents: 726 diff changeset	267 math.Max(t[0].Z, math.Max(t[1].Z, t[2].Z)) < h) {
707 9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	268 dupes[idx] = struct{}{}
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	269 fn(&t)
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	270 }
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	271 }
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	272 }
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	273 }
9db4ae29ded9 octree: Moved octree traveral code to own file. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	274 }
2572 7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	275
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	276 func (ot Tree) Diff(other Tree) PointMap {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	277
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	278 firstVs, secondVs := ot.Vertices(), other.Vertices()
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	279
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	280 result := make(PointMap, len(firstVs)+len(secondVs))
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	281
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	282 sliceWork(
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	283 firstVs,
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	284 result,
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	285 func(slice []Vertex, turn func([]Vertex) []Vertex) {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	286 p := turn(nil)
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	287 for i := range slice {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	288 v := &slice[i]
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	289 if z, found := other.Value(v.X, v.Y); found {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	290 p = append(p, Vertex{v.X, v.Y, v.Z - z})
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	291 if len(p) == cap(p) {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	292 p = turn(p)
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	293 }
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	294 }
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	295 }
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	296 if len(p) > 0 {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	297 turn(p)
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	298 }
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	299 })
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	300
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	301 sliceWork(
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	302 secondVs,
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	303 result,
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	304 func(
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	305 slice []Vertex, turn func([]Vertex) []Vertex) {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	306 p := turn(nil)
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	307 for i := range slice {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	308 v := &slice[i]
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	309 if z, found := ot.Value(v.X, v.Y); found {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	310 p = append(p, Vertex{v.X, v.Y, z - v.Z})
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	311 if len(p) == cap(p) {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	312 p = turn(p)
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	313 }
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	314 }
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	315 }
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	316 if len(p) > 0 {
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	317 turn(p)
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	318 }
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	319 })
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	320
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	321 return result
7686c7c23506 Morphological differences: Moved some code into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2516 diff changeset	322 }
3655 a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	323
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3655 diff changeset	324 func (ot *Tree) GenerateRandomVertices(n int, callback func([]Vertex)) {
3655 a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	325 var wg sync.WaitGroup
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	326
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	327 jobs := make(chan int)
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	328 out := make(chan []Vertex)
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	329 done := make(chan struct{})
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	330
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	331 cpus := runtime.NumCPU()
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	332
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	333 free := make(chan []Vertex, cpus)
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	334
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	335 for i := 0; i < cpus; i++ {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	336 wg.Add(1)
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	337 go func() {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	338 defer wg.Done()
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3655 diff changeset	339 xRange := common.Random(ot.Min.X, ot.Max.X)
d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3655 diff changeset	340 yRange := common.Random(ot.Min.Y, ot.Max.Y)
3655 a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	341
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	342 for size := range jobs {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	343 var vertices []Vertex
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	344 select {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	345 case vertices = <-free:
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	346 default:
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	347 vertices = make([]Vertex, 0, 1000)
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	348 }
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	349 for len(vertices) < size {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	350 x, y := xRange(), yRange()
4151 d12c2f4d3483 Made 'golint' more happy with the octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 3655 diff changeset	351 if z, ok := ot.Value(x, y); ok {
3655 a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	352 vertices = append(vertices, Vertex{X: x, Y: y, Z: z})
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	353 }
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	354 }
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	355 out <- vertices
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	356 }
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	357 }()
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	358 }
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	359
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	360 go func() {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	361 defer close(done)
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	362 for vertices := range out {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	363 callback(vertices)
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	364 select {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	365 case free <- vertices[:0]:
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	366 default:
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	367 }
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	368 }
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	369 }()
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	370
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	371 for remain := n; remain > 0; {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	372 if remain > 1000 {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	373 jobs <- 1000
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	374 remain -= 1000
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	375 } else {
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	376 jobs <- remain
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	377 remain = 0
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	378 }
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	379 }
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	380 close(jobs)
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	381 wg.Wait()
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	382 close(out)
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	383 <-done
a6c671abbc35 Started with cleaning up the single beam import. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2572 diff changeset	384 }

Mercurial > gemma

annotate pkg/octree/tree.go @ 4488:bff6c5c1db4f