Mercurial > gemma
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))