`S2BooleanOperation` output geometry validation concern (crash from duplicate polygon edges)

[benguild]

OK, so in follow up to #474 and #464…

This is very difficult to intentionally reproduce, but easy for me to sporadically reproduce. I've finally been able to reproduce it consistently in a standalone instance using particular polygon inputs and code shared below. There are two different failures included.

Core issue

As noted in the title, what comes back from intersection/union/difference at times can be invalid and crash a subsequent S2BooleanOperation operation for example.

There's limited ways to mitigate this when using S2LaxPolygonShape … compared to S2Polygon which offers not only an "IsValid()" check but by default will run that in debug builds unless disabled. (S2Debug::DISABLE etc.)

Reproducing the problem

I was able to reproduce this by looping some cells from level 0 to N (in this case level 5) and recursively performing intersections on each result using both S2LaxPolygonShape and S2Polygon in parallel to show the differences.

In this case, "IsValid()" on S2Polygon alerts us one or two levels prior to S2LaxPolygonShape causing a crash that the geometry has become invalid in that case.

From what I can tell…

• S2BooleanOperation does NOT (always/sufficiently) validate its output before returning success.
• When that invalid output geometry is then input to S2BooleanOperation … it can crash on internal CHECK() failures.
• This can only be detected using "IsValid()" on S2Polygon …as far as I can tell?

Code is here, note that a "polygon.txt" input is necessary and I've included two examples below alongside their output as noted above:

#include <fstream>
#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include <vector>

#include "s2/s2lax_polygon_shape.h"
#include "s2/s2polygon.h"
#include "s2/s2loop.h"
#include "s2/s2builder.h"
#include "s2/s2builderutil_lax_polygon_layer.h"
#include "s2/s2builderutil_snap_functions.h"
#include "s2/s2boolean_operation.h"
#include "s2/s2cell_id.h"
#include "s2/s2cell.h"
#include "s2/s2error.h"
#include "s2/s2latlng.h"
#include "s2/mutable_s2shape_index.h"

constexpr const char* INPUT_FILE = "polygon.txt";
constexpr int kSnapTolerance = 10;

constexpr uint64_t kCellPath[] = {
    0x7000000000000000ULL, // Level 0: Face 3
    0x6c00000000000000ULL, // Level 1
    0x6d00000000000000ULL, // Level 2
    0x6c40000000000000ULL, // Level 3
    0x6c30000000000000ULL, // Level 4
    0x6c24000000000000ULL  // Level 5
};

int main() {
    std::vector<int> loopSizes;
    std::vector<std::pair<double, double>> coords;

    std::ifstream file(INPUT_FILE);
    if (!file.is_open()) {
        std::cerr << "ERROR: Cannot open " << INPUT_FILE << "\n";
        std::cerr << "Please ensure the polygon data file exists.\n";
        return 1;
    }

    std::string line;
    std::getline(file, line); // "Header"

    if (std::getline(file, line)) {
        size_t start = line.find('[');
        size_t end = line.find(']');
        if (start != std::string::npos && end != std::string::npos) {
            std::istringstream iss(line.substr(start + 1, end - start - 1));
            int size;
            while (iss >> size) {
                loopSizes.push_back(size);
            }
        }
    }

    std::getline(file, line); // "Total Vertices"

    while (std::getline(file, line)) {
        if (line.empty()) continue;
        size_t comma = line.find(',');
        if (comma != std::string::npos) {
            coords.push_back({
                std::stod(line.substr(0, comma)),
                std::stod(line.substr(comma + 1))
            });
        }
    }

    std::cout << "  Vertices: " << coords.size() << "\n";
    std::cout << "  Loops: " << loopSizes.size() << " [";
    for (size_t i = 0; i < loopSizes.size(); i++) {
        if (i > 0) std::cout << ", ";
        std::cout << loopSizes[i];
    }
    std::cout << "]\n\n";

    std::vector<S2Point> points;
    for (const auto& coord : coords) {
        points.push_back(
            S2LatLng::FromDegrees(coord.first, coord.second).ToPoint()
        );
    }

    auto result = std::make_unique<S2LaxPolygonShape>();

    S2Builder::Options builderOpts{
        s2builderutil::IntLatLngSnapFunction(kSnapTolerance)
    };
    S2Builder builder{builderOpts};
    builder.StartLayer(
        std::make_unique<s2builderutil::LaxPolygonLayer>(result.get())
    );

    size_t pointIndex = 0;
    for (int loopSize : loopSizes) {
        for (int i = 0; i < loopSize; i++) {
            builder.AddEdge(
                points[pointIndex + i],
                points[pointIndex + ((i + 1) % loopSize)]
            );
        }
        pointIndex += loopSize;
    }

    S2Error error;
    if (!builder.Build(&error)) {
        std::cerr << "ERROR: Failed to build polygon: " << error << "\n";
        return 1;
    }

    std::cout << "  S2 polygon built: " << result->num_loops() << " loop(s)\n";
    std::cout << "  ✓ Input geometry is VALID\n\n";

    for (int level = 0; level < 6; level++) {
        uint64_t cellId = kCellPath[level];

        std::cout << "Step " << (level + 1) << ": Level " << level;
        if (level == 0) std::cout << " → Face 3";
        std::cout << "\n";
        std::cout << "  Cell: 0x" << std::hex << cellId << std::dec << "\n";

        S2CellId s2CellId(cellId);
        S2Cell cell(s2CellId);

        auto cellShape = std::make_unique<S2LaxPolygonShape>();

        S2Builder::Options cellBuilderOpts{
            s2builderutil::IntLatLngSnapFunction(kSnapTolerance)
        };
        S2Builder cellBuilder{cellBuilderOpts};
        cellBuilder.StartLayer(
            std::make_unique<s2builderutil::LaxPolygonLayer>(cellShape.get())
        );

        for (int i = 0; i < 4; i++) {
            cellBuilder.AddEdge(
                cell.GetVertex(i),
                cell.GetVertex((i + 1) % 4)
            );
        }

        if (!cellBuilder.Build(&error)) {
            std::cerr << "ERROR: Failed to build cell: " << error << "\n";
            return 1;
        }

        std::cout << "  " << (level == 0 ? "Polygon" : "Result")
                  << " ∩ Cell... ";
        std::cout.flush();

        auto newResult = std::make_unique<S2LaxPolygonShape>();

        MutableS2ShapeIndex indexA;
        int shapeIdA = indexA.Add(std::move(result));

        MutableS2ShapeIndex indexB;
        int shapeIdB = indexB.Add(std::move(cellShape));

        s2builderutil::LaxPolygonLayer::Options layerOpts;
        layerOpts.set_degenerate_boundaries(
            s2builderutil::LaxPolygonLayer::Options::DegenerateBoundaries::DISCARD
        );

        S2BooleanOperation::Options opOpts;
        opOpts.set_snap_function(
            s2builderutil::IntLatLngSnapFunction(kSnapTolerance)
        );

        S2BooleanOperation op(
            S2BooleanOperation::OpType::INTERSECTION,
            std::make_unique<s2builderutil::LaxPolygonLayer>(
                newResult.get(),
                layerOpts
            ),
            opOpts
        );

        bool success = op.Build(indexA, indexB, &error);

        result.reset(
            static_cast<S2LaxPolygonShape*>(indexA.Release(shapeIdA).release())
        );
        cellShape.reset(
            static_cast<S2LaxPolygonShape*>(indexB.Release(shapeIdB).release())
        );

        if (!success) {
            std::cerr << "ERROR: " << error << "\n";
            return 1;
        }

        std::cout << newResult->num_loops() << " loop(s) ✓\n";

        if (newResult->num_loops() == 0) {
            std::cerr << "ERROR: No intersection at Level " << level << "\n";
            return 1;
        }

        std::cout << "  Validating with `S2Polygon`... ";
        std::cout.flush();

        std::vector<std::unique_ptr<S2Loop>> loops;

        for (int i = 0; i < newResult->num_loops(); i++) {
            int numVertices = newResult->num_loop_vertices(i);
            std::vector<S2Point> vertices;

            for (int j = 0; j < numVertices; j++) {
                vertices.push_back(newResult->loop_vertex(i, j));
            }

            auto loop = std::make_unique<S2Loop>(vertices);
            loops.push_back(std::move(loop));
        }

        auto polygon = std::make_unique<S2Polygon>();
        polygon->set_s2debug_override(S2Debug::DISABLE);
        polygon->InitOriented(std::move(loops));

        if (!polygon->IsValid()) {
            S2Error validationError;
            polygon->FindValidationError(&validationError);

            std::cout << "INVALID\n";
            std::cout << "    ✗ `S2Polygon::IsValid()` returned FALSE\n";
            std::cout << "    ✗ `S2Polygon::FindValidationError()` says:\n";
            std::cout << "      \"" << validationError << "\"\n";
        } else {
            std::cout << "✓\n";
        }

        std::cout << "\n";

        result = std::move(newResult);
    }

    std::cout << "SUCCESS: No crash (unexpected!)\n";

    return 0;
}

