changeset 4729:1137c5a18242 stack-polygons

Virtualized point in polygon test with an interface to be usable for contours, too.
author Sascha L. Teichmann <teichmann@intevation.de>
date Thu, 17 Oct 2019 23:33:20 +0200
parents bfbdcf67ae55
children 76dbeab4a0d6
files pkg/octree/polygon.go
diffstat 1 files changed, 47 insertions(+), 27 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/octree/polygon.go	Thu Oct 17 22:37:04 2019 +0200
+++ b/pkg/octree/polygon.go	Thu Oct 17 23:33:20 2019 +0200
@@ -281,19 +281,18 @@
 
 	// 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) > 1 {
 		for _, hole := range p.rings[1:] {
-			if hole.contains(point) {
+			if contains(hole, box.X1, box.Y1) {
 				return IntersectionOutSide
 			}
 		}
 	}
 
 	// Check shell
-	if p.rings[0].contains(point) {
+	if contains(p.rings[0], box.X1, box.Y1) {
 		return IntersectionInside
 	}
 	return IntersectionOutSide
@@ -324,37 +323,59 @@
 	}
 	// No intersection -> check inside or outside
 	// if an abritrary point  is inside or not.
-	point := []float64{t[0].X, t[0].Y}
+	pX, pY := t[0].X, t[0].Y
 
 	// Check holes first: inside a hole means outside.
 	if len(p.rings) > 1 {
 		for _, hole := range p.rings[1:] {
-			if hole.contains(point) {
+			if contains(hole, pX, pY) {
 				return IntersectionOutSide
 			}
 		}
 	}
 
 	// Check shell
-	if p.rings[0].contains(point) {
+	if contains(p.rings[0], pX, pY) {
 		return IntersectionInside
 	}
 	return IntersectionOutSide
 }
 
-func (rng ring) isClosed() bool { return (len(rng) / 2) >= 3 }
+func (rng ring) closed() bool {
+	return (len(rng) / 2) >= 3
+}
+
+func (rng ring) length() int {
+	return len(rng) / 2
+}
 
-func (rng ring) contains(point []float64) bool {
-	if !rng.isClosed() {
+func (rng ring) point(i int) (float64, float64) {
+	i *= 2
+	return rng[i], rng[i+1]
+}
+
+type segments interface {
+	closed() bool
+	length() int
+	point(int) (float64, float64)
+}
+
+func contains(s segments, pX, pY float64) bool {
+	if !s.closed() {
 		return false
 	}
 
-	end := len(rng)/2 - 1
+	n := s.length()
+
+	sX, sY := s.point(0)
+	eX, eY := s.point(n - 1)
 
-	contains := intersectsWithRaycast(point, rng[:2], rng[end*2:end*2+2])
+	contains := intersectsWithRaycast(pX, pY, sX, sY, eX, eY)
 
-	for i := 2; i < len(rng); i += 2 {
-		if intersectsWithRaycast(point, rng[i-2:i], rng[i:i+2]) {
+	for i := 1; i < n; i++ {
+		sX, sY := s.point(i - 1)
+		eX, eY := s.point(i)
+		if intersectsWithRaycast(pX, pY, sX, sY, eX, eY) {
 			contains = !contains
 		}
 	}
@@ -365,46 +386,45 @@
 // Using the raycast algorithm, this returns whether or not the passed in point
 // Intersects with the edge drawn by the passed in start and end points.
 // Original implementation: http://rosettacode.org/wiki/Ray-casting_algorithm#Go
-func intersectsWithRaycast(point, start, end []float64) bool {
+func intersectsWithRaycast(pX, pY, sX, sY, eX, eY float64) bool {
 
 	// Always ensure that the the first point
 	// has a y coordinate that is less than the second point
-	if start[1] > end[1] {
+	if sY > eY {
 		// Switch the points if otherwise.
-		start, end = end, start
+		sX, sY, eX, eY = eX, eY, sX, sY
 	}
 
 	// Move the point's y coordinate
 	// outside of the bounds of the testing region
 	// so we can start drawing a ray
-	for point[1] == start[1] || point[1] == end[1] {
-		y := math.Nextafter(point[1], math.Inf(1))
-		point = []float64{point[0], y}
+	for pY == sY || pY == eY {
+		pY = math.Nextafter(pY, math.Inf(1))
 	}
 
 	// If we are outside of the polygon, indicate so.
-	if point[1] < start[1] || point[1] > end[1] {
+	if pY < sY || pY > eY {
 		return false
 	}
 
-	if start[0] > end[0] {
-		if point[0] > start[0] {
+	if sX > eX {
+		if pX > sX {
 			return false
 		}
-		if point[0] < end[0] {
+		if pX < eX {
 			return true
 		}
 	} else {
-		if point[0] > end[0] {
+		if pX > eX {
 			return false
 		}
-		if point[0] < start[0] {
+		if pX < sX {
 			return true
 		}
 	}
 
-	raySlope := (point[1] - start[1]) / (point[0] - start[0])
-	diagSlope := (end[1] - start[1]) / (end[0] - start[0])
+	raySlope := (pY - sY) / (pX - sX)
+	diagSlope := (eY - sY) / (eX - sX)
 
 	return raySlope >= diagSlope
 }