Mercurial > gemma
diff pkg/octree/tree.go @ 2516:1ec4c5633eb6 octree-diff
Clip STR tree and not Octree.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Tue, 05 Mar 2019 17:08:16 +0100 |
parents | e0a7571ac13a |
children | 7686c7c23506 |
line wrap: on
line diff
--- a/pkg/octree/tree.go Tue Mar 05 15:55:14 2019 +0100 +++ b/pkg/octree/tree.go Tue Mar 05 17:08:16 2019 +0100 @@ -14,10 +14,7 @@ package octree import ( - "fmt" - "log" "math" - "os" ) // Tree is an Octree holding triangles. @@ -51,317 +48,6 @@ {0.5, 0.5, 1.0, 1.0}, } -func (ot *Tree) Dump() error { - fake, err := os.Create("/tmp/dump.geojson") - if err != nil { - return err - } - defer fake.Close() - - fmt.Fprintln(fake, - `{ -"crs": { - "type": "name", - "properties": { - "name": "urn:ogc:def:crs:EPSG::32633" - } - }, - - "type": "FeatureCollection", - "features": [`) - - first := true - - already := make(map[int32]struct{}) - - stack := []int32{1} - for len(stack) > 0 { - pos := stack[len(stack)-1] - stack = stack[:len(stack)-1] - - if pos > 0 { // node - index := ot.index[pos:] - if len(index) > 8 { - index = index[:8] - } - for i := range index { - if index[i] != 0 { - stack = append(stack, index[i]) - } - } - } else { - pos = -pos - 1 - n := ot.index[pos] - indices := ot.index[pos+1 : pos+1+n] - for _, index := range indices { - if _, found := already[index]; found { - continue - } - already[index] = struct{}{} - tri := ot.triangles[index] - t := Triangle{ - ot.vertices[tri[0]], - ot.vertices[tri[1]], - ot.vertices[tri[2]], - } - if first { - first = false - } else { - fmt.Fprintln(fake, ",") - } - fmt.Fprintf(fake, - `{ "type": "Feature", - "properties": { - "id": %d - }, - "geometry": { - "type": "Polygon", - "coordinates": [[ - [ %.6f, %.6f ], - [ %.6f, %.6f ], - [ %.6f, %.6f ], - [ %.6f, %.6f ]] - ] - } -}`, index, - t[0].X, t[0].Y, - t[1].X, t[1].Y, - t[2].X, t[2].Y, - t[0].X, t[0].Y) - } - } - } - - fmt.Fprintln(fake, - `] -}`) - return nil -} - -func (ot *Tree) eliminate(removed map[int32]IntersectionType) { - - var bad int - - stack := []int32{1} - for len(stack) > 0 { - pos := stack[len(stack)-1] - stack = stack[:len(stack)-1] - - if pos > 0 { // node - index := ot.index[pos:] - if len(index) > 8 { - index = index[:8] - } - for i := range index { - if index[i] != 0 { - stack = append(stack, index[i]) - } - } - } else { - pos = -pos - 1 - n := ot.index[pos] - indices := ot.index[pos+1 : pos+1+n] - - for i := len(indices) - 1; i >= 0; i-- { - index := indices[i] - if t, found := removed[index]; found && t != IntersectionInside { - if i < len(indices)-1 { - copy(indices[i:], indices[i+1:]) - } - indices[len(indices)-1] = 0 - indices = indices[:len(indices)-1] - bad++ - } - } - ot.index[pos] = int32(len(indices)) - } - } - - log.Printf("bad triangles: %d\n", bad) -} - -func (ot *Tree) Clip(p *Polygon) { - - /* - fake, _ := os.Create("/tmp/removed.geojson") - defer fake.Close() - - fmt.Fprintln(fake, - `{ - "crs": { - "type": "name", - "properties": { - "name": "urn:ogc:def:crs:EPSG::32633" - } - }, - - "type": "FeatureCollection", - "features": [`) - - first := true - */ - - log.Printf("info: num triangles: %d\n", len(ot.triangles)) - - all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y} - - stack := []boxFrame{{1, all}} - - triChecks := make(map[int32]IntersectionType) - - var nodeTests int - var nodesClipped int - var trianglesClipped int - var nodesAllInside int - -frames: - for len(stack) > 0 { - top := stack[len(stack)-1] - stack = stack[:len(stack)-1] - - if top.pos > 0 { // node - nodeTests++ - switch p.IntersectionBox2D(top.Box2D) { - case IntersectionInside: - // all inside so nothing to clip. - nodesAllInside++ - continue frames - case IntersectionOutSide: - // all outside -> clip from tree. - index := ot.index[top.pos:] - if len(index) > 8 { - index = index[:8] - } - for i := range index { - if index[i] != 0 { - index[i] = 0 - nodesClipped++ - } - } - continue frames - default: // Overlaps - if index := ot.index[top.pos:]; len(index) > 7 { - children: - for i := 0; i < 4; i++ { - a := index[i] - b := index[i+4] - if a == 0 && b == 0 { - continue - } - dx := top.X2 - top.X1 - dy := top.Y2 - top.Y1 - nbox := Box2D{ - dx*scale[i][0] + top.X1, - dy*scale[i][1] + top.Y1, - dx*scale[i][2] + top.X1, - dy*scale[i][3] + top.Y1, - } - switch p.IntersectionBox2D(nbox) { - case IntersectionInside: - // all inside so nothing to clip. - nodesAllInside++ - continue children - case IntersectionOutSide: - // all are ouside -> clip from tree. - if a != 0 { - index[i] = 0 - nodesClipped++ - } - if b != 0 { - index[i+4] = 0 - nodesClipped++ - } - continue children - default: // Overlaps - if a != 0 { - stack = append(stack, boxFrame{a, nbox}) - } - if b != 0 { - stack = append(stack, boxFrame{b, nbox}) - } - } - } - } - } - } else { // leaf - pos := -top.pos - 1 - n := ot.index[pos] - indices := ot.index[pos+1 : pos+1+n] - tris: - for i := len(indices) - 1; i >= 0; i-- { - triIndex := indices[i] - what, found := triChecks[triIndex] - if !found { - tri := ot.triangles[triIndex] - t := Triangle{ - ot.vertices[tri[0]], - ot.vertices[tri[1]], - ot.vertices[tri[2]], - } - what = p.IntersectionWithTriangle(&t) - triChecks[triIndex] = what - - /* - - if what != IntersectionInside { - if first { - first = false - } else { - fmt.Fprintln(fake, ",") - } - fmt.Fprintf(fake, - `{ "type": "Feature", - "properties": { - "id": %d - }, - "geometry": { - "type": "Polygon", - "coordinates": [[ - [ %.6f, %.6f ], - [ %.6f, %.6f ], - [ %.6f, %.6f ], - [ %.6f, %.6f ]] - ] - } - }`, triIndex, - t[0].X, t[0].Y, - t[1].X, t[1].Y, - t[2].X, t[2].Y, - t[0].X, t[0].Y) - } - */ - } - switch what { - case IntersectionInside: - // triangle inside -> stay. - continue tris - default: - trianglesClipped++ - // outside or not fully covered -> remove. - if i < len(indices)-1 { - copy(indices[i:], indices[i+1:]) - } - indices[len(indices)-1] = 0 - indices = indices[:len(indices)-1] - } - } - ot.index[pos] = int32(len(indices)) - } - } - /* - fmt.Fprintln(fake, - `] - }`) - */ - log.Printf("info: node tests: %d\n", nodeTests) - log.Printf("info: nodes clipped: %d\n", nodesClipped) - log.Printf("info: nodes all inside: %d\n", nodesAllInside) - log.Printf("info: triangle clipped: %d\n", trianglesClipped) - log.Printf("info: tested triangles: %d\n", len(triChecks)) - - ot.eliminate(triChecks) -} - func (ot *Tree) Value(x, y float64) (float64, bool) { // out of bounding box