// finds the centroid of an arbitrary number of points.
// Assumes points[i] = x, points[i+1] = y.
972366
func centroid(points []float64) (int, int, error) {
	pointLen := len(points)
	if pointLen%2 != 0 {
		return -1, -1, &InvalidDimensionsErr{"number of points are not divisible by two"}
	}
	x := 0
	y := 0
	for i := 0; i < pointLen; i = i + 2 {
		x += int(points[i])
		y += int(points[i+1])
	}
	return x / (pointLen / 2), y / (pointLen / 2), nil
}
822671
func (bb BoundingBox) Centroid() *Point {
	var result *Point
	if bb.Valid() == nil {
		switch len(bb) {
		case 0:
		case 4:
			var coordinates [2]float64
			coordinates[0] = 0.5 * (bb[0] + bb[2])
			coordinates[1] = 0.5 * (bb[1] + bb[3])
			result = NewPoint(coordinates[0:])
		case 6:
			var coordinates [3]float64
			coordinates[0] = 0.5 * (bb[0] + bb[3])
			coordinates[1] = 0.5 * (bb[1] + bb[4])
			coordinates[2] = 0.5 * (bb[2] + bb[5])
			result = NewPoint(coordinates[0:])
		}
	}
	return result
}
346866
func findIndex(c int, points []int) int {
	a, b := 0, len(points)
	for b-a > 1 {
		d := int(uint(a+b) >> 1)
		if points[d] > c {
			b = d
		} else if points[d] < c {
			a = d
		} else {
			return d
		}
	}
	return a
}
1019163
func (e *Element) getCenter() (int, int, error) {
	points, err := e.Dimensions()
	if err != nil {
		return 0, 0, err
	}

	x, y, err := centroid(points)
	if err != nil {
		return 0, 0, err
	}
	return x, y, nil
}
1326868
func (ci CellID) centerST() r2.Point {
	_, si, ti := ci.faceSiTi()
	return r2.Point{siTiToST(si), siTiToST(ti)}
}
162439
func (l *Line) GeoMidpoint() *Point {
	p := &Point{}

	dLng := deg2rad(l.b.Lng() - l.a.Lng())

	aLatRad := deg2rad(l.a.Lat())
	bLatRad := deg2rad(l.b.Lat())

	x := math.Cos(bLatRad) * math.Cos(dLng)
	y := math.Cos(bLatRad) * math.Sin(dLng)

	p.SetLat(math.Atan2(math.Sin(aLatRad)+math.Sin(bLatRad), math.Sqrt((math.Cos(aLatRad)+x)*(math.Cos(aLatRad)+x)+y*y)))
	p.SetLng(deg2rad(l.a.Lng()) + math.Atan2(y, math.Cos(aLatRad)+x))

	// convert back to degrees
	p.SetLat(rad2deg(p.Lat()))
	p.SetLng(rad2deg(p.Lng()))

	return p
}
1237718
func (pTypeDef *Polyline) Init() *Polyline {
	if pTypeDef.Points == nil {
		pTypeDef.Points = make([]*Point, 0)
	}
	return pTypeDef
}
1184909
func MultiPointCentroid(point *geom.MultiPoint) geom.Coord {
	calc := NewPointCentroidCalculator()
	coords := point.FlatCoords()
	stride := point.Layout().Stride()
	for i := 0; i < len(coords); i += stride {
		calc.AddCoord(geom.Coord(coords[i : i+stride]))
	}

	return calc.GetCentroid()
}
125697
func (rect *Rect) PointsToUnits(t int) (r *Rect) {
	if rect == nil {
		return
	}

	if rect.unitOverride != Unit_Unset {
		t = rect.unitOverride
	}

	r = &Rect{W: rect.W, H: rect.H}
	PointsToUnitsVar(t, &r.W, &r.H)
	return
}
145550
func (calc *LineCentroidCalculator) GetCentroid() geom.Coord {
	cent := geom.Coord(make([]float64, calc.layout.Stride()))
	cent[0] = calc.centSum[0] / calc.totalLength
	cent[1] = calc.centSum[1] / calc.totalLength
	return cent
}
200287
func (p *Polygon) iteratorContainsPoint(it *ShapeIndexIterator, point Point) bool {
	// Test containment by drawing a line segment from the cell center to the
	// given point and counting edge crossings.
	aClipped := it.IndexCell().findByShapeID(0)
	inside := aClipped.containsCenter

	if len(aClipped.edges) == 0 {
		return inside
	}

	// This block requires ShapeIndex.
	crosser := NewEdgeCrosser(it.Center(), point)
	shape := p.index.Shape(0)
	for _, e := range aClipped.edges {
		edge := shape.Edge(e)
		inside = inside != crosser.EdgeOrVertexCrossing(edge.V0, edge.V1)
	}

	return inside
}
1192508
func (r Rect) Center() Point {
	return Point{r.X.Center(), r.Y.Center()}
}
1355387
func (c Cap) AddPoint(p Point) Cap {
	if c.IsEmpty() {
		c.center = p
		c.radius = 0
		return c
	}

	// After calling cap.AddPoint(p), cap.Contains(p) must be true. However
	// we don't need to do anything special to achieve this because Contains()
	// does exactly the same distance calculation that we do here.
	if newRad := ChordAngleBetweenPoints(c.center, p); newRad > c.radius {
		c.radius = newRad
	}
	return c
}
658622
func (cu *CellUnion) CapBound() Cap {
	if len(*cu) == 0 {
		return EmptyCap()
	}

	// Compute the approximate centroid of the region. This won't produce the
	// bounding cap of minimal area, but it should be close enough.
	var centroid Point

	for _, ci := range *cu {
		area := AvgAreaMetric.Value(ci.Level())
		centroid = Point{centroid.Add(ci.Point().Mul(area))}
	}

	if zero := (Point{}); centroid == zero {
		centroid = PointFromCoords(1, 0, 0)
	} else {
		centroid = Point{centroid.Normalize()}
	}

	// Use the centroid as the cap axis, and expand the cap angle so that it
	// contains the bounding caps of all the individual cells.  Note that it is
	// *not* sufficient to just bound all the cell vertices because the bounding
	// cap may be concave (i.e. cover more than one hemisphere).
	c := CapFromPoint(centroid)
	for _, ci := range *cu {
		c = c.AddCap(CellFromCellID(ci).CapBound())
	}

	return c
}
1171025
func (v *ViewPort) Center(x, y int) {
	if x < 0 || y < 0 || x >= v.limx || y >= v.limy || v.v == nil {
		return
	}
	v.viewx = x - (v.width / 2)
	v.viewy = y - (v.height / 2)
	v.ValidateView()
}
1313625
func (p PaddedCell) Center() Point {
	ijSize := sizeIJ(p.level)
	si := uint32(2*p.iLo + ijSize)
	ti := uint32(2*p.jLo + ijSize)
	return Point{faceSiTiToXYZ(p.id.Face(), si, ti).Normalize()}
}
96641
func (l *Loop) iteratorContainsPoint(it *ShapeIndexIterator, p Point) bool {
	// Test containment by drawing a line segment from the cell center to the
	// given point and counting edge crossings.
	aClipped := it.IndexCell().findByShapeID(0)
	inside := aClipped.containsCenter
	if len(aClipped.edges) > 0 {
		center := it.Center()
		crosser := NewEdgeCrosser(center, p)
		aiPrev := -2
		for _, ai := range aClipped.edges {
			if ai != aiPrev+1 {
				crosser.RestartAt(l.Vertex(ai))
			}
			aiPrev = ai
			inside = inside != crosser.EdgeOrVertexChainCrossing(l.Vertex(ai+1))
		}
	}
	return inside
}