func (cu *CellUnion) ExactArea() float64 {
	var area float64
	for _, id := range *cu {
		area += CellFromCellID(id).ExactArea()
	}
	return area
}
ExactArea returns the area of this CellUnion as accurately as possible.
package s2
import (
	"fmt"
	"io"
	"sort"
	"github.com/golang/geo/s1"
)
type CellUnion []CellID
func CellUnionFromRange(begin, end CellID) CellUnion {
	var cu CellUnion
	for id := begin.MaxTile(end); id != end; id = id.Next().MaxTile(end) {
		cu = append(cu, id)
	}
	return cu
}
func CellUnionFromUnion(cellUnions ...CellUnion) CellUnion {
	var cu CellUnion
	for _, cellUnion := range cellUnions {
		cu = append(cu, cellUnion...)
	}
	cu.Normalize()
	return cu
}
func CellUnionFromIntersection(x, y CellUnion) CellUnion {
	var cu CellUnion
	var i, j int
	for i < len(x) && j < len(y) {
		iMin := x[i].RangeMin()
		jMin := y[j].RangeMin()
		if iMin > jMin {
			if x[i] <= y[j].RangeMax() {
				cu = append(cu, x[i])
				i++
			} else {
				j = y.lowerBound(j+1, len(y), iMin)
				if x[i] <= y[j-1].RangeMax() {
					j--
				}
			}
		} else if jMin > iMin {
			if y[j] <= x[i].RangeMax() {
				cu = append(cu, y[j])
				j++
			} else {
				i = x.lowerBound(i+1, len(x), jMin)
				if y[j] <= x[i-1].RangeMax() {
					i--
				}
			}
		} else {
			if x[i] < y[j] {
				cu = append(cu, x[i])
				i++
			} else {
				cu = append(cu, y[j])
				j++
			}
		}
	}
	cu.Normalize()
	return cu
}
func CellUnionFromIntersectionWithCellID(x CellUnion, id CellID) CellUnion {
	var cu CellUnion
	if x.ContainsCellID(id) {
		cu = append(cu, id)
		cu.Normalize()
		return cu
	}
	idmax := id.RangeMax()
	for i := x.lowerBound(0, len(x), id.RangeMin()); i < len(x) && x[i] <= idmax; i++ {
		cu = append(cu, x[i])
	}
	cu.Normalize()
	return cu
}
func CellUnionFromDifference(x, y CellUnion) CellUnion {
	var cu CellUnion
	for _, xid := range x {
		cu.cellUnionDifferenceInternal(xid, &y)
	}
	return cu
}
func (cu *CellUnion) IsValid() bool {
	for i, cid := range *cu {
		if !cid.IsValid() {
			return false
		}
		if i == 0 {
			continue
		}
		if (*cu)[i-1].RangeMax() >= cid.RangeMin() {
			return false
		}
	}
	return true
}
func (cu *CellUnion) IsNormalized() bool {
	for i, cid := range *cu {
		if !cid.IsValid() {
			return false
		}
		if i == 0 {
			continue
		}
		if (*cu)[i-1].RangeMax() >= cid.RangeMin() {
			return false
		}
		if i < 3 {
			continue
		}
		if areSiblings((*cu)[i-3], (*cu)[i-2], (*cu)[i-1], cid) {
			return false
		}
	}
	return true
}
func (cu *CellUnion) Normalize() {
	sortCellIDs(*cu)
	output := make([]CellID, 0, len(*cu))  
	for _, ci := range *cu {
		if len(output) > 0 && output[len(output)-1].Contains(ci) {
			continue
		}
		j := len(output) - 1  
		for j >= 0 {
			if !ci.Contains(output[j]) {
				break
			}
			j--
		}
		output = output[:j+1]
		for len(output) >= 3 && areSiblings(output[len(output)-3], output[len(output)-2], output[len(output)-1], ci) {
			output = output[:len(output)-3]
			ci = ci.immediateParent()  
		}
		output = append(output, ci)
	}
	*cu = output
}
func (cu *CellUnion) IntersectsCellID(id CellID) bool {
	i := sort.Search(len(*cu), func(i int) bool { return id < (*cu)[i] })
	if i != len(*cu) && (*cu)[i].RangeMin() <= id.RangeMax() {
		return true
	}
	return i != 0 && (*cu)[i-1].RangeMax() >= id.RangeMin()
}
func (cu *CellUnion) ContainsCellID(id CellID) bool {
	i := sort.Search(len(*cu), func(i int) bool { return id < (*cu)[i] })
	if i != len(*cu) && (*cu)[i].RangeMin() <= id {
		return true
	}
	return i != 0 && (*cu)[i-1].RangeMax() >= id
}
func (cu *CellUnion) Denormalize(minLevel, levelMod int) {
	var denorm CellUnion
	for _, id := range *cu {
		level := id.Level()
		newLevel := level
		if newLevel < minLevel {
			newLevel = minLevel
		}
		if levelMod > 1 {
			newLevel += (maxLevel - (newLevel - minLevel)) % levelMod
			if newLevel > maxLevel {
				newLevel = maxLevel
			}
		}
		if newLevel == level {
			denorm = append(denorm, id)
		} else {
			end := id.ChildEndAtLevel(newLevel)
			for ci := id.ChildBeginAtLevel(newLevel); ci != end; ci = ci.Next() {
				denorm = append(denorm, ci)
			}
		}
	}
	*cu = denorm
}
func (cu *CellUnion) RectBound() Rect {
	bound := EmptyRect()
	for _, c := range *cu {
		bound = bound.Union(CellFromCellID(c).RectBound())
	}
	return bound
}
func (cu *CellUnion) CapBound() Cap {
	if len(*cu) == 0 {
		return EmptyCap()
	}
	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()}
	}
	c := CapFromPoint(centroid)
	for _, ci := range *cu {
		c = c.AddCap(CellFromCellID(ci).CapBound())
	}
	return c
}
func (cu *CellUnion) ContainsCell(c Cell) bool {
	return cu.ContainsCellID(c.id)
}
func (cu *CellUnion) IntersectsCell(c Cell) bool {
	return cu.IntersectsCellID(c.id)
}
func (cu *CellUnion) ContainsPoint(p Point) bool {
	return cu.ContainsCell(CellFromPoint(p))
}
func (cu *CellUnion) CellUnionBound() []CellID {
	return cu.CapBound().CellUnionBound()
}
func (cu *CellUnion) LeafCellsCovered() int64 {
	var numLeaves int64
	for _, c := range *cu {
		numLeaves += 1 << uint64((maxLevel-int64(c.Level()))<<1)
	}
	return numLeaves
}
func areSiblings(a, b, c, d CellID) bool {
	if (a ^ b ^ c) != d {
		return false
	}
	mask := d.lsb() << 1
	mask = ^(mask + (mask << 1))
	idMasked := (uint64(d) & mask)
	return ((uint64(a)&mask) == idMasked &&
		(uint64(b)&mask) == idMasked &&
		(uint64(c)&mask) == idMasked &&
		!d.isFace())
}
func (cu *CellUnion) Contains(o CellUnion) bool {
	for _, id := range o {
		if !cu.ContainsCellID(id) {
			return false
		}
	}
	return true
}
func (cu *CellUnion) Intersects(o CellUnion) bool {
	for _, c := range *cu {
		if o.IntersectsCellID(c) {
			return true
		}
	}
	return false
}
func (cu *CellUnion) lowerBound(begin, end int, id CellID) int {
	for i := begin; i < end; i++ {
		if (*cu)[i] >= id {
			return i
		}
	}
	return end
}
func (cu *CellUnion) cellUnionDifferenceInternal(id CellID, other *CellUnion) {
	if !other.IntersectsCellID(id) {
		(*cu) = append((*cu), id)
		return
	}
	if !other.ContainsCellID(id) {
		for _, child := range id.Children() {
			cu.cellUnionDifferenceInternal(child, other)
		}
	}
}
func (cu *CellUnion) ExpandAtLevel(level int) {
	var output CellUnion
	levelLsb := lsbForLevel(level)
	for i := len(*cu) - 1; i >= 0; i-- {
		id := (*cu)[i]
		if id.lsb() < levelLsb {
			id = id.Parent(level)
			for i > 0 && id.Contains((*cu)[i-1]) {
				i--
			}
		}
		output = append(output, id)
		output = append(output, id.AllNeighbors(level)...)
	}
	sortCellIDs(output)
	*cu = output
	cu.Normalize()
}
func (cu *CellUnion) ExpandByRadius(minRadius s1.Angle, maxLevelDiff int) {
	minLevel := maxLevel
	for _, cid := range *cu {
		minLevel = minInt(minLevel, cid.Level())
	}
	radiusLevel := MinWidthMetric.MaxLevel(minRadius.Radians())
	if radiusLevel == 0 && minRadius.Radians() > MinWidthMetric.Value(0) {
		cu.ExpandAtLevel(0)
	}
	cu.ExpandAtLevel(minInt(minLevel+maxLevelDiff, radiusLevel))
}
func (cu CellUnion) Equal(o CellUnion) bool {
	if len(cu) != len(o) {
		return false
	}
	for i := 0; i < len(cu); i++ {
		if cu[i] != o[i] {
			return false
		}
	}
	return true
}
func (cu *CellUnion) AverageArea() float64 {
	return AvgAreaMetric.Value(maxLevel) * float64(cu.LeafCellsCovered())
}
func (cu *CellUnion) ApproxArea() float64 {
	var area float64
	for _, id := range *cu {
		area += CellFromCellID(id).ApproxArea()
	}
	return area
}