S2RegionCoverer with fixed level issue

[Michael Brichko]

Hi,

It seems that using S2RegionCoverer with fixed level and in case of a big region and high level will run forever and\or till memory run out. In case of fixed level, setting max cells doesn't help. What would be the suggested solution to know in advace (in the course of is also perfectly fine) that count of cellsto cover some specific level will exceed some boundry amount ?

Essentially, I would want that setting max cells would just work in case of fixed level covering...

It would be great to hear any solutions\workarounds...

Thanks,

Michael

[Jesse Rosenstock]

min_level takes priority over max_cells.  What's the larger problem you're trying to solve? You probably want to do it without a range of levels.

One workaround would be to cover with a range of levels, then expand the cells yourself, but, fundamentally, you're going to run out of memory if you try to cover the whole sphere with leaf cells.  

[Michael Brichko]

Yes, I want to be able to cover regions withouth the range and I was hoping to not re-write the algorithm. Current implementation simply doesn't stop in the edge case, I want the algorthm to sop once it passes some threshold...

[Jesse Rosenstock]

On Thursday, March 12, 2020 at 1:24:31 PM UTC+1, Michael Brichko wrote:

Yes, I want to be able to cover regions withouth the range and I was hoping to not re-write the algorithm. Current implementation simply doesn't stop in the edge case, I want the algorthm to sop once it passes some threshold...

What do you want it to do if you ask for a covering with N cells, but it takes M > N cells to cover the region at the level you requested?

What are you doing with the cells in the covering? Maybe try to rewrite that to not require a fixed level.

What I was suggesting before is to do something like 

S2CellUnion covering = coverer.GetCovering(...);  // don't use fixed level here

vector<S2CellId> cell_ids;

covering.Denormalize(fixed_level, /*level_mod=*/1, &cell_ids);

But, as I said before, you may be fundamentally destined to run out of memory depending on your region and level.

[Michael Brichko]

In case I ask for covering with N cells but it takes M > N, I want the algorthm to stop, let's say return null, it would be great to receive some error code that says that N is not enough.

I need the cell id tokens of the same level for a higher abstraction algorithm.

I'm using next version of the covering method "void GetCovering(const S2Region& region, std::vector<S2CellId>* covering);"

[Jesse Rosenstock]

On Thursday, March 12, 2020 at 2:27:57 PM UTC+1, Michael Brichko wrote:

In case I ask for covering with N cells but it takes M > N, I want the algorthm to stop, let's say return null, it would be great to receive some error code that says that N is not enough.

I need the cell id tokens of the same level for a higher abstraction algorithm.

I think you can probably rewrite your algorithm so that it doesn't require a fixed level, but you can also get a variable level covering, then compute how many cells it will take once expanded to a fixed level. It's 4**(fixed_level - cell.level()) for each cell.  Do your error handling if this is too large. After that, you can either just do the expansion with Denormalize(), or call the coverer again.

[Michael Brichko]

I could use an algorithm that uses range but *I need* the fixed level. Thanks for your suggetion, I wonder if ther is a more performant calculation if M > N, your calculation makes sense but will require for me to pass on a normalized vector, seems quite expensive....

[Michael Brichko]

A follow-up question please, I also need s2cell tokens of fixed level for several regions, so naive approach for this would be to cover each region separately, calculate union of all s2 cell tokens and remove duplicates. Is there a better way to solve this ?

Thanks !!

[Jesse Rosenstock]

On Sunday, March 29, 2020 at 4:40:11 PM UTC+2, Michael Brichko wrote:

A follow-up question please, I also need s2cell tokens of fixed level for several regions, so naive approach for this would be to cover each region separately, calculate union of all s2 cell tokens and remove duplicates. Is there a better way to solve this ?

Use S2RegionUnion.

[Michael Brichko]

Cool ! Thanks a lot !!