Example 1: "Check failed: abs(e.second) <= 1 (2 vs. 1)"

Input: (as "polygon.txt")

Polygon
LoopSizes: [242 60 24]
TotalVertices: 326
52.28954425807473,171.47111117465545
52.70200282563701,169.5405761663112
51.95274976690291,168.38603627005386
50.02995318787981,165.1369848885696
50.02995318787981,163.64132368490493
50.02995318787981,162.44479472197315
50.01726272918205,161.12837994660154
50.00615857782151,159.97651701815107
49.982363967763035,157.508239314329
49.057118871150315,157.508239314329
34.550338873572436,157.508239314329
33.79276311529111,157.508239314329
31.368520688791005,157.508239314329
30.610944930509675,157.508239314329
23.641247954321823,157.508239314329
22.883672196040493,157.508239314329
22.126096437759184,157.508239314329
19.701854011259,157.508239314329
18.94427825297773,157.508239314329
18.344572350903945,157.508239314329
17.89638160048662,157.508239314329
14.121212218182714,157.508239314329
11.99973765102292,154.28944524226014
11.519009062928319,153.99682988738834
11.358774153077775,153.99683065006946
11.19853924322723,153.99683141275057
9.43595523487113,153.9968398022431
7.192666496963341,153.99685047977903
6.391491947710449,153.9968542931848
3.827733390101514,153.99686649608304
3.026558840848793,153.99687030948874
1.744679562044439,153.99687641093794
1.2639748324927307,153.99687869898128
-0.01790444631177479,153.9968848004304
-0.020663916200192034,155.9999843129243
-0.021535166200957672,156.63232139684672
-0.3200379738985741,157.5175933143379
-1.9550947912288354,157.5175933143379
-3.1442270220146042,157.5175933143379
-3.5901516085592675,158.22053120699977
-3.5901516085592675,159.2046442567264
-3.5901516085592675,159.9075821493881
-4.798363225597939,159.60293502220907
-4.871310513955223,158.2346563683319
-5.236644314180201,157.75661433233606
-6.07887967262197,156.65323332541865
-6.550000000000011,156.03583333333324
-6.847222222222172,155.9230555555556
-7.069273122300217,155.37854291999827
-7.6063949414409535,154.89894992423226
-8.428849718835068,154.8192240455246
-9.521693384873174,155.6882503295302
-13.890168148955524,157.5175933143379
-14.355879111368969,157.5175933143379
-18.44678902426985,157.5175933143379
-19.05284975210704,157.5175933143379
-19.810425540691387,157.5175933143379
-20.8710316022852,157.5175933143379
-21.62860736056649,157.5175933143379
-23.44678918044163,157.5175933143379
-25.568001303629273,157.5175933143379
-27.537698275160704,157.5175933143379
-28.446789185098243,157.5175933143379
-29.204364943379574,157.5175933143379
-29.961940701660847,157.5175933143379
-30.719516459942156,157.5175933143379
-31.174061914910947,157.5175933143379
-36.47709222288006,157.5175933143379
-36.7801225261926,157.5175933143379
-38.14375889109897,157.5175933143379
-39.2043649526928,157.5175933143379
-39.9104235594109,157.5175933143379
-41.72860537928608,157.5175933143379
-42.486181137567314,157.5175933143379
-45.21345386738005,157.5175933143379
-49.30436296209916,157.5175933143379
-50.0619387203804,157.5175933143379
-50.819514478661766,157.5175933143379
-51.577090236943036,157.5175933143379
-53.243756905161945,157.5175933143379
-54.46102966690167,157.5175933143379
-59.307394274445585,157.5175933143379
-60.82254579100811,157.5175933143379
-61.58012154928946,157.5175933143379
-63.246788217508346,157.5175933143379
-65.974060947321,157.5175933143379
-67.94375791885244,157.5175933143379
-69.01487692089353,157.76313576013075
-69.1464213165566,158.70517586754795
-69.28532042365515,159.50938906186911
-69.74863174651665,160.80331205117625
-70.0976516129179,161.31830534848973
-70.10134199402228,162.68147453061533
-70.18298135704163,163.67945862016734
-70.32347585887794,164.07557066118693
-70.43843580222304,166.04647283199353
-70.45465447896112,166.89135160258377
-72.8846936666373,170.37665353437256
-73.469121042518,168.90175576460297
-73.42595716163652,168.70125723164153
-73.8305989769479,166.81996801395547
-74.07231673553275,165.95463474217888
-74.36622006404997,165.9178833764787
-74.76343541387996,164.77973858750602
-74.96388308046687,164.54392248223178
-75.06920315293388,164.0109451529969
-75.32770721933059,163.17706291060654
-75.78537720496513,163.62023778097193
-76.08284303459612,163.48463818501716
-76.82008384125339,163.76063568633606
-77.00408006993678,163.95641265359382
-77.1882284068243,164.2598492702807
-77.27194276175436,164.36091028805458
-77.54634489791056,164.66207739413267
-77.82583501223291,165.74328024362433
-77.24211903497326,165.57657430794927
-76.75096924001315,166.68266065868784
-76.98969359663238,167.78110509002238
-77.16481113042022,167.8873468173747
-77.1900265152168,168.23083319273778
-77.41604429833592,170.13610486458833
-77.54993207347188,171.5298317560413
-76.56423069827308,172.50779660742032
-76.272258310746,172.50794271040309
-74.81239637311047,172.50867322531687
-73.76284822730217,172.50919857072412
-72.09618155908328,172.5100329040582
-71.64163610411447,172.51026044951308
-71.03557549748946,172.51056384345262
-70.73254519417696,172.51071554042244
-69.8234542842394,172.51117063133208
-65.42951488620781,172.51335714648565
-64.67193912792652,172.51373396466775
-62.68709210789611,172.51472672830505
-61.52042637347631,172.5153105283057
-60.18709410556786,172.5159777283062
-58.308306758363585,172.51691811618585
-56.03557948351969,172.5180558434595
-54.52042796695707,171.85993966102856
-54.52042796695707,169.74500402269553
-54.52042796695707,165.95712523128896
-54.52042796695707,165.19954947300752
-52.079972564684205,165.05208502135488
-51.246640563908024,165.05346852135617
-49.57997656235585,165.05623552135867
-47.24664696018285,165.06010932136243
-46.913314159872414,165.06066272136297
-46.07998215909627,165.06204622136434
-45.24665015832014,165.06342972136565
-44.41331815754404,165.06481322136688
-43.50933295670217,165.3231696966077
-42.43203695569887,166.0099066972471
-41.62406495494641,166.5249594477267
-38.71386815223607,168.3800993911211
-36.88684555053453,169.54475552553924
-35.059823282166256,170.70941665995701
-33.782185402188475,171.52386605465495
-33.27113025019738,171.84964581253416
-32.632311310208536,172.25687050988313
-31.434337167678695,172.50121366162577
-30.945527500556807,172.5012186616257
-30.313798611079505,172.50122549495904
-29.376213943539653,172.50123582829258
-22.96176954362632,172.5012917525349
-22.204193785344994,172.50129869192884
-20.23449681381362,172.50131641920174
-19.47692105553229,172.50132323738345
-17.50722408400094,172.50134096465612
-14.325405899219428,172.5013702070805
-13.5678301409381,172.50137717677737
-12.810254382656694,172.5013841464745
-10.53752710781282,172.50140505556544
-9.022375591250295,172.50141899495938
-7.8102543780000815,172.50143014647472
-6.143587709781343,172.5014454798081
-3.719345283281143,172.50146778283806
-3.1132846766561024,172.50147335859575
-2.3551539183743366,169.786827568189
-2.354812918374042,168.12016089997022
-2.354378918373527,165.9989487767823
-2.354259563815693,165.4154671288131
-2.3541277910264284,164.77078616381118
-2.3540223727950056,164.25504139180975
-1.1979333160752503,163.9962023356828
-0.04189696847127303,163.99523566555663
2.435323776394379,163.99316422957216
5.077692570917861,163.9909546978554
7.059469166810345,163.9892975490676
8.050357464756644,163.49848340660435
8.050357464756644,162.35518374777584
8.050357464756644,161.2118840889473
9.455046279344913,160.5597261576802
10.235428954116097,160.56036846850895
10.859735093932954,160.56088231717206
11.617310397668879,160.56182565050634
11.920340519163176,160.56220298384005
12.071855579910334,160.56239165050692
13.283976065887751,160.5639009838416
14.193066430370777,160.56503298384266
14.496096551865207,160.56541031717632
16.02639863207823,160.56731635051153
20.859754603246245,161.53675081808115
20.859785224458392,162.65166747063446
20.85982231536758,164.01530383554086
20.859838800216135,164.6213644421658
20.85985940627677,165.3789402004472
20.8598800123375,166.13651595872852
20.859900618398058,166.89409171700981
20.859942012337513,168.4092432335725
21.341241703694664,172.50035532829168
22.143221037774918,172.50069366162526
25.19074250727988,172.50197932829337
25.97496041104061,172.50230990405112
26.73253616932188,172.50262884344545
27.490111927603152,172.50294778283978
28.24768768588454,172.5032667222339
29.005263444165866,172.5035856616283
29.762839202447196,172.50390460102244
30.52041496072839,172.5042235404167
32.838595914402426,172.5051934282964
33.67192891517851,172.50554192829657
35.974958420353666,172.50650596466105
36.732534178635056,172.50682505557043
37.49010993691621,172.50714414647996
38.24768569519771,172.50746323738932
39.00526145347899,172.5077823282987
39.76283721176026,172.50810141920806
40.52041297004164,172.5084205101175
41.27798872832303,172.50873947981492
42.0355644866043,172.50905841920894
42.79314024488561,172.50937735860307
43.55071600316702,172.50969629799738
44.308291761448345,172.51001523739149
45.06586751972966,172.5103341767858
45.82344327801095,172.51065314648295
46.58101903629222,172.51097223739237
47.33859479457353,172.51129132830184
48.09617055285482,172.51161041921122
48.85374631113609,172.51192951012058
50.36889782769864,172.51256769193947
50.91088878990431,172.50762910756964
51.38879410769084,172.50643866611074
-28.0,167.0000000000001
-28.166666666666668,167.0000000000001
-28.333333333333332,167.0000000000001
-28.5,167.0000000000001
-28.666666666666668,167.0000000000001
-28.833333333333332,167.0000000000001
-29.0,167.0000000000001
-29.16666666666663,167.0000000000001
-29.333333333333258,167.0000000000001
-29.499999999999886,167.0000000000001
-29.666666666666572,167.0000000000001
-29.833333333333258,167.0000000000001
-29.999999999999943,167.0000000000001
-29.999999999999943,167.138888888889
-29.999999999999943,167.27777777777786
-29.999999999999943,167.41666666666674
-29.999999999999943,167.55555555555569
-29.999999999999943,167.69444444444466
-29.999999999999943,167.8333333333336
-29.999999999999943,167.97222222222248
-29.999999999999943,168.11111111111134
-29.999999999999943,168.25000000000023
-29.999999999999943,168.3888888888891
-29.999999999999943,168.52777777777797
-29.999999999999943,168.66666666666686
-29.999999999999943,168.80555555555574
-29.999999999999943,168.9444444444446
-29.999999999999943,169.08333333333348
-29.999999999999943,169.22222222222237
-29.999999999999943,169.36111111111123
-29.999999999999943,169.5000000000001
-29.833333333333258,169.5000000000001
-29.666666666666572,169.5000000000001
-29.499999999999886,169.5000000000001
-29.333333333333258,169.5000000000001
-29.16666666666663,169.5000000000001
-29.0,169.5000000000001
-28.833333333333332,169.5000000000001
-28.666666666666668,169.5000000000001
-28.5,169.5000000000001
-28.333333333333332,169.5000000000001
-28.166666666666668,169.5000000000001
-28.0,169.5000000000001
-28.0,169.36111111111123
-28.0,169.22222222222237
-28.0,169.08333333333348
-28.0,168.9444444444446
-28.0,168.80555555555574
-28.0,168.66666666666686
-28.0,168.52777777777797
-28.0,168.3888888888891
-28.0,168.25000000000023
-28.0,168.11111111111134
-28.0,167.97222222222248
-28.0,167.8333333333336
-28.0,167.69444444444466
-28.0,167.55555555555569
-28.0,167.41666666666674
-28.0,167.27777777777786
-28.0,167.138888888889
-31.000999999999976,158.5
-31.16749999999998,158.5
-31.333999999999985,158.5
-31.500499999999988,158.5
-31.66699999999999,158.5
-31.833499999999997,158.5
-32.0,158.5
-32.0,158.66666666666669
-32.0,158.83333333333337
-32.0,159.0
-32.0,159.16666666666663
-32.0,159.33333333333331
-32.0,159.5
-31.833333333333314,159.5
-31.66666666666663,159.5
-31.49999999999997,159.5
-31.333333333333314,159.5
-31.16666666666663,159.5
-30.999999999999943,159.5
-31.000166666666587,159.33333333333331
-31.00033333333323,159.16666666666663
-31.00049999999993,159.0
-31.000666666666632,158.83333333333337
-31.000833333333304,158.66666666666669

