Mercurial > gemma
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{}{} + } } } }