changeset 4730:76dbeab4a0d6 stack-polygons

Added a new contout type which is capable of doing a point in polygon check and use this as a second level filter in building the bbox tree.
author Sascha L. Teichmann <teichmann@intevation.de>
date Thu, 17 Oct 2019 23:56:19 +0200
parents 1137c5a18242
children dc0db4ede3b1
files pkg/octree/areas.go
diffstat 1 files changed, 43 insertions(+), 37 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/octree/areas.go	Thu Oct 17 23:33:20 2019 +0200
+++ b/pkg/octree/areas.go	Thu Oct 17 23:56:19 2019 +0200
@@ -224,7 +224,31 @@
 	return areas
 }
 
-func contourBBox(cnt contourmap.Contour) Box2D {
+type contour []contourmap.Point
+
+type bboxNode struct {
+	box      Box2D
+	cnt      contour
+	children []*bboxNode
+}
+
+type bboxForest struct {
+	roots []*bboxNode
+}
+
+func (cnt contour) closed() bool {
+	return len(cnt) >= 3
+}
+
+func (cnt contour) length() int {
+	return len(cnt)
+}
+
+func (cnt contour) point(i int) (float64, float64) {
+	return cnt[i].X, cnt[i].Y
+}
+
+func (cnt contour) bbox() Box2D {
 	minX, minY := math.MaxFloat64, math.MaxFloat64
 	maxX, maxY := -math.MaxFloat64, -math.MaxFloat64
 
@@ -245,22 +269,12 @@
 	return Box2D{X1: minX, X2: maxX, Y1: minY, Y2: maxY}
 }
 
-type bboxNode struct {
-	box      Box2D
-	cnt      contourmap.Contour
-	children []*bboxNode
-}
-
-type bboxForest struct {
-	roots []*bboxNode
-}
-
-func (bn *bboxNode) insert(cnt contourmap.Contour, box Box2D) {
-	// check if roots are inside new
+func (bn *bboxNode) insert(cnt contour, box Box2D) {
+	// check if children are inside new
 	var nr *bboxNode
 
 	for i, r := range bn.children {
-		if r.box.Inside(box) {
+		if r.box.Inside(box) && contains(cnt, r.cnt[0].X, r.cnt[0].Y) {
 			if nr == nil {
 				nr = &bboxNode{box: box, cnt: cnt}
 			}
@@ -285,31 +299,27 @@
 		return
 	}
 
-	var inserted bool
-
 	// check if new is inside an old
 	for _, r := range bn.children {
-		if box.Inside(r.box) {
+		if box.Inside(r.box) && contains(r.cnt, cnt[0].X, cnt[0].Y) {
 			r.insert(cnt, box)
-			inserted = true
+			return
 		}
 	}
 
-	// its a new root node.
-	if !inserted {
-		nr = &bboxNode{box: box, cnt: cnt}
-		bn.children = append(bn.children, nr)
-	}
+	// its a new child node.
+	nr = &bboxNode{box: box, cnt: cnt}
+	bn.children = append(bn.children, nr)
 }
 
-func (bf *bboxForest) insert(cnt contourmap.Contour) {
-	box := contourBBox(cnt)
+func (bf *bboxForest) insert(cnt contour) {
+	box := cnt.bbox()
 
 	// check if roots are inside new
 	var nr *bboxNode
 
 	for i, r := range bf.roots {
-		if r.box.Inside(box) {
+		if r.box.Inside(box) && contains(cnt, r.cnt[0].Y, r.cnt[0].Y) {
 			if nr == nil {
 				nr = &bboxNode{box: box, cnt: cnt}
 			}
@@ -334,24 +344,20 @@
 		return
 	}
 
-	var inserted bool
-
 	// check if new is inside an old
 	for _, r := range bf.roots {
-		if box.Inside(r.box) {
+		if box.Inside(r.box) && contains(r.cnt, cnt[0].X, cnt[0].Y) {
 			r.insert(cnt, box)
-			inserted = true
+			return
 		}
 	}
 
 	// its a new root node.
-	if !inserted {
-		nr = &bboxNode{box: box, cnt: cnt}
-		bf.roots = append(bf.roots, nr)
-	}
+	nr = &bboxNode{box: box, cnt: cnt}
+	bf.roots = append(bf.roots, nr)
 }
 
-type bboxOutFunc func(contourmap.Contour, []contourmap.Contour)
+type bboxOutFunc func(contour, []contourmap.Contour)
 
 func (bn *bboxNode) generate(shell bool, out bboxOutFunc) {
 	if shell && len(bn.children) == 0 {
@@ -374,14 +380,14 @@
 	var bf bboxForest
 
 	for _, cnt := range cnts {
-		bf.insert(cnt)
+		bf.insert(contour(cnt))
 	}
 
 	log.Printf("cnts: %d roots: %d\n", len(cnts), len(bf.roots))
 
 	var mp wkb.MultiPolygonGeom
 
-	out := func(sh contourmap.Contour, hls []contourmap.Contour) {
+	out := func(sh contour, hls []contourmap.Contour) {
 
 		polygon := make(wkb.PolygonGeom, 1+len(hls))