Output:

  Vertices: 326
  Loops: 3 [242, 60, 24]

  S2 polygon built: 3 loop(s)
  ✓ Input geometry is VALID

Step 1: Level 0 → Face 3
  Cell: 0x7000000000000000
  Polygon ∩ Cell... 3 loop(s) ✓
  Validating with `S2Polygon`... ✓

Step 2: Level 1
  Cell: 0x6c00000000000000
  Result ∩ Cell... 3 loop(s) ✓
  Validating with `S2Polygon`... ✓

Step 3: Level 2
  Cell: 0x6d00000000000000
  Result ∩ Cell... 3 loop(s) ✓
  Validating with `S2Polygon`... ✓

Step 4: Level 3
  Cell: 0x6c40000000000000
  Result ∩ Cell... 3 loop(s) ✓
  Validating with `S2Polygon`... WARNING: All log messages before absl::InitializeLog() is called are written to STDERR
E0000 00:00:1763005027.626485   58271 s2polygon.cc:228] One or more duplicate polygon edges detected
INVALID
    ✗ `S2Polygon::IsValid()` returned FALSE
    ✗ `S2Polygon::FindValidationError()` says:
      "One or more duplicate polygon edges detected"

Step 5: Level 4
  Cell: 0x6c30000000000000
  Result ∩ Cell... 2 loop(s) ✓
  Validating with `S2Polygon`... E0000 00:00:1763005027.630010   58271 s2polygon.cc:228] One or more duplicate polygon edges detected
INVALID
    ✗ `S2Polygon::IsValid()` returned FALSE
    ✗ `S2Polygon::FindValidationError()` says:
      "One or more duplicate polygon edges detected"

Step 6: Level 5
  Cell: 0x6c24000000000000
  Result ∩ Cell... F0000 00:00:1763005027.630402   58271 s2contains_vertex_query.cc:42] Check failed: abs(e.second) <= 1 (2 vs. 1) 
*** Check failure stack trace: ***
    @     0xffffa09a5f2c  absl::lts_20240116::log_internal::LogMessage::PrepareToDie()
    @     0xffffa09a5fa0  absl::lts_20240116::log_internal::LogMessage::SendToLog()
    @     0xffffa09a5a78  absl::lts_20240116::log_internal::LogMessage::Flush()
    @     0xffffa09a6224  absl::lts_20240116::log_internal::LogMessageFatal::~LogMessageFatal()
    @     0xffffa08726b0  S2ContainsVertexQuery::ContainsSign()
    @     0xffffa095c4c4  s2shapeutil::GetReferencePointAtVertex()
    @     0xffffa095c68c  s2shapeutil::GetReferencePoint()
    @     0xffffa08cca90  S2LaxPolygonShape::GetReferencePoint()
    @     0xffffa095ad74  s2shapeutil::ContainsBruteForce()
    @     0xffffa07705e0  MutableS2ShapeIndex::AddShape()
    @     0xffffa076f2d0  MutableS2ShapeIndex::ApplyUpdatesInternal()
    @     0xffffa076eff0  MutableS2ShapeIndex::ApplyUpdatesThreadSafe()
    @     0xffffa07753d0  MutableS2ShapeIndex::MaybeApplyUpdates()
    @     0xffffa077520c  MutableS2ShapeIndex::Iterator::Init()
    @     0xffffa07751cc  MutableS2ShapeIndex::Iterator::Iterator()
    @     0xffffa0777678  std::make_unique<>()
    @     0xffffa0775320  MutableS2ShapeIndex::NewIterator()
    @     0xffffa07a22e4  S2ShapeIndex::Iterator::Init()
    @     0xffffa07a222c  S2ShapeIndex::Iterator::Iterator()
    @     0xffffa07aac58  S2ContainsPointQuery<>::S2ContainsPointQuery()
    @     0xffffa07a7458  MakeS2ContainsPointQuery<>()
    @     0xffffa0799078  S2BooleanOperation::Impl::GetChainStarts()
    @     0xffffa0799c90  S2BooleanOperation::Impl::AddBoundaryPair()
    @     0xffffa0799ee4  S2BooleanOperation::Impl::BuildOpType()
    @     0xffffa079ae34  S2BooleanOperation::Impl::DoBuild()
    @     0xffffa079af2c  S2BooleanOperation::Impl::Build()
    @     0xffffa079b844  S2BooleanOperation::Build()
    @     0xaaaad3c8d008  main
    @     0xffff9fd87744  (unknown)
    @     0xffff9fd87818  __libc_start_main

