changeset 2495:98bc023750cf octree-diff

Impelemented line segment / line segment intersection test.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 04 Mar 2019 12:45:44 +0100
parents a727e0426240
children 12ed6feefea5
files pkg/octree/polygon.go
diffstat 1 files changed, 39 insertions(+), 2 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/octree/polygon.go	Mon Mar 04 12:27:56 2019 +0100
+++ b/pkg/octree/polygon.go	Mon Mar 04 12:45:44 2019 +0100
@@ -171,8 +171,45 @@
 }
 
 func (ls lineSegment) intersectsLineSegment(o lineSegment) bool {
-	// TODO: Implement me!
-	return false
+
+	p0 := ls[:2]
+	p1 := ls[2:4]
+	p2 := o[:2]
+	p3 := o[2:4]
+
+	s10x := p1[0] - p0[0]
+	s10y := p1[1] - p0[1]
+	s32x := p3[0] - p2[0]
+	s32y := p3[1] - p2[1]
+
+	den := s10x*s32y - s32x*s10y
+
+	if den == 0 {
+		return false
+	}
+
+	denPos := den > 0
+
+	s02x := p0[0] - p2[0]
+	s02y := p0[1] - p2[1]
+
+	sNum := s10x*s02y - s10y*s02x
+	if sNum < 0 == denPos {
+		return false
+	}
+
+	tNum := s32x*s02y - s32y*s02x
+	if tNum < 0 == denPos {
+		return false
+	}
+
+	if sNum > den == denPos || tNum > den == denPos {
+		return false
+	}
+
+	// t := tNum / den
+	// intersection at( p0[0] + (t * s10x), p0[1] + (t * s10y) )
+	return true
 }
 
 func (p *Polygon) IntersectionBox2D(box Box2D) IntersectionType {