[go: nahoru, domu]
Skip to content

Commit

Permalink
s2: Add RegionCoverer.IsCanonical.
Browse files Browse the repository at this point in the history 
Update the normalize covering method with the changes on C++ side from
the past couple of years.

Other than finishing more of the tests, this completes RegionCoverer.

Signed-off-by: David Symonds <dsymonds@golang.org>
  • Loading branch information
@rsned @dsymonds
rsned authored and dsymonds committed Jul 30, 2020
1 parent 673a6f8 commit f335e21
Show file tree
Hide file tree
Showing 3 changed files with 263 additions and 29 deletions.
2 changes: 1 addition & 1 deletion README.md
View file
Original file line number Diff line number Diff line change
Expand Up @@ -128,6 +128,7 @@ Approximately ~40% complete.
* Point
* PointCompression
* Region
* RegionCoverer
* s2edge_clipping
* s2edge_crosser
* s2edge_crossings
Expand All @@ -153,7 +154,6 @@ listing of the incomplete methods are documented at the end of each file.
* Loop - Loop is mostly complete now. Missing Project, Distance, Union, etc.
* Polyline - Missing InitTo... methods, NearlyCoversPolyline
* Rect (AKA s2latlngrect in C++) - Missing Centroid, InteriorContains.
* RegionCoverer - canonicalize
* s2_test.go (AKA s2testing and s2textformat in C++) - Missing Fractal test
shape generation. This file is a collection of testing helper methods.
* s2edge_distances - Missing Intersection
Expand Down
168 changes: 153 additions & 15 deletions s2/regioncoverer.go
View file
Original file line number Diff line number Diff line change
Expand Up @@ -16,6 +16,7 @@ package s2

import (
"container/heap"
"sort"
)

// RegionCoverer allows arbitrary regions to be approximated as unions of cells (CellUnion).
Expand Down Expand Up @@ -78,6 +79,16 @@ type RegionCoverer struct {
MaxCells int // the maximum desired number of cells in the approximation.
}

// NewRegionCoverer returns a region coverer with the appropriate defaults.
func NewRegionCoverer() *RegionCoverer {
return &RegionCoverer{
MinLevel: 0,
MaxLevel: maxLevel,
LevelMod: 1,
MaxCells: 8,
}
}

type coverer struct {
minLevel int // the minimum cell level to be used.
maxLevel int // the maximum cell level to be used.
Expand Down Expand Up @@ -306,8 +317,20 @@ func (c *coverer) coveringInternal(region Region) {
c.addCandidate(cand)
}
}

c.pq.Reset()
c.region = nil

// Rather than just returning the raw list of cell ids, we construct a cell
// union and then denormalize it. This has the effect of replacing four
// child cells with their parent whenever this does not violate the covering
// parameters specified (min_level, level_mod, etc). This significantly
// reduces the number of cells returned in many cases, and it is cheap
// compared to computing the covering in the first place.
c.result.Normalize()
if c.minLevel > 0 || c.levelMod > 1 {
c.result.Denormalize(c.minLevel, c.levelMod)
}
}

// newCoverer returns an instance of coverer.
Expand Down Expand Up @@ -378,8 +401,26 @@ func (rc *RegionCoverer) FastCovering(region Region) CellUnion {
return cu
}

// normalizeCovering normalizes the "covering" so that it conforms to the current covering
// parameters (MaxCells, minLevel, maxLevel, and levelMod).
// IsCanonical reports whether the given CellUnion represents a valid covering
// that conforms to the current covering parameters. In particular:
//
// - All CellIDs must be valid.
//
// - CellIDs must be sorted and non-overlapping.
//
// - CellID levels must satisfy MinLevel, MaxLevel, and LevelMod.
//
// - If the covering has more than MaxCells, there must be no two cells with
// a common ancestor at MinLevel or higher.
//
// - There must be no sequence of cells that could be replaced by an
// ancestor (i.e. with LevelMod == 1, the 4 child cells of a parent).
func (rc *RegionCoverer) IsCanonical(covering CellUnion) bool {
return rc.newCoverer().isCanonical(covering)
}