Example 2: "Check failed: multiplicity == 0 || multiplicity == 1"

Input: (as "polygon.txt")

Polygon
LoopSizes: [485 13 6]
TotalVertices: 504
51.851019987190739,172.36846329397179
52.225402494129071,171.60278557609013
52.549763284663669,170.93476992455967
52.921847229447017,170.16223398692929
52.602552991482469,169.38733181199188
52.12045629142991,168.64445880323129
51.700694444444594,167.99763888888913
51.236341578353176,167.3570691487057
50.819575531313319,166.7642805416117
50.424764359596566,166.17498189564034
50.029953187879812,165.58568324966893
50.029953187879812,164.83785264783671
50.029953187879812,164.09002204600426
50.029953187879812,163.34219144417204
50.029953187879812,162.5943608423396
50.023607958530931,161.78658733428742
50.01567642184483,160.96382809968009
50.007744885158729,160.14106886507253
49.999813348472628,159.31830963046525
49.991881811786527,158.49555039585778
49.983950275100256,157.67279116125044
49.453652483984321,157.50823931432899
48.792763129260948,157.50823931432899
48.035187370979678,157.50823931432899
47.277611612698401,157.50823931432899
46.520035854417074,157.50823931432899
45.762460096135804,157.50823931432899
45.004884337854513,157.50823931432899
44.2473085795732,157.50823931432899
43.489732821291874,157.50823931432899
42.732157063010526,157.50823931432899
41.974581304729327,157.50823931432899
41.217005546448,157.50823931432899
40.459429788166666,157.50823931432899
39.701854029885283,157.50823931432899
38.944278271604013,157.50823931432899
38.186702513322736,157.50823931432899
37.429126755041409,157.50823931432899
36.671550996760139,157.50823931432899
35.913975238478862,157.50823931432899
35.156399480197592,157.50823931432899
34.398823721916209,157.50823931432899
33.641247963634875,157.50823931432899
32.883672205353548,157.50823931432899
32.126096447072335,157.50823931432899
31.368520688791005,157.50823931432899
30.610944930509675,157.50823931432899
29.853369172228366,157.50823931432899
29.095793413947074,157.50823931432899
28.338217655665801,157.50823931432899
27.580641897384435,157.50823931432899
26.823066139103258,157.50823931432899
26.065490380821927,157.50823931432899
25.307914622540654,157.50823931432899
24.550338864259327,157.50823931432899
23.792763105978054,157.50823931432899
23.03518734769678,157.50823931432899
22.277611589415489,157.50823931432899
21.52003583113418,157.50823931432899
20.762460072852907,157.50823931432899
20.004884314571616,157.50823931432899
19.247308556290307,157.50823931432899
18.493969267709776,157.50823931432899
17.746984683680768,157.50823931432899
17.000000099651572,157.50823931432899
16.242424341370299,157.50823931432899
15.484848583089009,157.50823931432899
14.727272824807699,157.50823931432899
13.969697066526427,157.50823931432899
13.212121308245154,157.50823931432899
12.454545549963825,157.50823931432899
11.999976236452104,157.21562167141371
11.99991659009485,156.48407756412533
11.999856943737541,155.75253345683689
11.999797297380175,155.02098934954861
11.999737651022921,154.28944524226014
11.519009062928319,153.99682988738834
10.717834513675561,153.9968337007939
9.9166599644227063,153.99683751419968
9.1154854151699283,153.99684132760547
8.3143108659172071,153.99684514101102
7.5131363166644674,153.99684895441681
6.7119617674115375,153.99685276782259
5.9107872181588164,153.99685658122814
5.1096126689060952,153.99686039463393
4.3084381196533741,153.99686420803971
3.5072635704004256,153.99686802144527
2.7060890211477044,153.99687183485105
1.9049144718949833,153.99687564825683
1.1037399226421105,153.99687946166239
0.30256537338931366,153.99688327506817
-0.018456340289390027,154.39750470292915
-0.0193761635856049,155.06520454042729
-0.020295986881706085,155.73290437792522
-0.021186666200605941,156.37938656327776
-0.022057916201485266,157.01172364720003
-0.17139644505035298,157.51759331433789
-0.91460408929140158,157.51759331433789
-1.6578117335324123,157.51759331433789
-2.4010193777735176,157.51759331433789
-3.1442270220146042,157.51759331433789
-3.5901516085592675,157.7987684714027
-3.5901516085592675,158.50170636406446
-3.5901516085592675,159.2046442567264
-3.5901516085592675,159.90758214938811
-4.1163275437826883,160.05299558521577
-4.7740474628122342,160.05902790683467
-4.8145737341217796,159.29887309912525
-4.8551000054313818,158.53871829141579
-5.1453108641239282,157.87612484133513
-5.6077593452439105,157.27063331750381
-6.0788796726219703,156.65323332541865
-6.5500000000000114,156.03583333333324
-6.8865277777777294,155.80833333333345
-7.1579698944834149,155.24538257111021
-7.4742436768012226,154.97729851640136
-8.1350000000000477,154.58555555555563
-8.8696242970877677,155.16972678047819
-9.6900747943291776,155.82214676421938
-10.531981841608996,156.49162893766527
-11.373888888888928,157.16111111111115
-12.091694967717254,157.4581796138001
-12.790482917366205,157.51759331433789
-13.575972368501406,157.51759331433789
-14.355879111368969,157.51759331433789
-15.113455021165464,157.51759331433789
-15.871030930961828,157.51759331433789
-16.628606840758323,157.51759331433789
-17.386182750554781,157.51759331433789
-18.143758660351256,157.51759331433789
-18.901334570147736,157.51759331433789
-19.658910389035157,157.51759331433789
-20.416486147316391,157.51759331433789
-21.174061905597721,157.51759331433789
-21.93163766387903,157.51759331433789
-22.689213422160339,157.51759331433789
-23.44678918044163,157.51759331433789
-24.204364938722961,157.51759331433789
-24.961940697004234,157.51759331433789
-25.719516455285543,157.51759331433789
-26.477092213566834,157.51759331433789
-27.234667971848182,157.51759331433789
-27.992243730129474,157.51759331433789
-28.749819488410708,157.51759331433789
-29.507395246692113,157.51759331433789
-30.264971004973347,157.51759331433789
-31.022546763254695,157.51759331433789
-31.780122521535986,157.51759331433789
-32.537698279817313,157.51759331433789
-33.295274038098626,157.51759331433789
-34.052849796379938,157.51759331433789
-34.810425554661187,157.51759331433789
-35.568001312942499,157.51759331433789
-36.325577071223812,157.51759331433789
-37.083152829505138,157.51759331433789
-37.84072858778643,157.51759331433789
-38.598304346067778,157.51759331433789
-39.304362952785937,157.51759331433789
-40.061938711067171,157.51759331433789
-40.81951446934854,157.51759331433789
-41.57709022762981,157.51759331433789
-42.33466598591108,157.51759331433789
-43.092241744192449,157.51759331433789
-43.849817502473798,157.51759331433789
-44.607393260755011,157.51759331433789
-45.364969019036344,157.51759331433789
-46.122544777317614,157.51759331433789
-46.880120535598962,157.51759331433789
-47.637696293880218,157.51759331433789
-48.395272052161602,157.51759331433789
-49.152847810442914,157.51759331433789
-49.910423568724127,157.51759331433789
-50.667999327005532,157.51759331433789
-51.425575085286766,157.51759331433789
-52.183150843568079,157.51759331433789
-52.940726601849406,157.51759331433789
-53.698302360130754,157.51759331433789
-54.461029666901673,157.51759331433789
-55.244363167631207,157.51759331433789
-56.027696668360726,157.51759331433789
-56.811030169090316,157.51759331433789
-57.59436366981987,157.51759331433789
-58.377697170549403,157.51759331433789
-59.155879122789315,157.51759331433789
-59.91345488107055,157.51759331433789
-60.671030639351876,157.51759331433789
-61.428606397633189,157.51759331433789
-62.18618215591448,157.51759331433789
-62.943757914195828,157.51759331433789
-63.701333672477119,157.51759331433789
-64.458909430758467,157.51759331433789
-65.216485189039744,157.51759331433789
-65.974060947320993,157.51759331433789
-66.731636705602341,157.51759331433789
-67.489212463883632,157.51759331433789
-68.246788222164966,157.51759331433789
-69.004363980446271,157.51759331433789
-69.005504616097824,158.01170851077325
-69.115994473214784,158.61555685377209
-69.202246474338097,159.16484814984221
-69.33865200347546,159.81057162638871
-69.544489121519575,160.44909130852636
-69.780182814951786,160.82099499911624
-70.030438055237255,161.21693765211683
-70.085950917291143,161.52739600375298
-70.063771085016583,162.08196226287271
-70.101341994022278,162.68147453061533
-70.168077917502217,163.38172688948583
-70.259531954001545,163.96755491584179
-70.341386700064817,164.50638324327633
-70.391460975088535,165.22038497102835
-70.43843580222304,166.04647283199353
-70.44528212163533,166.70449144837937
-70.537227374347879,167.2067637171865
-70.612358591883293,167.73164632157489
-70.901503731085995,168.39731593397084
-71.004292975190424,168.74922370030072
-71.181127221379796,169.36744699648403
-71.153244669006597,169.91976452081951
-71.140285338746423,170.53519832267602
-71.445576717852362,171.04049333938821
-71.783951772673731,171.50854570134322
-72.045480575923534,171.25580310536884
-72.188607822443771,170.77100895594515
-72.515645518147721,170.88810636568746
-72.7615779846534,170.54569259556456
-73.083015135298524,170.22703182214332
-73.256473492890791,170.36272104374825
-73.571248930464037,170.5495215028576
-73.786550992325999,170.02041018812065
-73.786198874553406,169.34833887603338
-73.62295401347285,168.87607713641182
-73.461549614464843,168.89616817785873
-73.427994131734295,168.50731344253211
-73.64517022506638,167.82633231500449
-73.732710690581513,167.24607955008946
-73.890619646652453,166.72156256798417
-74.015866576737324,166.19341902341881
-74.324552107512773,165.79524108506951
-74.550683444546962,166.14316223794469
-74.793150560444474,165.76699829023971
-74.795207470619346,165.07120743088626
-75.000396970913016,164.41907781020427
-75.089908672408058,163.76698586910072
-75.193788566863248,163.34907526983454
-75.409901631238768,163.39181383653244
-75.575871535951194,163.69310407791738
-75.835758939317941,163.63635955813925
-76.147518929254943,163.43372539911616
-76.389664925185116,163.62764734794814
-76.623629417401673,163.63400782747931
-76.894996219446,163.679444719343
-77.049009935988522,163.97719410844445
-77.298797533679931,164.42190017996495
-77.546344897910558,164.66207739413267
-77.710284948790218,165.04704346305198
-77.837675510506074,165.63123052805429
-77.761746942279217,165.62137763319663
-77.542561495623204,165.31297205389058
-77.370045199552692,165.68200810236806
-77.1868364782149,165.62594439421434
-76.966878440222843,166.05103296594973
-76.78523448025112,166.36440278022746
-76.746157588749554,166.94218353779115
-76.815063197142138,167.54684086841132
-76.960682422063087,167.79141576807774
-77.111245478794729,167.73200872011688
-77.1900265152168,168.23083319273778
-77.230863786478892,168.99472581132829
-77.281802580837109,169.63399439916486
-77.416044298335919,170.13610486458833
-77.513730092326014,170.55237826510154
-77.539588650287328,171.25055933005854
-77.565447208248727,171.94874039501534
-77.440147860854282,172.50735829847221
-76.710216892036613,172.50772355592892
-75.980285923218887,172.5080888133858
-75.250354954401089,172.50845407084273
-74.520423985583477,172.50881932829941
-73.762848227302172,172.50919857072412
-73.005272469020838,172.50957781314875
-72.247696710739547,172.50995705557318
-71.490120952458199,172.51033629799795
-70.732545194176964,172.51071554042244
-69.974969435895673,172.51109478284718
-69.217393677614325,172.51147305557473
-68.459817919333034,172.51184987375709
-67.702242161051686,172.5122266919393
-66.944666402770395,172.51260351012135
-66.187090644489089,172.51298032830348
-65.429514886207812,172.51335714648565
-64.671939127926521,172.51373396466775
-63.853757842316021,172.51414292830455
-63.020425174873196,172.51455992830483
-62.187092507430485,172.51497692830529
-61.353759839987731,172.51539392830571
-60.520427172544942,172.515810928306
-59.68709450510223,172.51622792830639
-58.914367364988664,172.51661472224632
-58.156791606707316,172.51699396467075
-57.399215848426024,172.51737320709526
-56.641640090144698,172.51775244951997
-55.884064331863442,172.5181316919444
-55.126488573582002,172.51851093436912
-54.520427966957072,172.35409566148869
-54.520427966957072,171.5305023273886
-54.520427966957072,170.70690899328818
-54.520427966957072,169.89651917435174
-54.520427966957072,169.13894341607056
-54.520427966957072,168.38136765778913
-54.520427966957072,167.62379189950772
-54.520427966957072,166.86621614122635
-54.520427966957072,166.10864038294525
-54.520427966957072,165.35106462466379
-54.065084216532966,165.04878957135196
-53.246637365770709,165.0501481213532
-52.413305364994642,165.05153162135434
-51.579973364218517,165.05291512135565
-50.746641363442315,165.05429862135699
-49.913309362666325,165.05568212135813
-49.079977361890222,165.05706562135944
-48.246645361114133,165.05844912136078
-47.413313360338066,165.05983262136215
-46.579981359561941,165.06121612136351
-45.746649358785817,165.06259962136491
-44.913317358009749,165.06398312136605
-44.079985357233646,165.06536662136742
-43.374670956576757,165.40901182168759
-42.701360955949724,165.83822244708711
-42.028050955322634,166.26743307248694
-41.354740954695579,166.69664369788654
-40.681430954068503,167.12585432328626
-39.978729953414017,167.57379899037025
-39.276028952759646,168.02174365745415
-38.57332795210516,168.46968832453774
-37.870626951450696,168.91763299162173
-37.167925950796302,169.36557765870563
-36.465224950141874,169.81352232578934
-35.826406010152958,170.2207470231383
-35.187587070164035,170.62797172048727
-34.548768130175119,171.03519641783623
-33.909949190186239,171.4424211151852
-33.27113025019738,171.84964581253416
-32.632311310208536,172.25687050988313
-31.923146834800605,172.5012086616257
-31.108464056264097,172.50121699495909
-30.313798611079505,172.50122549495904
-29.532478054796268,172.50123410607034
-28.751157498513066,172.5012427171815
-27.969836942229847,172.5012513282926
-27.204193790001607,172.50125272223207
-26.446618031720334,172.50125969192914
-25.689042273439025,172.50126666162598
-24.931466515157695,172.50127363132285
-24.173890756876403,172.50128060101997
-23.416314998595073,172.50128757071681
-22.658739240313821,172.50129454041368
-21.901163482032416,172.50130141920158
-21.143587723751182,172.50130823738357
-20.386011965469891,172.50131505556536
-19.628436207188543,172.50132187374709
-18.87086044890729,172.50132869192893
-18.113284690625942,172.50133551011064
-17.355708932344669,172.50134232829248
-16.598133174063339,172.50134929798961
-15.84055741578201,172.50135626768648
-15.082981657500738,172.50136323738366
-14.325405899219428,172.5013702070805
-13.567830140938099,172.50137717677737
-12.810254382656694,172.50138414647449
-12.05267862437546,172.50139111617139
-11.295102866094112,172.50139808586849
-10.537527107812821,172.50140505556544
-9.7799513495315864,172.50141202526251
-9.0223755912502952,172.50141899495938
-8.2647998329689472,172.50142596465651
-7.507224074687656,172.50143293435346
-6.7496483164063461,172.50143990405039
-5.9920725581250736,172.50144687374745
-5.2344967998437824,172.5014538434443
-4.476921041562453,172.50146081314116
-3.7193452832811431,172.50146778283806
-2.961769524999871,172.50147475253513
-2.3556755850414675,172.33839057814075
-2.3555089183746531,171.5229418273816
-2.3553422517078957,170.70749307662228
-2.3551849183743534,169.93834271984528
-2.3550299183742709,169.1807669615639
-2.3548749183740747,168.42319120328276
-2.3547199183739544,167.66561544500135
-2.3545649183737964,166.90803968671992
-2.3544099183735816,166.15046392843854
-2.3542595638156931,165.41546712881311
-2.3541277910264284,164.77078616381118
-2.3539960182371638,164.12610519880934
-1.6933774650483617,163.99661662287971
-0.86763721675981742,163.99592614421817
-0.041896968471273027,163.99523566555663
0.78384327981729029,163.99454518689529
1.6095835281057589,163.9938547082337
2.4353237763943789,163.99316422957216
3.2610640246829803,163.99247375091065
4.0868042729715626,163.99178327224911
4.9125445212601448,163.99109279358774
5.7382847695487271,163.99040231492617
6.5640250178371389,163.98971183626463
7.389765266125778,163.98902135760298
8.0503574647566438,163.82514045198397
8.0503574647566438,163.00849783853494
8.0503574647566438,162.19185522508602
8.0503574647566438,161.37521261163712
8.0503574647566438,160.55856999818809
8.8307401395278848,160.55921230901706
9.6111228142991276,160.55985461984594
10.391505489070369,160.56049693067473
11.162765215427385,160.5612596505058
11.920340519163176,160.56220298384005
12.677915822899081,160.5631463171743
13.435491126634949,160.56408965050852
14.193066430370777,160.56503298384266
14.950641734106625,160.56597631717693
15.70821703784255,160.5669196505111
16.526398232543858,160.56794045051217
17.359730899986573,160.5689806171797
18.193063567429288,160.57002078384747
19.02639623487217,160.57106095051503
19.859728902314885,160.57210111718257
20.693061569757599,160.57314128385028
20.859745769912877,161.2156169844487
20.85976785324624,162.0184515685296
20.859789345670492,162.80318262229073
20.85980995173124,163.56075838057214
20.859830557791781,164.31833413885329
20.85985116385255,165.07590989713461
20.859871769913145,165.83348565541601
20.859892375973857,166.59106141369739
20.859912982034398,167.34863717197854
20.85993370930716,168.10621293025994
20.859954466882982,168.86378868854126
20.859975224458651,169.62136444682241
20.859995982034395,170.37894020510382
20.860016739610217,171.13651596338514
20.860037497185886,171.89409172166643
21.020449970062561,172.50021999495814
21.822429304142815,172.50055832829173
22.62440863822307,172.50089666162555
23.426387972303321,172.50123499495911
24.228367306383575,172.50157332829281
25.030346640463829,172.50191166162662
25.823445259384318,172.50224611617227
26.581021017665591,172.50256505556661
27.338596775946922,172.50288399496091
28.096172534228305,172.50320293435504
28.853748292509636,172.50352187374949
29.611324050790909,172.5038408131436
30.368899809072143,172.5041597525379
31.17192991285026,172.50449642829574
32.00526291362646,172.50484492829614
32.838595914402426,172.50519342829639
33.671928915178512,172.50554192829657
34.505261915954634,172.50589042829685
35.338594916730642,172.50623892829719
36.126473572009957,172.50656978284292
36.884049330291283,172.50688887375233
37.641625088572518,172.5072079646618
38.399200846854001,172.50752705557125
39.156776605135271,172.5078461464806
39.914352363416562,172.50816523738999
40.671928121697874,172.50848432829935
41.429503879979315,172.50880326769371
42.187079638260535,172.50912220708778
42.944655396541918,172.50944114648189
43.702231154823245,172.50976008587622
44.459806913104579,172.51007902527033
45.217382671385963,172.51039796466466
45.974958429667232,172.51071696466485
46.732534187948453,172.51103605557424
47.490109946229836,172.51135514648377
48.247685704511106,172.51167423739312
49.005261462792326,172.51199332830251
49.762837221073653,172.51231241921187
50.520412979354866,172.51263151012131
51.030365119350961,172.50733149720497
51.647039097540336,172.51635925251006
51.776161592465087,172.52131954570973
-28,167.00000000000011
-28.833333333333332,167.00000000000011
-29.666666666666572,167.00000000000011
-29.999999999999943,167.41666666666674
-29.999999999999943,168.11111111111134
-29.999999999999943,168.80555555555574
-29.999999999999943,169.50000000000011
-29.166666666666629,169.50000000000011
-28.333333333333332,169.50000000000011
-28,169.08333333333348
-28,168.38888888888911
-28,167.69444444444466
-28,167.138888888889
-31.000999999999976,158.5
-31.833499999999997,158.5
-32,159.16666666666663
-31.499999999999972,159.5
-31.000333333333231,159.16666666666663
-31.000833333333304,158.66666666666669

