changeset 2494:a727e0426240 octree-diff

More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 04 Mar 2019 12:27:56 +0100
parents e3487fa9284d
children 98bc023750cf
files pkg/octree/polygon.go pkg/octree/vertex.go
diffstat 2 files changed, 59 insertions(+), 4 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/octree/polygon.go	Mon Mar 04 11:56:07 2019 +0100
+++ b/pkg/octree/polygon.go	Mon Mar 04 12:27:56 2019 +0100
@@ -91,7 +91,7 @@
 	p.indices = indices
 }
 
-func (a Box2D) InterectsSegment(ls lineSegment) bool {
+func (ls lineSegment) intersects(a Box2D) bool {
 	p1x := ls[0]
 	p1y := ls[1]
 	p2x := ls[2]
@@ -170,6 +170,11 @@
 	return true
 }
 
+func (ls lineSegment) intersectsLineSegment(o lineSegment) bool {
+	// TODO: Implement me!
+	return false
+}
+
 func (p *Polygon) IntersectionBox2D(box Box2D) IntersectionType {
 
 	if len(p.rings) == 0 {
@@ -179,8 +184,7 @@
 	for _, index := range p.indices {
 		var intersects bool
 		index.Search(box, func(item rtree.Item) bool {
-			ls := item.(lineSegment)
-			if box.InterectsSegment(ls) {
+			if item.(lineSegment).intersects(box) {
 				intersects = true
 				return false
 			}
@@ -203,6 +207,8 @@
 			}
 		}
 	}
+
+	// Check shell
 	if p.rings[0].contains(point) {
 		return IntersectionInside
 	}
@@ -210,7 +216,45 @@
 }
 
 func (p *Polygon) IntersectionWithTriangle(t *Triangle) IntersectionType {
-	// TODO: Implement me
+	box := t.BBox()
+	for _, index := range p.indices {
+		var intersects bool
+		index.Search(box, func(item rtree.Item) bool {
+			ls := item.(lineSegment)
+			other := make(lineSegment, 4)
+			for i := range t {
+				other[0] = t[i].X
+				other[1] = t[i].Y
+				other[2] = t[(i+1)%len(t)].X
+				other[3] = t[(i+1)%len(t)].Y
+				if ls.intersectsLineSegment(other) {
+					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{t[0].X, t[0].Y}
+
+	// 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
+			}
+		}
+	}
+
+	// Check shell
+	if p.rings[0].contains(point) {
+		return IntersectionInside
+	}
 	return IntersectionOutSide
 }
 
--- a/pkg/octree/vertex.go	Mon Mar 04 11:56:07 2019 +0100
+++ b/pkg/octree/vertex.go	Mon Mar 04 12:27:56 2019 +0100
@@ -88,6 +88,17 @@
 	}
 }
 
+func (t *Triangle) BBox() Box2D {
+	minX := math.Min(math.Min(t[0].X, t[1].X), t[2].X)
+	maxX := math.Max(math.Max(t[0].X, t[1].X), t[2].X)
+	minY := math.Min(math.Min(t[0].Y, t[1].Y), t[2].Y)
+	maxY := math.Max(math.Max(t[0].Y, t[1].Y), t[2].Y)
+	return Box2D{
+		X1: minX, Y1: minY,
+		X2: maxX, Y2: maxY,
+	}
+}
+
 func (p Plane3D) Z(x, y float64) float64 {
 	// p.A*x + p.B*y + p.C*z + p.D = 0
 	return -(p.A*x + p.B*y + p.D) / p.C