# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1570974339 -7200
# Node ID 89a72e0e2f9b841695da6e0f9323ff1e8689ffa0
# Parent  a1a9b1eab57c6daf4dfae59c785c132242815bf0
Add a method to serialize an STRTree.

diff -r a1a9b1eab57c -r 89a72e0e2f9b go.mod
--- a/go.mod	Fri Oct 11 23:46:35 2019 +0200
+++ b/go.mod	Sun Oct 13 15:45:39 2019 +0200
@@ -16,6 +16,7 @@
 	github.com/magiconair/properties v1.8.1 // indirect
 	github.com/mitchellh/go-homedir v1.1.0
 	github.com/pelletier/go-toml v1.4.0 // indirect
+	github.com/pierrec/lz4 v2.3.0+incompatible
 	github.com/pkg/errors v0.8.1 // indirect
 	github.com/rs/cors v1.7.0
 	github.com/sergi/go-diff v1.0.0
diff -r a1a9b1eab57c -r 89a72e0e2f9b go.sum
--- a/go.sum	Fri Oct 11 23:46:35 2019 +0200
+++ b/go.sum	Sun Oct 13 15:45:39 2019 +0200
@@ -95,6 +95,8 @@
 github.com/pelletier/go-toml v1.2.0/go.mod h1:5z9KED0ma1S8pY6P1sdut58dfprrGBbd/94hg7ilaic=
 github.com/pelletier/go-toml v1.4.0 h1:u3Z1r+oOXJIkxqw34zVhyPgjBsm6X2wn21NWs/HfSeg=
 github.com/pelletier/go-toml v1.4.0/go.mod h1:PN7xzY2wHTK0K9p34ErDQMlFxa51Fk0OUruD3k1mMwo=
+github.com/pierrec/lz4 v2.3.0+incompatible h1:CZzRn4Ut9GbUkHlQ7jqBXeZQV41ZSKWFc302ZU6lUTk=
+github.com/pierrec/lz4 v2.3.0+incompatible/go.mod h1:pdkljMzZIN41W+lC3N2tnIh5sFi+IEE17M5jbnwPHcY=
 github.com/pkg/errors v0.8.0 h1:WdK/asTD0HN+q6hsWO3/vpuAkAr+tw6aNJNDFFf0+qw=
 github.com/pkg/errors v0.8.0/go.mod h1:bwawxfHBFNV+L2hUp1rHADufV3IMtnDRdf1r5NINEl0=
 github.com/pkg/errors v0.8.1 h1:iURUrRGxPUNPdy5/HRSm+Yj6okJ6UtLINN0Q9M4+h3I=
diff -r a1a9b1eab57c -r 89a72e0e2f9b pkg/imports/sr.go
--- a/pkg/imports/sr.go	Fri Oct 11 23:46:35 2019 +0200
+++ b/pkg/imports/sr.go	Sun Oct 13 15:45:39 2019 +0200
@@ -24,6 +24,7 @@
 	"errors"
 	"fmt"
 	"io"
+	"log"
 	"math"
 	"os"
 	"path"
@@ -565,6 +566,16 @@
 	feedback.Info("Clipping STR tree took %v.", time.Since(start))
 	feedback.Info("Number of triangles to clip %d.", len(removed))
 
+	start = time.Now()
+	s := octree.STRTree{Entries: 16}
+	s.BuildWithout(tin, removed)
+	if _, err2 := s.Bytes(); err2 != nil {
+		log.Printf("serializing STRTree failed: %v\n", err2)
+	}
+	log.Printf("Building strtree took: %v.\n", time.Since(start))
+
+	// return nil, UnchangedError("nothing to do")
+
 	feedback.Info("Build final octree index")
 
 	builder := octree.NewBuilder(tin)
diff -r a1a9b1eab57c -r 89a72e0e2f9b pkg/octree/strtree.go
--- a/pkg/octree/strtree.go	Fri Oct 11 23:46:35 2019 +0200
+++ b/pkg/octree/strtree.go	Sun Oct 13 15:45:39 2019 +0200
@@ -14,8 +14,14 @@
 package octree
 
 import (
+	"bytes"
+	"encoding/binary"
+	"io"
+	"log"
 	"math"
 	"sort"
+
+	"github.com/pierrec/lz4"
 )
 
 const STRTreeDefaultEntries = 8
@@ -44,6 +50,9 @@
 			}
 		} else { // leaf
 			top = -top - 1
+			if !s.bbox(top).Contains(x, y) {
+				continue
+			}
 			for i, n := int32(0), s.index[top+1]; i < n; i++ {
 				idx := s.index[top+2+i]
 				ti := s.tin.Triangles[idx]
@@ -150,6 +159,95 @@
 	return removed
 }
 
+func (s *STRTree) serializeIndex(w io.Writer) error {
+
+	if err := binary.Write(w, binary.LittleEndian, int32(len(s.index))); err != nil {
+		return err
+	}
+
+	if err := binary.Write(w, binary.LittleEndian, s.index[0]); err != nil {
+		return err
+	}
+
+	var buf [binary.MaxVarintLen32]byte
+
+	var last int32
+	var written int
+
+	for _, x := range s.index[1:] {
+		delta := x - last
+		n := binary.PutVarint(buf[:], int64(delta))
+		for p := buf[:n]; len(p) > 0; p = p[n:] {
+			var err error
+			if n, err = w.Write(p); err != nil {
+				return err
+			}
+			written += n
+		}
+
+		last = x
+	}
+	log.Printf("info: compressed index in bytes: %d %.2f (%d %.2f)\n",
+		written,
+		float64(written)/(1024*1024),
+		4*len(s.index),
+		float64(4*len(s.index))/(1024*1024),
+	)
+
+	return nil
+}
+
+func (s *STRTree) serializeBBoxes(w io.Writer) (rr error) {
+
+	if err := binary.Write(w, binary.LittleEndian, int32(len(s.bboxes))); err != nil {
+		return err
+	}
+
+	var err error
+
+	write := func(v float64) {
+		if err == nil {
+			err = binary.Write(w, binary.LittleEndian, math.Float64bits(v))
+		}
+	}
+	for _, box := range s.bboxes {
+		write(box.X1)
+		write(box.Y1)
+		write(box.X2)
+		write(box.Y2)
+	}
+
+	return err
+}
+
+func (s *STRTree) Bytes() ([]byte, error) {
+
+	var buf bytes.Buffer
+	w := lz4.NewWriter(&buf)
+
+	if err := s.tin.serialize(w); err != nil {
+		return nil, err
+	}
+
+	if err := binary.Write(w, binary.LittleEndian, uint8(s.Entries)); err != nil {
+		return nil, err
+	}
+
+	if err := s.serializeIndex(w); err != nil {
+		return nil, err
+	}
+
+	if err := s.serializeBBoxes(w); err != nil {
+		return nil, err
+	}
+
+	if err := w.Flush(); err != nil {
+		return nil, err
+	}
+
+	return buf.Bytes(), nil
+}
+
 func (s *STRTree) allTriangles(pos int32, tris map[int32]struct{}) {
 	stack := []int32{pos}
 	for len(stack) > 0 {