Output:

  Vertices: 504
  Loops: 3 [485, 13, 6]

  S2 polygon built: 3 loop(s)
  ✓ Input geometry is VALID

Step 1: Level 0 → Face 3
  Cell: 0x7000000000000000
  Polygon ∩ Cell... 3 loop(s) ✓
  Validating with `S2Polygon`... ✓

Step 2: Level 1
  Cell: 0x6c00000000000000
  Result ∩ Cell... 3 loop(s) ✓
  Validating with `S2Polygon`... ✓

Step 3: Level 2
  Cell: 0x6d00000000000000
  Result ∩ Cell... 3 loop(s) ✓
  Validating with `S2Polygon`... ✓

Step 4: Level 3
  Cell: 0x6c40000000000000
  Result ∩ Cell... 3 loop(s) ✓
  Validating with `S2Polygon`... WARNING: All log messages before absl::InitializeLog() is called are written to STDERR
E0000 00:00:1763005048.366099   58305 s2polygon.cc:228] One or more duplicate polygon edges detected
INVALID
    ✗ `S2Polygon::IsValid()` returned FALSE
    ✗ `S2Polygon::FindValidationError()` says:
      "One or more duplicate polygon edges detected"

Step 5: Level 4
  Cell: 0x6c30000000000000
  Result ∩ Cell... F0000 00:00:1763005048.367569   58305 s2boolean_operation.cc:503] Check failed: multiplicity == 0 || multiplicity == 1 
