diff pkg/octree/tree.go @ 2466:a1e751c08c56 octree-diff

Calculate difference on single core.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 25 Feb 2019 18:21:33 +0100
parents fe1aa62195c2
children c85b16db8a02
line wrap: on
line diff
--- a/pkg/octree/tree.go	Mon Feb 25 17:02:33 2019 +0100
+++ b/pkg/octree/tree.go	Mon Feb 25 18:21:33 2019 +0100
@@ -32,6 +32,10 @@
 	Max Vertex
 }
 
+func (ot *Tree) Vertices() []Vertex {
+	return ot.vertices
+}
+
 var scale = [4][4]float64{
 	{0.0, 0.0, 0.5, 0.5},
 	{0.5, 0.0, 1.0, 0.5},
@@ -39,6 +43,76 @@
 	{0.5, 0.5, 1.0, 1.0},
 }
 
+func (ot *Tree) Value(x, y float64) (float64, bool) {
+
+	// out of bounding box
+	if x < ot.Min.X || ot.Max.X < x ||
+		y < ot.Min.Y || ot.Max.Y < y {
+		return 0, false
+	}
+
+	type frame struct {
+		pos int32
+		Box2D
+	}
+
+	all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}
+
+	stack := []frame{{1, all}}
+
+	for len(stack) > 0 {
+		top := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+
+		if top.pos > 0 { // node
+			if index := ot.index[top.pos:]; len(index) > 7 {
+				for i := 0; i < 4; i++ {
+					a := index[i]
+					b := index[i+4]
+					if a == 0 && b == 0 {
+						continue
+					}
+					dx := top.X2 - top.X1
+					dy := top.Y2 - top.Y1
+					nbox := Box2D{
+						dx*scale[i][0] + top.X1,
+						dy*scale[i][1] + top.Y1,
+						dx*scale[i][2] + top.X1,
+						dy*scale[i][3] + top.Y1,
+					}
+					if nbox.Contains(x, y) {
+						if a != 0 {
+							stack = append(stack, frame{a, nbox})
+						}
+						if b != 0 {
+							stack = append(stack, frame{b, nbox})
+						}
+						break
+					}
+				}
+			}
+		} else { // leaf
+			pos := -top.pos - 1
+			n := ot.index[pos]
+			indices := ot.index[pos+1 : pos+1+n]
+
+			for _, idx := range indices {
+				tri := ot.triangles[idx]
+				t := Triangle{
+					ot.vertices[tri[0]],
+					ot.vertices[tri[1]],
+					ot.vertices[tri[2]],
+				}
+				if t.Contains(x, y) {
+					return t.Plane3D().Z(x, y), true
+				}
+			}
+		}
+	}
+
+	return 0, false
+}
+
 // Vertical does a vertical cross cut from (x1, y1) to (x2, y2).
 func (ot *Tree) Vertical(x1, y1, x2, y2 float64, fn func(*Triangle)) {