returned cap from CapBound for Polyline is too big

[djadala]

Hi,
i have case that performance using CapBound is in times slower compared to suggested replacement.

geo/s2/polyline.go

Line 91 in fb250ae

func (p *Polyline) CapBound() Cap {

Please change from

// CapBound returns the bounding Cap for this Polyline.
func (p *Polyline) CapBound() Cap {
	return p.RectBound().CapBound()
}

to

// CapBound returns the bounding Cap for this Polyline.
func (p *Polyline) CapBound() Cap {
	c := s2.EmptyCap()
	for _, v := range *p {
		c.AddPoint(v)
	}
	return c
}

[dsymonds]

/cc @rsned

[djadala]

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.

[djadala]

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
}

[dsymonds]

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.