*** Check failure stack trace: ***
    @     0xffffa3de5f2c  absl::lts_20240116::log_internal::LogMessage::PrepareToDie()
    @     0xffffa3de5fa0  absl::lts_20240116::log_internal::LogMessage::SendToLog()
    @     0xffffa3de5a78  absl::lts_20240116::log_internal::LogMessage::Flush()
    @     0xffffa3de6224  absl::lts_20240116::log_internal::LogMessageFatal::~LogMessageFatal()
    @     0xffffa3bd4b90  (anonymous namespace)::GraphEdgeClipper::Run()
    @     0xffffa3bd5e34  (anonymous namespace)::EdgeClippingLayer::Build()
    @     0xffffa3c0bba0  S2Builder::BuildLayers()
    @     0xffffa3c080b8  S2Builder::Build()
    @     0xffffa3bdae78  S2BooleanOperation::Impl::DoBuild()
    @     0xffffa3bdaf2c  S2BooleanOperation::Impl::Build()
    @     0xffffa3bdb844  S2BooleanOperation::Build()
    @     0xaaaae8efd008  main
    @     0xffffa31c7744  (unknown)
    @     0xffffa31c7818  __libc_start_main

[benguild]

The invalid polygons by the way are too large to ignore, not rounding errors or stray fragments that have near zero area or are out of bounds, etc. …

The only potential workaround I'm aware of at the moment (which is obviously a lot of extra overhead) is to do this after each union/intersection/difference operation:

• Convert S2LaxPolygonShape output to S2Polygon
• Validate using S2Polygon::IsValid() and return original S2LaxPolygonShape if validation passes
• Otherwise, repair invalid geometry using S2Polygon::InitToSimplified()
• Rebuild "repaired" S2LaxPolygonShape using S2Builder with "simplified" S2Polygon input and original snap tolerance

[jmr]

Can you make this minimal and self-contained (no input file) and so it's just

1. setup input (from array/vector/string)
2. perform operation
3. crash
   ?

It will be easier to debug if you minimize the geometry. Try removing vertices. In the other bug, I could reduce 19 vertices to 4.

[benguild]

I actually did try to reduce it a bunch already whenever I could (there were more vertices prior) but I hit a point where I wasn't seeing a dramatic reduction so I stopped. Since there are two different possible outputs from two inputs I had kept it as a separate input via a file for now, is that unusable? In #476 there's only one so I put it in the code itself as with #474.

