Intersection of polygon borders

[iskandari]

Given a polygon from an s2 cell, and a polygon from an s2 cell union, what methods could be used to check whether the borders of these cells intersect? In the below example, the both red and green cells are contained by the yellow union, but only the green cell's borders intersect the union's borders.

I have tried using S2ShapeIndex but this does not work. I would be grateful for any suggestions!

bool checkIntersection(const std::vector<uint64_t>& cell_union_ids, uint64_t cell_id) {
    std::vector<S2CellId> cell_ids;
    for (auto id : cell_union_ids) {
        cell_ids.push_back(S2CellId(id));
    }
    S2CellUnion cell_union;
    cell_union.Init(cell_ids);

    S2Cell cell(S2CellId(cell_id));
    S2Polygon cell_polygon(S2Cell(cell));

    S2Polygon cell_union_polygon;
    cell_union_polygon.InitToCellUnionBorder(cell_union);

    S2BooleanOperation::Options options;
    S2PolygonLayer::Options poly_options;
    S2PolygonLayer result_layer(&cell_polygon, poly_options);

    S2ShapeIndex cell_index;
    cell_index.Add(absl::make_unique<S2Polygon::Shape>(&cell_polygon));
    S2ShapeIndex union_index;
    union_index.Add(absl::make_unique<S2Polygon::Shape>(&cell_union_polygon));

    S2BooleanOperation op(S2BooleanOperation::OpType::INTERSECT, &result_layer, options);
    bool intersected = op.Build(&cell_index, &union_index);

    return intersected && !cell_polygon.is_empty();
}

[smcallis]

To avoid the A/B problem can you elaborate on your ultimate goal? I wouldn't treat S2Cells as polygons at all in this case. If you have an S2CellUnion you can check if it contains another cell with S2CellUnion::Contains. If you want to be sure that it's on the boundary of the S2CellUnion I'd have to give it some more thought.

Doing it as polygons will invoke the degeneracy rules for edges, since it's pretty likely that the edges shown will be co-linear, we have to invoke symbolic perturbation to break the tie, so you'll end with effectively a 50/50 change of coincident cell edges actually testing as crossing.

[iskandari]

Sure, the original problem A is that in my application, a user will be adding or subtracting cells from a cell union. Naturally, they will only see the union's exterior which is made up of the vertices from polygon.InitToCellUnionBorder(cell_union); (the yellow polygon).

The constraint is that holes must be avoided which limits the cells that may be subtracted. Cells that are contained by the union but do not border it must not be subtracted. Cells that are contained by the union and border it may be subtracted. My objective is to determine whether an S2Cell boundary is on the boundary of an S2CellUnion. Another way to construct the problem would be to determine whether any vertex of an S2Cell intersects any of the outer edges of the S2CellUnion.

[smcallis]

So you can think of an S2CellUnion as a sorted set of cell ids, so like an absl::btree_set<S2CellId>. So if you want to remove things from that set you can. In fact S2CellUnion has a Difference method to subtract another cell union from it.

Can we go back even one more layer and elaborate on why users need to add and subtract cells from a cell union? Do they need to be able to only affect the perimeter? This will all be easier if we can avoid turning anything into a polygon.

[iskandari]

Exactly, users need to be able to change only the perimeter of a cell union through subtraction or addition. Nearby cells that intersect but are not contained by the union should be able to be added (such as the blue cell in the image below), thereby changing the perimeter. Each addition/subtraction operation will result in a perimeter change. It is also worth mentioning that the levels are constrained to 5-15, so only cells that fall within that range are allowed to be added or subtracted. Is it possible to create a btree_set for all parents and children of each cell within a cell union within a specific level range (5, 15)? That may be far more computationally expensive but would solve the problem.

[smcallis]

But why is that? What does toggling the perimeter of a cell union achieve?

…

On Fri, May 3, 2024 at 2:26 PM Alexander Tedeschi ***@***.***> wrote: Exactly, users need to be able to change only the perimeter of a cell union through subtraction or addition. Nearby cells that intersect but are not contained by the union should be able to be added (such as the blue cell in the image below) Screenshot.2024-05-03.at.4.23.31.PM.png (view on web) <https://github.com/google/s2geometry/assets/8308461/f19eae52-460f-40e9-993a-39a8df3728b8> — Reply to this email directly, view it on GitHub <#364 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGEMKRW2DJRCNHD32OEJ6DZAPXGXAVCNFSM6AAAAABHGBPLDWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDAOJTG4YTKMRRGY> . You are receiving this because you commented.Message ID: ***@***.***>

[iskandari]

It allows one to edit the geometry of large geographic areas approximated by s2 coverage using the same s2 cell conventions. Given some complex polygon that represents a natural boundary, It is much easier and faster to approximate this area as a set of cell ids (to which new cell ids can be added) than to store and fetch the geometries of very complex shapes. Ultimately the cell union perimeters will be editable in a web map application. Under the hood we perform our s2 operations, but to the user it will appear as a single polygon without holes. Does this make sense?

[smcallis]

Yes I think so, though I don't have all the details. My best thought would be to convert the cell boundaries to IJ coordinates (using S2Cell::GetIJCoordOfEdge()), which will make all the cell edges a range in I or J coordinates, which you could then track as a set. If you toggle each I/J range as you add cells, when you're done adding all the cells from the union, the only surviving ranges will be the perimeter, then you can update that as you go.

[benguild]

I actually ran into some flavor of this while debugging #464… in that S2BooleanOperation::INTERSECTION with IntLatLngSnapFunction can produce S2LaxPolygonShape(s) containing degenerate loops (2-vertex sibling edge pairs) that share vertices with other loops in the same shape, directly violating the requirement stated in "s2lax_polygon_shape.h" and causing a crash:

To be valid for boolean operations, degenerate edges and sibling pairs cannot coincide with any other edges.

The bug breaks composition of multi-step geometric computations since intermediate results cannot be safely reused, and stems from mixing geometries with inconsistent snap functions… when vertices near polygon boundaries get snapped to different coordinate grids. The algorithm can split nearly-coincident edges into a separate degenerate loop without properly isolating the shared vertices, and manifests when boundary edges from differently-snapped (or unsnapped) geometries align closely enough that snapping makes them overlap.

What makes this particularly concerning is there's no obvious way to detect it at the API level… the operation silently produces outputs that violate the library's own invariants, creating a landmine for downstream operations.

[jmr]

S2BooleanOperation::INTERSECTION with IntLatLngSnapFunction can produce S2LaxPolygonShape(s) containing degenerate loops (2-vertex sibling edge pairs) that share vertices with other loops in the same shape, directly violating the requirement stated in "s2lax_polygon_shape.h" and causing a crash

Can you file a new bug for this with your (ideally minimal) reproducer?

[benguild]

Can you file a new bug for this with your (ideally minimal) reproducer?

#474

[ericveach]

Regarding the original question that was asked, probably the fastest way to do it is the following. Let x be the original S2CellUnion. Construct a new S2CellUnion y = S2CellUnion::WholeSphere().Difference(x), i.e. the complement of the original S2CellUnion. Then construct an S2CellIndex for each S2CellUnion (which is very fast). Now given a cell "c", you can test whether it is on the border by using S2ClosestCellQuery to measure the distance "c" to "x" and then to "y". If both distances are zero, then "c" is on the boundary between them.