returned cap from CapBound for Polyline is too big about geo HOT 4 CLOSED

/cc @rsned

from geo.

While truing to write small reproducer, i discover that when i use built-in CapBound, there is zero point, erroneously inserted at start of polyline , and that is reason for huge cap differences.
Now there is no more ' times slower' performance, but suggested change still return smaller caps, and as i understand, computational complexity is the same.

from geo.

Here is benchmark, proposed change is faster!(i don't expect such difference):

goos: linux
goarch: amd64
pkg: jambo/tests/geos2
BenchmarkCap1-4   	   20000	     61406 ns/op
BenchmarkCap2-4   	 1000000	      1289 ns/op

package main

import (
	"math/rand"
	"testing"

	"github.com/golang/geo/s2"
)

///////////////////////////////////atoi

const N = 200

var polyline s2.Polyline

func init() {
	const s = 100000
	for i := 0; i < N; i++ {
		t := float64(rand.Int63n(90*s)) / s
		g := float64(rand.Int63n(180*s)) / s
		polyline = append(polyline, s2.PointFromLatLng(s2.LatLngFromDegrees(t, g)))
	}
}

func BenchmarkCap1(b *testing.B) {

	for i := 0; i < b.N; i++ {
		_ = polyline.CapBound()
	}

}

func BenchmarkCap2(b *testing.B) {

	for i := 0; i < b.N; i++ {
		_ = CapBound(polyline)
	}

}

func CapBound(p s2.Polyline) s2.Cap {
	c := s2.EmptyCap()
	for _, v := range p {
		c.AddPoint(v)
	}
	return c
}

from geo.

The C++ code uses code like

S2Cap S2Polyline::GetCapBound() const {
  return GetRectBound().GetCapBound();
}

It is unlikely we will diverge from C++ algorithmically.

But note that I believe your code may be incorrect for large polylines. If an edge of the polyline is long enough, adding its endpoints to a cap progressively may end up with a cap that doesn't include the line in its entirety.

from geo.