[jmr]

Hundreds of vertices is certainly not ideal.

Try randomly deleting lines until it stops crashing, then back up one step. You can script this externally while you're still reading the input.

[benguild]

Let me take another look, hang on.

[benguild]

OK, I was able to run the same script as #476 and cut this down successfully, I think.

Example 1: "Check failed: abs(e.second) <= 1 (2 vs. 1)"

Polygon
LoopSizes: [3 3 0]
TotalVertices: 6
-8.428849718835068,154.8192240455246
-35.059823282166256,170.70941665995701
51.38879410769084,172.50643866611074
-28.0,169.5000000000001
-28.0,167.27777777777786
-28.0,167.138888888889

Example 2: "Check failed: multiplicity == 0 || multiplicity == 1"

Polygon
 LoopSizes: [3 3 3]
TotalVertices: 9
19.8597,160.572
20.6931,160.573
51.7762,172.521
-28,168.389
-28,167.694
-28,167.139
-31.5,159.5
-31.0003,159.167
-31.0008,158.667

These might not be the exact same triggers but I did verify the error message crashed upon and output seemed the same for each. If any adjustment is made to the code, the original input should probably be verified as well.

[benguild]

@jmr just wanted to do a quick sanity check here… (mostly for me)

1. are these operation APIs expected to be near or fully stable, or is that a goal or not expected due to geometric/algorithmic complexities, etc.?
2. are these specific reports helpful, or more of a burden given the amount of potential failures? or is it possible that these can be added to a test suite and the coverage remains at 100% after some investigation?

the reason I ask is because if I find a crash or problem, it takes me a while to prepare a way to reproduce it… if I'm able to consistently at all. if the expectation above is that union/intersection/difference has to have some failure tolerance in any application, I'd kind of like to know if we're not just dealing with edge cases here.

[jmr]

are these operation APIs expected to be near or fully stable?

What do you mean by stable? It should definitely produce the same results if you run it twice.

are these specific reports helpful?

Yes, as long as they're minimized.

is it possible that these can be added to a test suite

If a bug is found, test cases will be added. No bugs have been found yet, AFAIK.

the reason I ask is because if I find a crash or problem, it takes me a while to prepare a way to reproduce it

Such is the nature of debugging. You may be able to ask an LLM to reproduce/minimize.

if I'm able to consistently at all

I'm very confused by this. If you have an example of something not reproducible across runs, we definitely want to know.

[jmr]

Can you post the code for your minimal test cases with the inputs from #475 (comment)?

It should be just setup input, perform op, get crash as described in #475 (comment).

[benguild]

Can you post the code for your minimal test cases with the inputs from #475 (comment)?

@jmr Here's the program with simplified input for "Example 1" embedded… which was regenerated since I realized my reduction script from the previous post had flattened a hole, and that seemed questionable. I left the prior input above for verification/comparison.

The prior reduced "Example 2" is commented out for alternative use, but I realized that may have a "flipped loop" (potentially from the reduction script, needs tweak) but I don't have time at the moment to go back through and see if I can find the original valid geometry prior to that happening if the OP's polygon is also like that. I'll keep an eye out for that coming back in some other instance while also monitoring for a way to reproduce #476 again. (The updated code below also has the InitOriented fix also mentioned there.)

If there's any user error here, that would be a relief, but I'm happy to take a look at anything further in any case. Thanks for your help/patience.

#include <iostream>
#include <memory>
#include <vector>

#include "s2/s2lax_polygon_shape.h"
#include "s2/s2polygon.h"
#include "s2/s2loop.h"
#include "s2/s2builder.h"
#include "s2/s2builderutil_lax_polygon_layer.h"
#include "s2/s2builderutil_snap_functions.h"
#include "s2/s2boolean_operation.h"
#include "s2/s2cell_id.h"
#include "s2/s2cell.h"
#include "s2/s2error.h"
#include "s2/s2latlng.h"
#include "s2/mutable_s2shape_index.h"

constexpr int kSnapTolerance = 10;

constexpr uint64_t kCellPath[] = {
    0x7000000000000000ULL, // Level 0: Face 3
    0x6c00000000000000ULL, // Level 1
    0x6d00000000000000ULL, // Level 2
    0x6c40000000000000ULL, // Level 3
    0x6c30000000000000ULL, // Level 4
    0x6c24000000000000ULL  // Level 5
};

int main() {
    // Example 1: "Check failed: abs(e.second) <= 1 (2 vs. 1)"
    std::vector<int> loopSizes = {3, 3, 3};
    std::vector<std::pair<double, double>> coords = {
        {51.77616159246509, 172.52131954570973},
        {-75.00039697091302, 164.41907781020427},
        {51.85101998719074, 172.36846329397179},
        {-28.0, 167.0000000000001},
        {-29.999999999999943, 169.5000000000001},
        {-28.0, 167.138888888889},
        {-31.000999999999976, 158.5},
        {-31.49999999999997, 159.5},
        {-31.000833333333304, 158.66666666666669},
    };

    // Example 2: "Check failed: multiplicity == 0 || multiplicity == 1" (may have orientation issues)
    // std::vector<int> loopSizes = {3, 3, 3};
    // std::vector<std::pair<double, double>> coords = {
    //     {19.8597, 160.572},
    //     {20.6931, 160.573},
    //     {51.7762, 172.521},
    //     {-28, 168.389},
    //     {-28, 167.694},
    //     {-28, 167.139},
    //     {-31.5, 159.5},
    //     {-31.0003, 159.167},
    //     {-31.0008, 158.667},
    // };

    std::cout << "  Vertices: " << coords.size() << "\n";
    std::cout << "  Loops: " << loopSizes.size() << " [";
    for (size_t i = 0; i < loopSizes.size(); i++) {
        if (i > 0) std::cout << ", ";
        std::cout << loopSizes[i];
    }
    std::cout << "]\n\n";

    std::vector<S2Point> points;
    for (const auto& coord : coords) {
        points.push_back(
            S2LatLng::FromDegrees(coord.first, coord.second).ToPoint()
        );
    }

    auto result = std::make_unique<S2LaxPolygonShape>();

    S2Builder::Options builderOpts{
        s2builderutil::IntLatLngSnapFunction(kSnapTolerance)
    };
    S2Builder builder{builderOpts};
    builder.StartLayer(
        std::make_unique<s2builderutil::LaxPolygonLayer>(result.get())
    );

    size_t pointIndex = 0;
    for (int loopSize : loopSizes) {
        for (int i = 0; i < loopSize; i++) {
            builder.AddEdge(
                points[pointIndex + i],
                points[pointIndex + ((i + 1) % loopSize)]
            );
        }
        pointIndex += loopSize;
    }

    S2Error error;
    if (!builder.Build(&error)) {
        std::cerr << "ERROR: Failed to build polygon: " << error << "\n";
        return 1;
    }

    std::cout << "  S2 polygon built: " << result->num_loops() << " loop(s)\n";
    std::cout << "  ✓ Input geometry is VALID\n\n";

    for (int level = 0; level < 6; level++) {
        uint64_t cellId = kCellPath[level];

        std::cout << "Step " << (level + 1) << ": Level " << level;
        if (level == 0) std::cout << " → Face 3";
        std::cout << "\n";
        std::cout << "  Cell: 0x" << std::hex << cellId << std::dec << "\n";

        S2CellId s2CellId(cellId);
        S2Cell cell(s2CellId);

        auto cellShape = std::make_unique<S2LaxPolygonShape>();

        S2Builder::Options cellBuilderOpts{
            s2builderutil::IntLatLngSnapFunction(kSnapTolerance)
        };
        S2Builder cellBuilder{cellBuilderOpts};
        cellBuilder.StartLayer(
            std::make_unique<s2builderutil::LaxPolygonLayer>(cellShape.get())
        );

        for (int i = 0; i < 4; i++) {
            cellBuilder.AddEdge(
                cell.GetVertex(i),
                cell.GetVertex((i + 1) % 4)
            );
        }

        if (!cellBuilder.Build(&error)) {
            std::cerr << "ERROR: Failed to build cell: " << error << "\n";
            return 1;
        }

        std::cout << "  " << (level == 0 ? "Polygon" : "Result")
                  << " ∩ Cell... ";
        std::cout.flush();

        auto newResult = std::make_unique<S2LaxPolygonShape>();

        MutableS2ShapeIndex indexA;
        int shapeIdA = indexA.Add(std::move(result));

        MutableS2ShapeIndex indexB;
        int shapeIdB = indexB.Add(std::move(cellShape));

        s2builderutil::LaxPolygonLayer::Options layerOpts;
        layerOpts.set_degenerate_boundaries(
            s2builderutil::LaxPolygonLayer::Options::DegenerateBoundaries::DISCARD
        );

        S2BooleanOperation::Options opOpts;
        opOpts.set_snap_function(
            s2builderutil::IntLatLngSnapFunction(kSnapTolerance)
        );

        S2BooleanOperation op(
            S2BooleanOperation::OpType::INTERSECTION,
            std::make_unique<s2builderutil::LaxPolygonLayer>(
                newResult.get(),
                layerOpts
            ),
            opOpts
        );

        bool success = op.Build(indexA, indexB, &error);

        result.reset(
            static_cast<S2LaxPolygonShape*>(indexA.Release(shapeIdA).release())
        );
        cellShape.reset(
            static_cast<S2LaxPolygonShape*>(indexB.Release(shapeIdB).release())
        );

        if (!success) {
            std::cerr << "ERROR: " << error << "\n";
            return 1;
        }

        std::cout << newResult->num_loops() << " loop(s) ✓\n";

        if (newResult->num_loops() == 0) {
            std::cerr << "ERROR: No intersection at Level " << level << "\n";
            return 1;
        }

        std::cout << "  Validating with `S2Polygon`... ";
        std::cout.flush();

        std::vector<std::unique_ptr<S2Loop>> loops;

        for (int i = 0; i < newResult->num_loops(); i++) {
            int numVertices = newResult->num_loop_vertices(i);
            std::vector<S2Point> vertices;

            for (int j = 0; j < numVertices; j++) {
                vertices.push_back(newResult->loop_vertex(i, j));
            }

            auto loop = std::make_unique<S2Loop>(vertices);
            loops.push_back(std::move(loop));
        }

        auto polygon = std::make_unique<S2Polygon>();
        polygon->set_s2debug_override(S2Debug::DISABLE);
        polygon->InitOriented(std::move(loops));

        if (!polygon->IsValid()) {
            S2Error validationError;
            polygon->FindValidationError(&validationError);

            std::cout << "INVALID\n";
            std::cout << "    ✗ `S2Polygon::IsValid()` returned FALSE\n";
            std::cout << "    ✗ `S2Polygon::FindValidationError()` says:\n";
            std::cout << "      \"" << validationError << "\"\n";
        } else {
            std::cout << "✓\n";
        }

        std::cout << "\n";

        result = std::move(newResult);
    }

    std::cout << "SUCCESS: No crash (unexpected!)\n";

    return 0;
}