// normalizeCovering normalizes the "covering" so that it conforms to the
// current covering parameters (maxCells, minLevel, maxLevel, and levelMod).
// This method makes no attempt to be optimal. In particular, if
// minLevel > 0 or levelMod > 1 then it may return more than the
// desired number of cells even when this isn't necessary.
Expand All @@ -400,6 +441,25 @@ func (c *coverer) normalizeCovering(covering *CellUnion) {
// Sort the cells and simplify them.
covering.Normalize()

// Make sure that the covering satisfies minLevel and levelMod,
// possibly at the expense of satisfying MaxCells.
if c.minLevel > 0 || c.levelMod > 1 {
covering.Denormalize(c.minLevel, c.levelMod)
}

// If there are too many cells and the covering is very large, use the
// RegionCoverer to compute a new covering. (This avoids possible O(n^2)
// behavior of the simpler algorithm below.)
excess := len(*covering) - c.maxCells
if excess <= 0 || c.isCanonical(*covering) {
return
}
if excess*len(*covering) > 10000 {
rc := NewRegionCoverer()
(*covering) = rc.Covering(covering)
return
}

// If there are still too many cells, then repeatedly replace two adjacent
// cells in CellID order by their lowest common ancestor.
for len(*covering) > c.maxCells {
Expand All @@ -420,14 +480,99 @@ func (c *coverer) normalizeCovering(covering *CellUnion) {
if bestLevel < c.minLevel {
break
}
(*covering)[bestIndex] = (*covering)[bestIndex].Parent(bestLevel)
covering.Normalize()

// Replace all cells contained by the new ancestor cell.
id := (*covering)[bestIndex].Parent(bestLevel)
(*covering) = c.replaceCellsWithAncestor(*covering, id)

// Now repeatedly check whether all children of the parent cell are
// present, in which case we can replace those cells with their parent.
for bestLevel > c.minLevel {
bestLevel -= c.levelMod
id = id.Parent(bestLevel)
if !c.containsAllChildren(*covering, id) {
break
}
(*covering) = c.replaceCellsWithAncestor(*covering, id)
}
}
// Make sure that the covering satisfies minLevel and levelMod,
// possibly at the expense of satisfying MaxCells.
if c.minLevel > 0 || c.levelMod > 1 {
covering.Denormalize(c.minLevel, c.levelMod)
}

// isCanonical reports whether the covering is canonical.
func (c *coverer) isCanonical(covering CellUnion) bool {
trueMax := c.maxLevel
if c.levelMod != 1 {
trueMax = c.maxLevel - (c.maxLevel-c.minLevel)%c.levelMod
}
tooManyCells := len(covering) > c.maxCells
sameParentCount := 1

prevID := CellID(0)
for _, id := range covering {
if !id.IsValid() {
return false
}

// Check that the CellID level is acceptable.
level := id.Level()
if level < c.minLevel || level > trueMax {
return false
}
if c.levelMod > 1 && (level-c.minLevel)%c.levelMod != 0 {
return false
}

if prevID != 0 {
// Check that cells are sorted and non-overlapping.
if prevID.RangeMax() >= id.RangeMin() {
return false
}

lev, ok := id.CommonAncestorLevel(prevID)
// If there are too many cells, check that no pair of adjacent cells
// could be replaced by an ancestor.
if tooManyCells && (ok && lev >= c.minLevel) {
return false
}

// Check that there are no sequences of (4 ** level_mod) cells that all
// have the same parent (considering only multiples of "level_mod").
pLevel := level - c.levelMod
if pLevel < c.minLevel || level != prevID.Level() ||
id.Parent(pLevel) != prevID.Parent(pLevel) {
sameParentCount = 1
} else {
sameParentCount++
if sameParentCount == 1<<uint(2*c.levelMod) {
return false
}
}
}
prevID = id
}

return true
}

func (c *coverer) containsAllChildren(covering []CellID, id CellID) bool {
pos := sort.Search(len(covering), func(i int) bool { return (covering)[i] >= id.RangeMin() })
level := id.Level() + c.levelMod
for child := id.ChildBeginAtLevel(level); child != id.ChildEndAtLevel(level); child = child.Next() {
if pos == len(covering) || covering[pos] != child {
return false
}
pos++
}
return true
}

// replaceCellsWithAncestor replaces all descendants of the given id in covering
// with id. This requires the covering contains at least one descendant of id.
func (c *coverer) replaceCellsWithAncestor(covering []CellID, id CellID) []CellID {
begin := sort.Search(len(covering), func(i int) bool { return covering[i] > id.RangeMin() })
end := sort.Search(len(covering), func(i int) bool { return covering[i] > id.RangeMax() })

return append(append(covering[:begin], id), covering[end:]...)
}

// SimpleRegionCovering returns a set of cells at the given level that cover
Expand Down Expand Up @@ -468,10 +613,3 @@ func FloodFillRegionCovering(region Region, start CellID) []CellID {

return output
}

// TODO(roberts): The differences from the C++ version
// finish up FastCovering to match C++
// IsCanonical
// CanonicalizeCovering
// containsAllChildren
// replaceCellsWithAncestor
122 changes: 109 additions & 13 deletions s2/regioncoverer_test.go
View file
Original file line number Diff line number Diff line change
Expand Up @@ -27,13 +27,12 @@ func TestCovererRandomCells(t *testing.T) {

// Test random cell ids at all levels.
for i := 0; i < 10000; i++ {
id := CellID(randomUint64())
for !id.IsValid() {
id = CellID(randomUint64())
}
id := randomCellID()
covering := rc.Covering(Region(CellFromCellID(id)))
if len(covering) != 1 {
t.Errorf("Iteration %d, cell ID token %s, got covering size = %d, want covering size = 1", i, id.ToToken(), len(covering))
// if the covering isn't len 1, the next check will panic
break
}
if (covering)[0] != id {
t.Errorf("Iteration %d, cell ID token %s, got covering = %v, want covering = %v", i, id.ToToken(), covering, id)
Expand Down Expand Up @@ -115,7 +114,7 @@ func checkCoveringTight(t *testing.T, r Region, cover CellUnion, checkTight bool
}

func TestCovererRandomCaps(t *testing.T) {
rc := &RegionCoverer{}
rc := &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 1}
for i := 0; i < 1000; i++ {
rc.MinLevel = int(rand.Int31n(maxLevel + 1))
rc.MaxLevel = int(rand.Int31n(maxLevel + 1))
Expand Down Expand Up @@ -194,6 +193,111 @@ func TestRegionCovererSimpleRegionCovering(t *testing.T) {
}
}

func TestRegionCovererIsCanonical(t *testing.T) {
tests := []struct {
cells []string
cov *RegionCoverer
want bool
}{
// InvalidCellID
{cells: []string{"1/"}, cov: NewRegionCoverer(), want: true},
{cells: []string{"invalid"}, cov: NewRegionCoverer(), want: false},
// Unsorted
{cells: []string{"1/1", "1/3"}, cov: NewRegionCoverer(), want: true},
{cells: []string{"1/3", "1/1"}, cov: NewRegionCoverer(), want: false},

// Overlapping
{cells: []string{"1/2", "1/33"}, cov: NewRegionCoverer(), want: true},
{cells: []string{"1/3", "1/33"}, cov: NewRegionCoverer(), want: false},

// MinLevel
{
cells: []string{"1/31"},
cov: &RegionCoverer{MinLevel: 2, MaxLevel: 30, LevelMod: 1, MaxCells: 8},
want: true,
},
{
cells: []string{"1/3"},
cov: &RegionCoverer{MinLevel: 2, MaxLevel: 30, LevelMod: 1, MaxCells: 8},
want: false,
},

// MaxLevel
{
cells: []string{"1/31"},
cov: &RegionCoverer{MinLevel: 0, MaxLevel: 2, LevelMod: 1, MaxCells: 8},
want: true,
},
{
cells: []string{"1/312"},
cov: &RegionCoverer{MinLevel: 0, MaxLevel: 2, LevelMod: 1, MaxCells: 8},
want: false,
},

// LevelMod
{
cells: []string{"1/31"},
cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 2, MaxCells: 8},
want: true,
},
{
cells: []string{"1/312"},
cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 2, MaxCells: 8},
want: false,
},

// MaxCells
{cells: []string{"1/1", "1/3"}, cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 2}, want: true},
{cells: []string{"1/1", "1/3", "2/"}, cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 2}, want: false},
{cells: []string{"1/123", "2/1", "3/0122"}, cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 2}, want: true},

// Normalized
// Test that no sequence of cells could be replaced by an ancestor.
{
cells: []string{"1/01", "1/02", "1/03", "1/10", "1/11"},
cov: NewRegionCoverer(),
want: true,
},
{
cells: []string{"1/00", "1/01", "1/02", "1/03", "1/10"},
cov: NewRegionCoverer(),
want: false,
},

{
cells: []string{"0/22", "1/01", "1/02", "1/03", "1/10"},
cov: NewRegionCoverer(),
want: true,
},
{
cells: []string{"0/22", "1/00", "1/01", "1/02", "1/03"},
cov: NewRegionCoverer(),
want: false,
},

{
cells: []string{"1/1101", "1/1102", "1/1103", "1/1110", "1/1111", "1/1112",
"1/1113", "1/1120", "1/1121", "1/1122", "1/1123", "1/1130",
"1/1131", "1/1132", "1/1133", "1/1200"},
cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 2, MaxCells: 20},
want: true,
},
{
cells: []string{"1/1100", "1/1101", "1/1102", "1/1103", "1/1110", "1/1111",
"1/1112", "1/1113", "1/1120", "1/1121", "1/1122", "1/1123",
"1/1130", "1/1131", "1/1132", "1/1133"},
cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 2, MaxCells: 20},
want: false,
},
}
for _, test := range tests {
cu := makeCellUnion(test.cells...)
if got := test.cov.IsCanonical(cu); got != test.want {
t.Errorf("IsCanonical(%v) = %t, want %t", cu, got, test.want)
}
}
}

