changeset 4703:6e179b338f1a

STRTree: Improve usage of bounding boxes in leaves of the tree. Speeds stuff 10x up.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Wed, 16 Oct 2019 18:03:24 +0200
parents ef21c1464843
children 9eb708176b43
files pkg/octree/strtree.go
diffstat 1 files changed, 20 insertions(+), 9 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/octree/strtree.go	Wed Oct 16 17:35:25 2019 +0200
+++ b/pkg/octree/strtree.go	Wed Oct 16 18:03:24 2019 +0200
@@ -204,16 +204,27 @@
 			}
 		} else { // leaf
 			top = -top - 1
-			for i, n := int32(0), s.index[top+1]; i < n; i++ {
-				idx := s.index[top+2+i]
-				ti := s.tin.Triangles[idx]
-				t := Triangle{
-					vertices[ti[0]],
-					vertices[ti[1]],
-					vertices[ti[2]],
+			switch p.IntersectionBox2D(s.bbox(top)) {
+			case IntersectionInside:
+				// all triangles are inside polygon
+			case IntersectionOutSide:
+				// all triangles are outside polygon
+				n := s.index[top+1]
+				for _, idx := range s.index[top+2 : top+2+n] {
+					removed[idx] = struct{}{}
 				}
-				if p.IntersectionWithTriangle(&t) != IntersectionInside {
-					removed[idx] = struct{}{}
+			default:
+				n := s.index[top+1]
+				for _, idx := range s.index[top+2 : top+2+n] {
+					ti := s.tin.Triangles[idx]
+					t := Triangle{
+						vertices[ti[0]],
+						vertices[ti[1]],
+						vertices[ti[2]],
+					}
+					if p.IntersectionWithTriangle(&t) != IntersectionInside {
+						removed[idx] = struct{}{}
+					}
 				}
 			}
 		}