Here's the output for "Example 1" …

  Vertices: 9
  Loops: 3 [3, 3, 3]

  S2 polygon built: 3 loop(s)
  ✓ Input geometry is VALID

Step 1: Level 0 → Face 3
  Cell: 0x7000000000000000
  Polygon ∩ Cell... 4 loop(s) ✓
  Validating with `S2Polygon`... 
E0000 00:00:1763146449.977870   96135 s2polygon.cc:228] Inconsistent loop orientations detected
INVALID
    ✗ `S2Polygon::IsValid()` returned FALSE
    ✗ `S2Polygon::FindValidationError()` says:
      "Inconsistent loop orientations detected"

Step 2: Level 1
  Cell: 0x6c00000000000000
  Result ∩ Cell... 4 loop(s) ✓
  Validating with `S2Polygon`... E0000 00:00:1763146449.980003   96135 s2polygon.cc:228] Inconsistent loop orientations detected
INVALID
    ✗ `S2Polygon::IsValid()` returned FALSE
    ✗ `S2Polygon::FindValidationError()` says:
      "Inconsistent loop orientations detected"

Step 3: Level 2
  Cell: 0x6d00000000000000
  Result ∩ Cell... 4 loop(s) ✓
  Validating with `S2Polygon`... E0000 00:00:1763146449.982394   96135 s2polygon.cc:228] Inconsistent loop orientations detected
INVALID
    ✗ `S2Polygon::IsValid()` returned FALSE
    ✗ `S2Polygon::FindValidationError()` says:
      "Inconsistent loop orientations detected"

Step 4: Level 3
  Cell: 0x6c40000000000000
  Result ∩ Cell... 4 loop(s) ✓
  Validating with `S2Polygon`... E0000 00:00:1763146449.984675   96135 s2polygon.cc:228] Inconsistent loop orientations detected
INVALID
    ✗ `S2Polygon::IsValid()` returned FALSE
    ✗ `S2Polygon::FindValidationError()` says:
      "Inconsistent loop orientations detected"

Step 5: Level 4
  Cell: 0x6c30000000000000
  Result ∩ Cell... 2 loop(s) ✓
  Validating with `S2Polygon`... E0000 00:00:1763146449.986030   96135 s2polygon.cc:228] Inconsistent loop orientations detected
INVALID
    ✗ `S2Polygon::IsValid()` returned FALSE
    ✗ `S2Polygon::FindValidationError()` says:
      "Inconsistent loop orientations detected"

Step 6: Level 5
  Cell: 0x6c24000000000000
  Result ∩ Cell... F0000 00:00:1763146449.986373   96135 s2contains_vertex_query.cc:42] Check failed: abs(e.second) <= 1 (2 vs. 1) 
*** Check failure stack trace: ***
    @     0xffff8d7f5f2c  absl::lts_20240116::log_internal::LogMessage::PrepareToDie()
    @     0xffff8d7f5fa0  absl::lts_20240116::log_internal::LogMessage::SendToLog()
    @     0xffff8d7f5a78  absl::lts_20240116::log_internal::LogMessage::Flush()
    @     0xffff8d7f6224  absl::lts_20240116::log_internal::LogMessageFatal::~LogMessageFatal()
    @     0xffff8d6c26b0  S2ContainsVertexQuery::ContainsSign()
    @     0xffff8d7ac4c4  s2shapeutil::GetReferencePointAtVertex()
    @     0xffff8d7ac68c  s2shapeutil::GetReferencePoint()
    @     0xffff8d71ca90  S2LaxPolygonShape::GetReferencePoint()
    @     0xffff8d7aad74  s2shapeutil::ContainsBruteForce()
    @     0xffff8d5c05e0  MutableS2ShapeIndex::AddShape()
    @     0xffff8d5bf2d0  MutableS2ShapeIndex::ApplyUpdatesInternal()
    @     0xffff8d5beff0  MutableS2ShapeIndex::ApplyUpdatesThreadSafe()
    @     0xffff8d5c53d0  MutableS2ShapeIndex::MaybeApplyUpdates()
    @     0xffff8d5c520c  MutableS2ShapeIndex::Iterator::Init()
    @     0xffff8d5c51cc  MutableS2ShapeIndex::Iterator::Iterator()
    @     0xffff8d5c7678  std::make_unique<>()
    @     0xffff8d5c5320  MutableS2ShapeIndex::NewIterator()
    @     0xffff8d5f22e4  S2ShapeIndex::Iterator::Init()
    @     0xffff8d5f222c  S2ShapeIndex::Iterator::Iterator()
    @     0xffff8d5fac58  S2ContainsPointQuery<>::S2ContainsPointQuery()
    @     0xffff8d5f7458  MakeS2ContainsPointQuery<>()
    @     0xffff8d5e9078  S2BooleanOperation::Impl::GetChainStarts()
    @     0xffff8d5e9c90  S2BooleanOperation::Impl::AddBoundaryPair()
    @     0xffff8d5e9ee4  S2BooleanOperation::Impl::BuildOpType()
    @     0xffff8d5eae34  S2BooleanOperation::Impl::DoBuild()
    @     0xffff8d5eaf2c  S2BooleanOperation::Impl::Build()
    @     0xffff8d5eb844  S2BooleanOperation::Build()
    @     0xaaaad741c6f4  main
    @     0xffff8cbd7744  (unknown)
    @     0xffff8cbd7818  __libc_start_main

[jmr]

This is too much code to look at. Which function's result do you think is wrong? If it's the op.Build() for step 6, then set up the index and call that one function. The functions in s2text_format.h can help you print / parse. There should not be loops or complicated logic. It should be very obvious what the inputs / outputs are.

[benguild]

This is too much code to look at.

OK, let's take a break here. In this case, the challenge was that I was seeing an issue where after subsequent intersections it would crash. I tried to reproduce this using the 0 through N cell loop but as you noted this code is complicated. It's also complicated for me to try to simplify, and I'm noticing a pattern that due to the complexity of the library and working with these data sets and making sample code there can be other issues that pop up in the process.

The code I posted is nearly identical to the OP aside from the correction you mentioned in #476. But there could be other issues.

I'll just close this, but if I can come up with simple test cases that fail I'll see if it makes sense to explore in the future.