# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1551696929 -3600
# Node ID 10681749371da18bd6849d73166ef33667db891e
# Parent  c9164ff988712964b1ec4edc0e13b5967a82f16a
Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.

diff -r c9164ff98871 -r 10681749371d pkg/octree/polygon.go
--- a/pkg/octree/polygon.go	Sun Mar 03 21:10:07 2019 +0100
+++ b/pkg/octree/polygon.go	Mon Mar 04 11:55:29 2019 +0100
@@ -19,17 +19,25 @@
 	"fmt"
 	"math"
 
+	"github.com/tidwall/rtree"
+
 	"gemma.intevation.de/gemma/pkg/wkb"
 )
 
-type ring []float64
+type (
+	ring []float64
+
+	Polygon struct {
+		// TODO: Implement me!
+		rings []ring
 
-type Polygon struct {
-	// TODO: Implement me!
-	rings []ring
-}
+		indices []*rtree.RTree
+	}
 
-type IntersectionType byte
+	IntersectionType byte
+
+	lineSegment []float64
+)
 
 const (
 	IntersectionInside IntersectionType = iota
@@ -37,8 +45,167 @@
 	IntersectionOverlaps
 )
 
+func (ls lineSegment) Rect(interface{}) ([]float64, []float64) {
+
+	var min, max [2]float64
+
+	if ls[0] < ls[2] {
+		min[0] = ls[0]
+		max[0] = ls[2]
+	} else {
+		min[0] = ls[2]
+		max[0] = ls[0]
+	}
+
+	if ls[1] < ls[3] {
+		min[1] = ls[1]
+		max[1] = ls[3]
+	} else {
+		min[1] = ls[3]
+		max[1] = ls[1]
+	}
+
+	return min[:], max[:]
+}
+
+func (p *Polygon) Indexify() {
+	indices := make([]*rtree.RTree, len(p.rings))
+
+	for i := range indices {
+		index := rtree.New(nil)
+		indices[i] = index
+
+		rng := p.rings[i]
+
+		for i := 0; i < len(rng); i += 2 {
+			var ls lineSegment
+			if i+4 <= len(rng) {
+				ls = lineSegment(rng[i : i+4])
+			} else {
+				ls = []float64{rng[i], rng[i+1], rng[0], rng[1]}
+			}
+			index.Insert(ls)
+		}
+	}
+
+	p.indices = indices
+}
+
+func (a Box2D) InterectsSegment(ls lineSegment) bool {
+	p1x := ls[0]
+	p1y := ls[1]
+	p2x := ls[2]
+	p2y := ls[3]
+
+	left := a.X1
+	right := a.X2
+	top := a.Y1
+	bottom := a.Y2
+
+	// The direction of the ray
+	dx := p2x - p1x
+	dy := p2y - p1y
+
+	min, max := 0.0, 1.0
+
+	var t0, t1 float64
+
+	// Left and right sides.
+	// - If the line is parallel to the y axis.
+	if dx == 0 {
+		if p1x < left || p1x > right {
+			return false
+		}
+	} else {
+		// - Make sure t0 holds the smaller value by checking the direction of the line.
+		if dx > 0 {
+			t0 = (left - p1x) / dx
+			t1 = (right - p1x) / dx
+		} else {
+			t1 = (left - p1x) / dx
+			t0 = (right - p1x) / dx
+		}
+
+		if t0 > min {
+			min = t0
+		}
+		if t1 < max {
+			max = t1
+		}
+		if min > max || max < 0 {
+			return false
+		}
+	}
+
+	// The top and bottom side.
+	// - If the line is parallel to the x axis.
+	if dy == 0 {
+		if p1y < top || p1y > bottom {
+			return false
+		}
+	} else {
+		// - Make sure t0 holds the smaller value by checking the direction of the line.
+		if dy > 0 {
+			t0 = (top - p1y) / dy
+			t1 = (bottom - p1y) / dy
+		} else {
+			t1 = (top - p1y) / dy
+			t0 = (bottom - p1y) / dy
+		}
+
+		if t0 > min {
+			min = t0
+		}
+		if t1 < max {
+			max = t1
+		}
+		if min > max || max < 0 {
+			return false
+		}
+	}
+
+	// The point of intersection
+	// ix = p1x + dx*min
+	// iy = p1y + dy*min
+	return true
+}
+
 func (p *Polygon) IntersectionBox2D(box Box2D) IntersectionType {
-	// TODO: Implement me
+
+	if len(p.rings) == 0 {
+		return IntersectionOutSide
+	}
+
+	for _, index := range p.indices {
+		var intersects bool
+		index.Search(box, func(item rtree.Item) bool {
+			ls := item.(lineSegment)
+			if box.InterectsSegment(ls) {
+				intersects = true
+				return false
+			}
+			return true
+		})
+		if intersects {
+			return IntersectionOverlaps
+		}
+	}
+
+	// No intersection -> check inside or outside
+	// if an abritrary point  is inside or not.
+	point := []float64{box.X1, box.Y1}
+
+	// Check holes first: inside a hole means outside.
+	if len(p.rings) > 0 {
+		for _, hole := range p.rings[1:] {
+			if hole.contains(point) {
+				return IntersectionOutSide
+			}
+		}
+	}
+	if p.rings[0].contains(point) {
+		return IntersectionInside
+	}
 	return IntersectionOutSide
 }
 
diff -r c9164ff98871 -r 10681749371d pkg/octree/vertex.go
--- a/pkg/octree/vertex.go	Sun Mar 03 21:10:07 2019 +0100
+++ b/pkg/octree/vertex.go	Mon Mar 04 11:55:29 2019 +0100
@@ -681,6 +681,10 @@
 	return out
 }
 
+func (a Box2D) Rect(interface{}) ([]float64, []float64) {
+	return []float64{a.X1, a.Y1}, []float64{a.X2, a.Y2}
+}
+
 // Intersects checks if two Box2Ds intersect.
 func (a Box2D) Intersects(b Box2D) bool {
 	return !(a.X2 < a.X1 || a.X2 < b.X1 ||