Source file src/github.com/golang/geo/s2/encode_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2017 Google Inc. All rights reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package s2
    16  
    17  import (
    18  	"bytes"
    19  	"encoding/hex"
    20  	"fmt"
    21  	"io"
    22  	"math"
    23  	"reflect"
    24  	"testing"
    25  
    26  	"github.com/golang/geo/r3"
    27  )
    28  
    29  type encodableRegion interface {
    30  	Encode(io.Writer) error
    31  }
    32  
    33  type decodableRegion interface {
    34  	Decode(io.Reader) error
    35  }
    36  
    37  const (
    38  
    39  	// encodedCapEmpty comes from EmptyCap()
    40  	encodedCapEmpty = "000000000000F03F00000000000000000000000000000000000000000000F0BF"
    41  	// encodedCapFull comes from FullCap()
    42  	encodedCapFull = "000000000000F03F000000000000000000000000000000000000000000001040"
    43  	// Cap from Point(3, 2, 1).Normalize()
    44  	encodedCapFromPoint = "3F36105836A8E93F2A2460E5CE1AE13F2A2460E5CE1AD13F0000000000000000"
    45  	// Cap from Point(0, 0, 1) with height 5
    46  	encodedCapFromCenterHeight = "00000000000000000000000000000000000000000000F03F0000000000001040"
    47  	// Cap from Point(0, 0, 1) with height 0.5
    48  	encodedCapFromCenterHeight2 = "00000000000000000000000000000000000000000000F03F000000000000F03F"
    49  	// CellID from Face 0.
    50  	encodedCellIDFace0 = "0000000000000010"
    51  	// CellID from Face 5.
    52  	encodedCellIDFace5 = "00000000000000B0"
    53  	// CellID from Face 0 in the last Cell at MaxLevel.
    54  	encodedCellIDFace0MaxLevel = "0100000000000020"
    55  	// CellID from Face 5 in the last Cell at MaxLevel.
    56  	encodedCellIDFace5MaxLevel = "01000000000000C0"
    57  	// CellID FromFacePosLevel(3, 0x12345678, MaxLevel - 4)
    58  	encodedCellIDFacePosLevel = "0057341200000060"
    59  	// CellID from the 0 value.
    60  	encodedCellIDInvalid = "0000000000000000"
    61  
    62  	// Cell from Point(1, 2, 3)
    63  	encodedCellFromPoint = "F51392E0F35DCC43"
    64  	// Cell from (39.0, -120.0) - The Lake Tahoe border corner of CA/NV.
    65  	encodedCellFromLatLng = "6308962A95849980"
    66  	// Cell FromFacePosLevel(3, 0x12345678, MaxLevel - 4)
    67  	encodedCellFromFacePosLevel = "0057341200000060"
    68  	// Cell from Face 0.
    69  	encodedCellFace0 = "0000000000000010"
    70  
    71  	// An uninitialized empty CellUnion.
    72  	encodedCellUnionEmpty = "010000000000000000"
    73  	// CellUnion from a CellID from Face 1.
    74  	encodedCellUnionFace1 = "0101000000000000000000000000000030"
    75  	// CellUnion from the cells {0x33, 0x8e3748fab, 0x91230abcdef83427};
    76  	encodedCellUnionFromCells = "0103000000000000003300000000000000AB8F74E3080000002734F8DEBC0A2391"
    77  
    78  	// Loop
    79  	encodedLoopEmpty = "010100000000000000000000000000000000000000000000000000F03F000000000001000000000000F03F0000000000000000182D4454FB210940182D4454FB2109C0"
    80  	encodedLoopFull  = "010100000000000000000000000000000000000000000000000000F0BF010000000001182D4454FB21F9BF182D4454FB21F93F182D4454FB2109C0182D4454FB210940"
    81  	// Loop from the unit test value kCross1;
    82  	encodedLoopCross = "0108000000D44A8442C3F9EF3F7EDA2AB341DC913F27DCF7C958DEA1BFB4825F3C81FDEF3F27DCF7C958DE913F1EDD892B0BDF91BFB4825F3C81FDEF3F27DCF7C958DE913F1EDD892B0BDF913FD44A8442C3F9EF3F7EDA2AB341DC913F27DCF7C958DEA13FD44A8442C3F9EF3F7EDA2AB341DC91BF27DCF7C958DEA13FB4825F3C81FDEF3F27DCF7C958DE91BF1EDD892B0BDF913FB4825F3C81FDEF3F27DCF7C958DE91BF1EDD892B0BDF91BFD44A8442C3F9EF3F7EDA2AB341DC91BF27DCF7C958DEA1BF0000000000013EFC10E8F8DFA1BF3EFC10E8F8DFA13F389D52A246DF91BF389D52A246DF913F"
    83  	// Loop encoded using EncodeCompressed from snapped points.
    84  	//
    85  	//       CellIDFromLatLng("0:178")).ToPoint(),
    86  	//       CellIDFromLatLng("-1:180")).ToPoint(),
    87  	//       CellIDFromLatLng("0:-179")).ToPoint(),
    88  	//       CellIDFromLatLng("1:-180")).ToPoint()};
    89  	// LoopFromPoints((snapped_loop_a_vertices));
    90  	encodedLoopCompressed = "041B02222082A222A806A0C7A991DE86D905D7C3A691F2DEE40383908880A0958805000003"
    91  
    92  	// OriginPoint()
    93  	encodedPointOrigin = "013BED86AA997A84BF88EC8B48C53C653FACD2721A90FFEF3F"
    94  	// Point(12.34, 56.78, 9.1011).Normalize()
    95  	encodedPointTesting = "0109AD578332DBCA3FBC9FDB9BB4E4EE3FE67E7C2CA7CEC33F"
    96  
    97  	// Polygon from makePolygon("").
    98  	// This is encoded in compressed format.
    99  	encodedPolygonEmpty = "041E00"
   100  	// Polygon from makePolygon("full").
   101  	// This is encoded in compressed format.
   102  	encodedPolygonFull = "040001010B000100"
   103  	// Loop from the unit test value cross1. This is encoded in lossless format.
   104  	encodedPolygon1Loops = "010100010000000108000000D44A8442C3F9EF3F7EDA2AB341DC913F27DCF7C958DEA1BFB4825F3C81FDEF3F27DCF7C958DE913F1EDD892B0BDF91BFB4825F3C81FDEF3F27DCF7C958DE913F1EDD892B0BDF913FD44A8442C3F9EF3F7EDA2AB341DC913F27DCF7C958DEA13FD44A8442C3F9EF3F7EDA2AB341DC91BF27DCF7C958DEA13FB4825F3C81FDEF3F27DCF7C958DE91BF1EDD892B0BDF913FB4825F3C81FDEF3F27DCF7C958DE91BF1EDD892B0BDF91BFD44A8442C3F9EF3F7EDA2AB341DC91BF27DCF7C958DEA1BF0000000000013EFC10E8F8DFA1BF3EFC10E8F8DFA13F389D52A246DF91BF389D52A246DF913F013EFC10E8F8DFA1BF3EFC10E8F8DFA13F389D52A246DF91BF389D52A246DF913F"
   105  	// Loop from the unit test value cross1+crossHole.
   106  	// This is encoded in lossless format.
   107  	encodedPolygon2Loops = "010101020000000108000000D44A8442C3F9EF3F7EDA2AB341DC913F27DCF7C958DEA1BFB4825F3C81FDEF3F27DCF7C958DE913F1EDD892B0BDF91BFB4825F3C81FDEF3F27DCF7C958DE913F1EDD892B0BDF913FD44A8442C3F9EF3F7EDA2AB341DC913F27DCF7C958DEA13FD44A8442C3F9EF3F7EDA2AB341DC91BF27DCF7C958DEA13FB4825F3C81FDEF3F27DCF7C958DE91BF1EDD892B0BDF913FB4825F3C81FDEF3F27DCF7C958DE91BF1EDD892B0BDF91BFD44A8442C3F9EF3F7EDA2AB341DC91BF27DCF7C958DEA1BF0000000000013EFC10E8F8DFA1BF3EFC10E8F8DFA13F389D52A246DF91BF389D52A246DF913F0104000000C5D7FA4B60FFEF3F1EDD892B0BDF813F214C95C437DF81BFC5D7FA4B60FFEF3F1EDD892B0BDF813F214C95C437DF813FC5D7FA4B60FFEF3F1EDD892B0BDF81BF214C95C437DF813FC5D7FA4B60FFEF3F1EDD892B0BDF81BF214C95C437DF81BF000100000001900C5E3B73DF81BF900C5E3B73DF813F399D52A246DF81BF399D52A246DF813F013EFC10E8F8DFA1BF3EFC10E8F8DFA13F389D52A246DF91BF389D52A246DF913F"
   108  	// TODO(roberts): Create Polygons that use compressed encoding.
   109  
   110  	// A Polyline from an empty slice.
   111  	encodedPolylineEmpty = "0100000000"
   112  	// A Polyline from 3 LatLngs {(0, 0),(0, 90),(0,180)};
   113  	// TODO(roberts): The next two goldens differ from the C++ in the last few bits of the
   114  	// IEEE 754 values.
   115  	//
   116  	// When converting the LatLng (0, 90) to a Point.
   117  	//
   118  	// Go:  cos(theta)*cos(phi) = 6.12323399573675740770266929248e-17
   119  	// C++: cos(theta)*cos(phi) = 6.12323399573676603586882014729e-17
   120  	//
   121  	//   want: 005C143326A6913C
   122  	//   got:  075C143326A6913C
   123  	//   diff:  ^
   124  	//
   125  	// C++ golden: 0103000000000000000000F03F00000000000000000000000000000000075C143326A6913C000000000000F03F0000000000000000000000000000F0BF075C143326A6A13C0000000000000000
   126  	encodedPolylineSemiEquator = "0103000000000000000000F03F00000000000000000000000000000000005C143326A6913C000000000000F03F0000000000000000000000000000F0BF005C143326A6A13C0000000000000000"
   127  
   128  	// A Polyline from makePolyline("0:0, 0:10, 10:20, 20:30");
   129  	// See comment above for why this golden differs from the C++ golden.
   130  	// C++ golden: 0104000000000000000000F03F00000000000000000000000000000000171C818C8B83EF3F89730B7E1A3AC63F000000000000000061B46C3A039DED3FE2DC829F868ED53F89730B7E1A3AC63F1B995E6FA10AEA3F1B2D5242F611DE3FF50B8A74A8E3D53F
   131  	encodedPolyline3Segments = "0104000000000000000000F03F00000000000000000000000000000000181C818C8B83EF3F89730B7E1A3AC63F000000000000000062B46C3A039DED3FE2DC829F868ED53F89730B7E1A3AC63F1B995E6FA10AEA3F1B2D5242F611DE3FF50B8A74A8E3D53F"
   132  
   133  	// Rect from EmptyRect
   134  	encodedRectEmpty = "01000000000000F03F0000000000000000182D4454FB210940182D4454FB2109C0"
   135  	// Rect from FullRect
   136  	encodedRectFull = "01182D4454FB21F9BF182D4454FB21F93F182D4454FB2109C0182D4454FB210940"
   137  	// Rect from Center=(80,170), Size=(40,60)
   138  	encodedRectCentersize = "0165732D3852C1F03F182D4454FB21F93FF75B8A41358C03408744E74A185706C0"
   139  
   140  	// R2Rect - Not yet implemented.
   141  	// RegionIntersection - Not yet implemented.
   142  	// RegionUnion - Not yet implemented.
   143  )
   144  
   145  func TestEncodeDecode(t *testing.T) {
   146  	cu := CellUnion{}
   147  	cuFace := CellUnion([]CellID{CellIDFromFace(1)})
   148  	cuCells := CellUnion([]CellID{
   149  		CellID(0x33),
   150  		CellID(0x8e3748fab),
   151  		CellID(0x91230abcdef83427),
   152  	})
   153  
   154  	capPtr := func(c Cap) *Cap { return &c }
   155  	cidPtr := func(c CellID) *CellID { return &c }
   156  	cellPtr := func(c Cell) *Cell { return &c }
   157  	ptPtr := func(pt Point) *Point { return &pt }
   158  	rectPtr := func(r Rect) *Rect { return &r }
   159  
   160  	// Polyline inputs
   161  	// semiEquator := Polyline([]Point{
   162  	//	PointFromLatLng(LatLngFromDegrees(0, 0)),
   163  	// 	PointFromLatLng(LatLngFromDegrees(0, 90)),
   164  	// 	PointFromLatLng(LatLngFromDegrees(0, 180)),
   165  	// })
   166  	// threeSegments := makePolyline("0:0, 0:10, 10:20, 20:30")
   167  
   168  	const cross1 = "-2:1, -1:1, 1:1, 2:1, 2:-1, 1:-1, -1:-1, -2:-1"
   169  	const crossCenterHole = "-0.5:0.5, 0.5:0.5, 0.5:-0.5, -0.5:-0.5;"
   170  
   171  	emptyPolygon := func() *Polygon {
   172  		p := &Polygon{loops: []*Loop{}, bound: EmptyRect(), subregionBound: EmptyRect()}
   173  		p.initEdgesAndIndex()
   174  		return p
   175  	}
   176  
   177  	tests := []struct {
   178  		golden string
   179  		reg    encodableRegion
   180  	}{
   181  		// Caps
   182  		{encodedCapEmpty, capPtr(EmptyCap())},
   183  		{encodedCapFull, capPtr(FullCap())},
   184  		{encodedCapFromPoint, capPtr(CapFromPoint(PointFromCoords(3, 2, 1)))},
   185  		{encodedCapFromCenterHeight, capPtr(CapFromCenterHeight(PointFromCoords(0, 0, 1), 5))},
   186  		{encodedCapFromCenterHeight2, capPtr(CapFromCenterHeight(PointFromCoords(0, 0, 1), 0.5))},
   187  
   188  		// CellIDs
   189  		{encodedCellIDFace0, cidPtr(CellIDFromFace(0))},
   190  		{encodedCellIDFace5, cidPtr(CellIDFromFace(5))},
   191  		{encodedCellIDFace0MaxLevel, cidPtr(CellIDFromFace(0).ChildEndAtLevel(MaxLevel))},
   192  		{encodedCellIDFace5MaxLevel, cidPtr(CellIDFromFace(5).ChildEndAtLevel(MaxLevel))},
   193  		{encodedCellIDFacePosLevel, cidPtr(CellIDFromFacePosLevel(3, 0x12345678, MaxLevel-4))},
   194  		{encodedCellIDInvalid, cidPtr(CellID(0))},
   195  
   196  		// Cells
   197  		{encodedCellFromPoint, cellPtr(CellFromPoint(Point{r3.Vector{1, 2, 3}}))},
   198  		// Lake Tahoe CA/NV border corner
   199  		{encodedCellFromLatLng, cellPtr(CellFromLatLng(LatLngFromDegrees(39.0, -120.0)))},
   200  		{encodedCellFromFacePosLevel, cellPtr(CellFromCellID(CellIDFromFacePosLevel(3, 0x12345678, MaxLevel-4)))},
   201  		{encodedCellFace0, cellPtr(CellFromCellID(CellIDFromFace(0)))},
   202  
   203  		// CellUnions
   204  		{encodedCellUnionEmpty, &cu},
   205  		{encodedCellUnionFace1, &cuFace},
   206  		{encodedCellUnionFromCells, &cuCells},
   207  
   208  		// Loops
   209  		{encodedLoopEmpty, EmptyLoop()},
   210  		{encodedLoopFull, FullLoop()},
   211  		{encodedLoopCross, LoopFromPoints(parsePoints(cross1))},
   212  
   213  		// Points
   214  		{encodedPointOrigin, ptPtr(OriginPoint())},
   215  		{encodedPointTesting, ptPtr(PointFromCoords(12.34, 56.78, 9.1011))},
   216  
   217  		// Polygons.
   218  		{encodedPolygonEmpty, emptyPolygon()},
   219  		{encodedPolygonFull, FullPolygon()},
   220  		{encodedPolygon1Loops, makePolygon(cross1, false)},
   221  		{encodedPolygon2Loops, makePolygon(cross1+";"+crossCenterHole, false)},
   222  
   223  		// Polylines
   224  		{encodedPolylineEmpty, (&Polyline{})},
   225  		// TODO(nsch): Comment these lines back in once all decoders are implemented.
   226  		// Then, switch the test from encode->decode->deepequal to
   227  		// decode->approxequal->encode
   228  		// {encodedPolylineSemiEquator, semiEquator},
   229  		// {encodedPolyline3Segments, threeSegments},
   230  
   231  		// Rects
   232  		{encodedRectEmpty, rectPtr(EmptyRect())},
   233  		{encodedRectFull, rectPtr(FullRect())},
   234  		{encodedRectCentersize, rectPtr(RectFromCenterSize(LatLngFromDegrees(80, 170), LatLngFromDegrees(40, 60)))},
   235  	}
   236  
   237  	for _, test := range tests {
   238  		// Test encode.
   239  		buf := new(bytes.Buffer)
   240  		if err := test.reg.Encode(buf); err != nil {
   241  			t.Errorf("error encoding %v: %v", test.reg, err)
   242  		}
   243  
   244  		encoded := fmt.Sprintf("%X", buf.Bytes())
   245  		if test.golden != encoded {
   246  			t.Errorf("%#v.Encode() = %q, want %q", test.reg, encoded, test.golden)
   247  		}
   248  
   249  		// Create target for decoding.
   250  		decoded := reflect.New(reflect.TypeOf(test.reg).Elem()).Interface().(decodableRegion)
   251  
   252  		if err := decoded.Decode(buf); err != nil {
   253  			t.Errorf("decode(%#v): %v", test.reg, err)
   254  			continue
   255  		}
   256  		if !reflect.DeepEqual(decoded, test.reg) {
   257  			t.Errorf("decode = %#v, want %#v", decoded, test.reg)
   258  		}
   259  	}
   260  }
   261  
   262  func TestDecodeCompressedLoop(t *testing.T) {
   263  	dat, err := hex.DecodeString(encodedLoopCompressed)
   264  	if err != nil {
   265  		t.Fatal(err)
   266  	}
   267  	d := &decoder{r: bytes.NewReader(dat)}
   268  	gotDecoded := new(Loop)
   269  	gotDecoded.decodeCompressed(d, MaxLevel)
   270  	if d.err != nil {
   271  		t.Fatalf("loop.decodeCompressed: %v", d.err)
   272  	}
   273  	wantDecoded := []LatLng{LatLngFromDegrees(0, 178), LatLngFromDegrees(-1, 180), LatLngFromDegrees(0, -179), LatLngFromDegrees(1, -180)}
   274  	for i, v := range gotDecoded.Vertices() {
   275  		got := LatLngFromPoint(v)
   276  		want := wantDecoded[i]
   277  		const margin = 1e-9
   278  		if math.Abs((got.Lat-want.Lat).Radians()) >= margin || math.Abs((got.Lng-want.Lng).Radians()) >= margin {
   279  			t.Errorf("decoding golden at %d = %v, want %v", i, got, want)
   280  		}
   281  	}
   282  	var buf bytes.Buffer
   283  	e := &encoder{w: &buf}
   284  	gotDecoded.encodeCompressed(e, MaxLevel, gotDecoded.xyzFaceSiTiVertices())
   285  	if e.err != nil {
   286  		t.Fatalf("encodeCompressed(decodeCompressed(loop)): %v", err)
   287  	}
   288  	gotReencoded := fmt.Sprintf("%X", buf.Bytes())
   289  	if gotReencoded != encodedLoopCompressed {
   290  		t.Errorf("encodeCompressed(decodeCompressed(loop)) = %q, want %q", gotReencoded, encodedLoopCompressed)
   291  	}
   292  }
   293  
   294  // Captures the uncompressed path.
   295  func TestLoopEncodeDecode(t *testing.T) {
   296  	pts := parsePoints("30:20, 40:20, 39:43, 33:35")
   297  	loops := []*Loop{LoopFromPoints(pts), EmptyLoop(), FullLoop()}
   298  	for i, l := range loops {
   299  		var buf bytes.Buffer
   300  		l.Encode(&buf)
   301  		ll := new(Loop)
   302  		if err := ll.Decode(&buf); err != nil {
   303  			t.Errorf("Decode %d: %v", i, err)
   304  			continue
   305  		}
   306  		if !reflect.DeepEqual(l, ll) {
   307  			t.Errorf("encoding roundtrip failed")
   308  		}
   309  	}
   310  }
   311  
   312  func TestLoopEncodeDecodeFuzzed(t *testing.T) {
   313  	for i := 3; i < 100; i++ {
   314  		var pts []Point
   315  		for j := 0; j < i; j++ {
   316  			pts = append(pts, randomPoint())
   317  		}
   318  		loop := LoopFromPoints(pts)
   319  		if err := loop.Validate(); err != nil {
   320  			t.Fatalf("loop(%v).Validate: %v", loop, err)
   321  		}
   322  		polygon := PolygonFromLoops([]*Loop{loop})
   323  		var buf bytes.Buffer
   324  		if err := polygon.Encode(&buf); err != nil {
   325  			t.Fatal(err)
   326  		}
   327  		got := new(Loop)
   328  		if err := got.Decode(&buf); err != nil {
   329  			// TODO(nsch): Uncomment the next line as soon as decoding of all encoded loops works.
   330  			// t.Fatalf("decode(encode(%v)): %v", loop, err)
   331  			continue
   332  		}
   333  
   334  		if !reflect.DeepEqual(got, polygon) {
   335  			t.Errorf("decode(encode()) = %v, want %v", got, polygon)
   336  		}
   337  	}
   338  }
   339  
   340  func BenchmarkRectDecode(b *testing.B) {
   341  	rect := RectFromCenterSize(LatLngFromDegrees(80, 170), LatLngFromDegrees(40, 60))
   342  	var buf bytes.Buffer
   343  	if err := rect.Encode(&buf); err != nil {
   344  		b.Fatal(err)
   345  	}
   346  	encoded := buf.Bytes()
   347  	b.ReportAllocs()
   348  	b.SetBytes(int64(len(encoded)))
   349  	b.ResetTimer()
   350  	var out Rect
   351  	for i := 0; i < b.N; i++ {
   352  		if err := out.Decode(bytes.NewReader(encoded)); err != nil {
   353  			b.Fatal(err)
   354  		}
   355  	}
   356  }
   357  

View as plain text