const numCoveringBMRegions = 1000

func BenchmarkRegionCovererCoveringCap(b *testing.B) {
Expand Down Expand Up @@ -278,14 +382,6 @@ func benchmarkRegionCovererCovering(b *testing.B, genLabel func(n int) string, g
// TODO(roberts): Differences from C++
// func TestRegionCovererAccuracy(t *testing.T) {
// func TestRegionCovererFastCoveringHugeFixedLevelCovering(t *testing.T) {
// func TestRegionCovererIsCanonicalInvalidS2CellId(t *testing.T) {
// func TestRegionCovererIsCanonicalUnsorted(t *testing.T) {
// func TestRegionCovererIsCanonicalOverlapping(t *testing.T) {
// func TestRegionCovererIsCanonicalMinLevel(t *testing.T) {
// func TestRegionCovererIsCanonicalMaxLevel(t *testing.T) {
// func TestRegionCovererIsCanonicalLevelMod(t *testing.T) {
// func TestRegionCovererIsCanonicalMaxCells(t *testing.T) {
// func TestRegionCovererIsCanonicalNormalized(t *testing.T) {
// func TestRegionCovererCanonicalizeCoveringUnsortedDuplicateCells(t *testing.T) {
// func TestRegionCovererCanonicalizeCoveringMaxLevelExceeded(t *testing.T) {
// func TestRegionCovererCanonicalizeCoveringWrongLevelMod(t *testing.T) {
Expand Down

0 comments on commit f335e21

Please sign in to comment.