radarlabs
question: RegionCoverer interface
Heya, I was checking out the RegionCoverer today and I noticed that the GetCovering* methods currently only support a single Loop (s2.LatLng[]) for the first argument.
Diving into the C++ code I see that the S2RegionCoverer::GetCovering method accepts an interface, and that interface provides an abstraction so it can operate on all sorts of polygonal geometries and spherical geometry such as discs (S2Cap).
Similarly in the Go Port the s2.Region is also an interface.
Looking at the C++ code I also noticed that these methods (such as GetRadiusCovering) don't exist in the C++ API, but are convenience methods of the JS API.
It would be really cool if I could pass a Polygon to a GetCovering() method and it compute the covering, considering any holes etc which I'm not confident in computing manually via CellUnion intersection of each ring, due to various error cases which could creep in (such as the holes being too large).
Do you have any long-term plans for developing the RegionCoverer? if so would you consider reverting to an API more similar to the C++ one which supports interfaces, if that's even possible in JS/TS?
I'm not sure if S2Polygon::GetCellUnionBound actually removes holes from the CellUnion or not 🤷♂️
I was a bit disappointed to see that the Go Port (p *Polygon) CellUnionBound() function returns the CellUnion of the Cap! So it's just returning a coverage of outer rings and not considering interior rings 😢
I might have had the wrong assumptions about RegionCoverer, I assumed it would cover the surface of the shape rather than the exterior boundary, looking at the C++ code that doesn't seem to be the case.
#include "s2/s2point.h"
#include "s2/s2cell_id.h"
#include "s2/s2builder.h"
#include "s2/s2builderutil_s2polygon_layer.h"
#include "s2/s2polygon.h"
#include "s2/s2loop.h"
#include "s2/s2text_format.h"
#include "s2/s2region.h"
#include "s2/s2region_coverer.h"
using s2builderutil::S2PolygonLayer;
using s2textformat::MakeLoopOrDie;
using s2textformat::MakePolygonOrDie;
using s2textformat::ToString;
using absl::make_unique;
using std::cout;
using std::endl;
string CellUnionTokens(const S2CellUnion &cell_union)
{
string out;
for (S2CellId cell_id : cell_union)
{
if (!out.empty())
out += ",";
out += cell_id.ToToken();
}
return out;
}
int main()
{
S2Builder::Options options;
S2Builder builder(options);
S2Polygon output;
builder.StartLayer(make_unique<S2PolygonLayer>(&output));
auto outer = MakeLoopOrDie("-32.364:153.207, -35.364:153.207, -35.364:158.207");
builder.AddLoop(*outer);
cout << "-- outer --" << endl;
cout << ToString(*outer) << endl;
auto inner1 = MakeLoopOrDie("-34.364:155.207, -34.364:154.207, -33.364:154.207");
builder.AddLoop(*inner1);
cout << "-- inner1 --" << endl;
cout << ToString(*inner1) << endl;
// auto inner2 = MakeLoopOrDie("-34.364:157.207, -34.364:156.207, -33.364:156.207");
// builder.AddLoop(*inner2);
// cout << "-- inner2 --" << endl;
// cout << ToString(*inner2) << endl;
cout << "-- build --" << endl;
S2Error error;
builder.Build(&error);
cout << error << endl;
cout << "-- output --" << endl;
cout << ToString(output) << endl;
S2RegionCoverer coverer;
S2CellUnion ret = coverer.GetCovering(output);
cout << "-- cell union --" << endl;
cout << CellUnionTokens(ret) << endl;
return 0;
}
-- outer --
-32.364:153.207, -35.364:153.207, -35.364:158.207
-- inner1 --
-34.364:155.207, -34.364:154.207, -33.364:154.207
-- build --
-- output --
-32.364:153.207, -35.364:153.207, -35.364:158.207;
-33.364:154.207, -34.364:154.207, -34.364:155.207
-- cell union --
6b63,6b65,6b6f,6b71,6b77,6b7c,6c82c,6c9d
I found this function GetInteriorCovering() which solves my issue 🎉
auto outer = MakeLoopOrDie("-35.364:153.207, -35.364:158.207, -32.364:158.207, -32.364:153.207");
auto inner1 = MakeLoopOrDie("-34.364:154.207, -34.364:155.207, -33.364:155.207, -33.364:154.207");
auto inner2 = MakeLoopOrDie("-34.364:156.207, -34.364:157.207, -33.364:157.207, -33.364:156.207");
S2RegionCoverer coverer;
coverer.mutable_options()->set_min_level(0);
coverer.mutable_options()->set_max_level(16);
coverer.mutable_options()->set_max_cells(100);
S2CellUnion outerCells = coverer.GetCovering(*outer);
S2CellUnion inner1Cells = coverer.GetInteriorCovering(*inner1);
S2CellUnion inner2Cells = coverer.GetInteriorCovering(*inner2);
auto output = outerCells.Difference(inner1Cells).Difference(inner2Cells);
cout << CellUnionTokens(output) << endl;
result: https://s2.sidewalklabs.com/regioncoverer/?center=-33.958564%2C155.768571&zoom=8&cells=6b6295%2C6b62b%2C6b62d%2C6b62e4%2C6b62ec%2C6b634%2C6b6454%2C6b645c%2C6b64604%2C6b64c%2C6b654%2C6b659%2C6b65a4%2C6b65ac%2C6b65bd5%2C6b6e3%2C6b6e5%2C6b6ed%2C6b6ef%2C6b6f1%2C6b6f24%2C6b6f3c%2C6b6f4004%2C6b6f7%2C6b6fc%2C6b7001%2C6b7003%2C6b70041%2C6b70045%2C6b70047%2C6b7004c%2C6b70054%2C6b7005c%2C6b7006c%2C6b70073%2C6b70075%2C6b70077%2C6b700c3%2C6b700c5%2C6b700cc%2C6b700d4%2C6b700dc%2C6b700e4%2C6b700e9%2C6b700ef%2C6b700f4%2C6b700fc%2C6b7014%2C6b701c%2C6b703%2C6b705%2C6b7064%2C6b706c%2C6b70704%2C6b7070c%2C6b70711%2C6b70717%2C6b7071c%2C6b70724%2C6b7072c%2C6b70731%2C6b70733%2C6b7073b%2C6b7073d%2C6b707b%2C6b707d%2C6b7085%2C6b70864%2C6b70869%2C6b7086f%2C6b70871%2C6b70877%2C6b7087c%2C6b708c%2C6b7094%2C6b7099%2C6b709a4%2C6b709ac%2C6b709b4%2C6b709bb%2C6b709bd%2C6b70a24%2C6b70a2c%2C6b70a34%2C6b70a39%2C6b70a3b%2C6b70a3f%2C6b70a5%2C6b70a7%2C6b70ac%2C6b70b4%2C6b70bc%2C6b70d%2C6b70f%2C6b711%2C6b713%2C6b71b%2C6b71d%2C6b76d%2C6b76f%2C6b774%2C6b7784%2C6b779c%2C6b77a01%2C6b782c%2C6b7834%2C6b785%2C6b78b4%2C6b78b9%2C6b78d%2C6b78f%2C6b794%2C6b79c%2C6b7a04%2C6b7a084%2C6b7a08c%2C6b7a091%2C6b7a093%2C6b7a09b%2C6b7a09d%2C6b7a0f4%2C6b7a0fc%2C6b7a104%2C6b7a109%2C6b7a10b%2C6b7a1c%2C6b7a21%2C6b7a23%2C6b7a244%2C6b7a25c%2C6b7a27%2C6b7a29%2C6b7a2b%2C6b7a2ec%2C6b7a2f3%2C6b7a2f5%2C6b7aa8c%2C6b7aa94%2C6b7aa9c%2C6b7aab%2C6b7aad%2C6b7aae4%2C6b7aaec%2C6b7aaf4%2C6b7aafb%2C6b7aafd%2C6b7aaff%2C6b7ab4%2C6b7ab84%2C6b7ab9c%2C6b7aba4%2C6b7ac43%2C6b7ac45%2C6b7ac4c%2C6b7ac54%2C6b7ac5c%2C6b7ac64%2C6b7ac6c%2C6b7ac7c%2C6b7acc%2C6b7ad4%2C6b7ad9%2C6b7adb%2C6b7adc1%2C6b7adc7%2C6b7adec%2C6b7adf4%2C6b7b05%2C6b7b07%2C6b7b0c%2C6b7b14%2C6b7b19%2C6b7b1b%2C6b7b20c%2C6b7b214%2C6b7b219%2C6b7b21b%2C6b7b23%2C6b7b25%2C6b7b27%2C6b7b2c%2C6b7b34%2C6b7b3c%2C6b7b5%2C6b7b7%2C6b7b9%2C6b7ba4%2C6b7ba9%2C6b7baf%2C6b7bb1%2C6b7bb7%2C6b7bbc%2C6b7bc4%2C6b7bc9%2C6b7bcf%2C6b7bd1%2C6b7bd43%2C6b7bd45%2C6b7bd4d%2C6b7bd4f%2C6b7bd54%2C6b7bd5c%2C6b7bd7%2C6b7bdc%2C6b7bf%2C6b7c04%2C6b7c0c%2C6b7c11%2C6b7c13%2C6b7c144%2C6b7c14c%2C6b7c151%2C6b7c153%2C6b7c15c%2C6b7c164%2C6b7c16c%2C6b7c174%2C6b7c179%2C6b7c17b%2C6b7c183%2C6b7c185%2C6b7c18c%2C6b7c194%2C6b7c19c%2C6b7c1b%2C6b7c1d%2C6b7c1e4%2C6b7c1ec%2C6b7c1f4%2C6b7c1fb%2C6b7c1fd%2C6b7c603%2C6b7c605%2C6b7c60d%2C6b7c60f%2C6b7c614%2C6b7c61c%2C6b7c63%2C6b7c65%2C6b7c664%2C6b7c66c%2C6b7c674%2C6b7c67b%2C6b7c67d%2C6b7c69%2C6b7c6a3%2C6b7c6a5%2C6b7c6ac%2C6b7c6b4%2C6b7c6bc%2C6b7c6d%2C6b7c6f%2C6b7c74%2C6b7c7c%2C6b7c84%2C6b7c89%2C6b7c8a4%2C6b7c8ac%2C6b7c8b1%2C6b7c8b7%2C6b7c8bc%2C6b7c8c4%2C6b7c8c9%2C6b7c8cf%2C6b7c8d1%2C6b7c8d5%2C6b7c8d7%2C6b7c8dc%2C6b7c8f%2C6b7c94%2C6b7c9c%2C6b7cb%2C6b7cd%2C6b7ce4%2C6b7cec%2C6b7cf04%2C6b7cf09%2C6b7cf0f%2C6b7cf14%2C6b7cf1c%2C6b7cf24%2C6b7cf2c%2C6b7cfa3%2C6b7cfa5%2C6b7cfa7%2C6b7cfac%2C6b7cfb4%2C6b7cfbc%2C6b7cfd%2C6b7cfe1%2C6b7cfe7%2C6b7d014%2C6b7d01c%2C6b7d03%2C6b7d05%2C6b7d064%2C6b7d06c%2C6b7d07b%2C6b7d07d%2C6b7d084%2C6b7d08c%2C6b7d094%2C6b7d099%2C6b7d09b%2C6b7d09f%2C6b7d0b%2C6b7d0d%2C6b7d0f%2C6b7d14%2C6b7d1c%2C6b7d3%2C6b7d5%2C6b7d7%2C6b7d84%2C6b7d8c%2C6b7d9d4%2C6b7d9dc%2C6b7d9e1%2C6b7d9e3%2C6b7d9fd%2C6b7d9ff%2C6b7da04%2C6b7df4%2C6b7dfc%2C6b7e04%2C6b7e154%2C6b7e15c%2C6b7e1c%2C6b7e3%2C6b7e5%2C6b7e61%2C6b7e624%2C6b7e663%2C6b7e665%2C6b7e66c%2C6b7e674%2C6b7e67c%2C6b7e684%2C6b7e689%2C6b7e68f%2C6b7e69c%2C6b7e6a4%2C6b7e6a9%2C6b7e6ab%2C6b7e6af%2C6b7e893%2C6b7e895%2C6b7e897%2C6b7e89c%2C6b7e8b%2C6b7e8d%2C6b7e8e4%2C6b7e8ec%2C6b7e903%2C6b7e905%2C6b7e90d%2C6b7e90f%2C6b7e914%2C6b7e91c%2C6b7e93%2C6b7e95%2C6b7e97%2C6b7ea05%2C6b7ea07%2C6b7ea0c%2C6b7ea14%2C6b7ea1c%2C6b7ea3%2C6b7ea5%2C6b7ea7%2C6b7eac%2C6b7eb4%2C6b7ebc%2C6b7ed%2C6b7ef%2C6b7f1%2C6b7f3%2C6b7f44%2C6b7f4c%2C6b7f7%2C6b7fc%2C6b8001%2C6b80021%2C6c7e2c%2C6c7e33%2C6c7fcd5%2C6c7fd4%2C6c7fdc%2C6c7fe4%2C6c7ffc%2C6c804%2C6c8084%2C6c808c%2C6c80f4%2C6c80fc%2C6c8104%2C6c810c%2C6c8174%2C6c817c%2C6c81c%2C6c824%2C6c82c%2C6c8304%2C6c831c%2C6c8324%2C6c832c%2C6c83ac%2C6c83b4%2C6c83cc%2C6c83d4%2C6c9cd4%2C6c9d3%2C6c9d5