changeset 778:9be20bd0f131

Fixed a bug with 2d planes (lines) found while working on line intersections. Added unit test.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Wed, 26 Sep 2018 13:17:32 +0200
parents f27bfc57143b
children 8ba1be486833
files pkg/octree/plane2d_test.go pkg/octree/tree.go pkg/octree/vertex.go
diffstat 3 files changed, 61 insertions(+), 6 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/pkg/octree/plane2d_test.go	Wed Sep 26 13:17:32 2018 +0200
@@ -0,0 +1,34 @@
+package octree
+
+import (
+	"math"
+	"testing"
+)
+
+func TestIntersection(t *testing.T) {
+
+	table := []struct {
+		a          [4]float64
+		b          [4]float64
+		intersects bool
+		x, y       float64
+	}{
+		{[4]float64{-1, -1, 1, 1}, [4]float64{-1, 1, 1, -1}, true, 0, 0},
+		{[4]float64{0, 0, 1, 1}, [4]float64{0, 1, 1, 0}, true, 0.5, 0.5},
+		{[4]float64{0, 0, 1, 0}, [4]float64{0, 1, 1, 1}, false, 0, 0},
+	}
+
+	for _, e := range table {
+		p1 := NewPlane2D(e.a[0], e.a[1], e.a[2], e.a[3])
+		p2 := NewPlane2D(e.b[0], e.b[1], e.b[2], e.b[3])
+		x, y, intersects := p1.Intersection(p2)
+		if intersects != e.intersects {
+			t.Fatalf("Have %t want %t\n", intersects, e.intersects)
+		}
+		if e.intersects {
+			if math.Abs(e.x-x) > epsPlane || math.Abs(e.y-y) > epsPlane {
+				t.Fatalf("Have (%f, %f)t want (%f, %f)\n", x, y, e.x, e.y)
+			}
+		}
+	}
+}
--- a/pkg/octree/tree.go	Wed Sep 26 12:44:22 2018 +0200
+++ b/pkg/octree/tree.go	Wed Sep 26 13:17:32 2018 +0200
@@ -100,8 +100,9 @@
 				v1 := line.Eval(t[1].X, t[1].Y)
 				v2 := line.Eval(t[2].X, t[2].Y)
 
-				if math.Abs(v0) < eps || math.Abs(v1) < eps ||
-					math.Abs(v2) < eps ||
+				if math.Abs(v0) < epsPlane ||
+					math.Abs(v1) < epsPlane ||
+					math.Abs(v2) < epsPlane ||
 					sides(sides(sides(0, v0), v1), v2) == 3 {
 					fn(&t)
 				}
--- a/pkg/octree/vertex.go	Wed Sep 26 12:44:22 2018 +0200
+++ b/pkg/octree/vertex.go	Wed Sep 26 13:17:32 2018 +0200
@@ -335,8 +335,8 @@
 }
 
 func NewPlane2D(x1, y1, x2, y2 float64) Plane2D {
-	a := x2 - x1
-	b := y2 - y1
+	b := x2 - x1
+	a := -(y2 - y1)
 
 	l := math.Sqrt(a*a + b*b)
 	a /= l
@@ -360,8 +360,6 @@
 	return s | 1
 }
 
-const eps = 1e-05
-
 func (a Box2D) IntersectsPlane(p Plane2D) bool {
 	var s int
 	for i := 0; i < 2; i++ {
@@ -382,3 +380,25 @@
 	//log.Printf("side: %d\n", s)
 	return false
 }
+
+func (a Vertex) Cross(b Vertex) Vertex {
+	return Vertex{
+		a.Y*b.Z - a.Z*b.Y,
+		a.Z*b.X - a.X*b.Z,
+		a.X*b.Y - a.Y*b.X,
+	}
+}
+
+func (p1 Plane2D) Intersection(p2 Plane2D) (float64, float64, bool) {
+
+	u1 := Vertex{p1.A, p1.B, p1.C}
+	u2 := Vertex{p2.A, p2.B, p2.C}
+
+	p := u1.Cross(u2)
+
+	if p.Z == 0 {
+		return 0, 0, false
+	}
+
+	return p.X / p.Z, p.Y / p.Z, true
+}