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