# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1551699944 -3600
# Node ID 98bc023750cff30d72c19471f82db9f023ab6f7d
# Parent  a727e0426240cea7b0c9a8c5c606e2863324ea4c
Impelemented line segment / line segment intersection test.

diff -r a727e0426240 -r 98bc023750cf pkg/octree/polygon.go
--- 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 {