No rings error on intersection error

[angaither]

I think we have a faulty dcel ring extraction.

Given two valid geometries, an intersection should return. Here is a test that should pass in both cases against the latest tag v0.45.1 however the first example fails due to "no rings to extract" When the geometry is simplified to 6 floating decimal points (second test case) an intersection is returned.

I believe it is related to the issue mentioned in this commit

I added the following test to geom/alg_set_op_test.go

func TestIntersection(t *testing.T) {
    for i, tc := range []struct {
        inputA, inputB, want string
    }{
        {
            // failing case with no rings to extract (should not fail).
            "POLYGON ((-57.84764391579377 -14.00436771429812, -57.98105430423379 -13.978568346975345, -57.97219 -13.895754, -57.815573 -13.870471, -57.78975494169227 -13.97408746357712, -57.79567678742665 -14.003207561112367, -57.84764391579377 -14.00436771429812))",
            "POLYGON ((-57.97219 -13.895754, -57.815573 -13.870471, -57.782572 -14.002915, -57.984142 -14.007415, -57.97219 -13.895754))",
            "POLYGON((-57.97219 -13.895754,-57.98105430423379 -13.978568346975345,-57.84764391579377 -14.00436771429812,-57.82788805023705 -14.003926669524565,-57.79567678742665 -14.003207561112367,-57.78975494169227 -13.97408746357712,-57.815573 -13.870471,-57.97219 -13.895754))",
        },
        {
            // simplified, same coords to 6 decimal points.
            "POLYGON ((-57.847643 -14.004367, -57.981054 -13.978568, -57.97219 -13.895754, -57.815573 -13.870471, -57.789754 -13.974087, -57.795676 -14.003207, -57.847643 -14.004367))",
            "POLYGON ((-57.97219 -13.895754, -57.815573 -13.870471, -57.782572 -14.002915, -57.984142 -14.007415, -57.97219 -13.895754))",
            "POLYGON((-57.97219 -13.895754,-57.981054 -13.978568,-57.847643 -14.004367,-57.795676 -14.003207,-57.78975447509755 -13.974089336177082,-57.815573 -13.870471,-57.97219 -13.895754))",
        },
    } {
        t.Run(strconv.Itoa(i), func(t *testing.T) {
            aoi, err := geom.UnmarshalWKT(tc.inputA)
            expectNoErr(t, err)
            mask, err := geom.UnmarshalWKT(tc.inputB)
            expectNoErr(t, err)

            got, err := geom.Intersection(aoi, mask)
            expectNoErr(t, err)
            expectGeomEqWKT(t, got, tc.want)
        })
    }

this is failing on go version go1.20 darwin/amd64 but weirdly enough will pass on go version go1.20.5 darwin/arm64

[peterstace]

Thanks for the detailed bug report @angaither.

It's interesting that the bug occurs on amd64 but fails on arm64. I've run into something similar to that in the past where arm64 was using a fused-add-multiply but amd64 wasn't -- that might be the issue here as well.

There's nothing "weird" or degenerate etc. going on with the inputs, so this is a case that I definitely want to get working correctly.

I suspect it's got something to do with the DCEL noding step -- I'll see if I can work out what's going on.

[angaither]

If it helps, I've got a few more failing test case examples:

               {
            // failed w "no rings"
            "POLYGON ((-91.090505 33.966621, -91.094941 33.966624, -91.09491 33.96729, -91.094691 33.968384, -91.094602 33.968744, -91.094547 33.968945, -91.094484 33.969145, -91.093264 33.972456, -91.093108 33.97274, -91.092382 33.973979, -89.942235 35.721107, -89.941594 35.721928, -89.940438 35.723405, -89.720717 36, -89.711573 36, -89.645271 35.924821, -89.644942 35.924442, -89.644529 35.923925, -89.6429 35.921751, -89.642692 35.921465, -89.642576 35.921135, -89.642146 35.919717, -89.642026 35.91928, -89.641571 35.917498, -89.641166 35.91565, -89.63955 35.907509, -89.639384 35.906472, -89.639338 35.905496, -89.639356 35.904841, -89.639394 35.903992, -89.63944 35.90339, -89.639487 35.902831, -89.639559 35.902218, -89.640275 35.896772, -89.64057 35.894942, -89.640962 35.893237, -89.641113 35.892633, -89.641786 35.890644, -89.642306 35.889248, -89.642587 35.888566, -89.642808 35.888057, -89.643386 35.88681, -89.64378 35.885975, -90.060853 35.140433, -90.585556 34.404858, -90.888428 34.027973, -90.890265 34.026455, -90.890862 34.026091, -90.895918 34.023915, -90.896574 34.023654, -90.896965 34.023521, -91.090505 33.966621))",
            "POLYGON ((-90.19553150069916 34.95162878475482, -90.42127335893674 34.993424947208105, -90.30813100280166 35.16529356781885, -90.12850301040231 35.13253239680938, -90.16769780459812 34.99064851784101, -90.19553150069916 34.95162878475482))",
            "POLYGON((-90.19553 34.95163,-90.1677 34.99065,-90.1285 35.13253,-90.30813 35.16529,-90.42127 34.99342,-90.19553 34.95163))",
        },
        {
            // failed w "no rings"
            "POLYGON ((-91.090505 33.966621, -91.094941 33.966624, -91.09491 33.96729, -91.094691 33.968384, -91.094602 33.968744, -91.094547 33.968945, -91.094484 33.969145, -91.093264 33.972456, -91.093108 33.97274, -91.092382 33.973979, -89.942235 35.721107, -89.941594 35.721928, -89.940438 35.723405, -89.720717 36, -89.711573 36, -89.645271 35.924821, -89.644942 35.924442, -89.644529 35.923925, -89.6429 35.921751, -89.642692 35.921465, -89.642576 35.921135, -89.642146 35.919717, -89.642026 35.91928, -89.641571 35.917498, -89.641166 35.91565, -89.63955 35.907509, -89.639384 35.906472, -89.639338 35.905496, -89.639356 35.904841, -89.639394 35.903992, -89.63944 35.90339, -89.639487 35.902831, -89.639559 35.902218, -89.640275 35.896772, -89.64057 35.894942, -89.640962 35.893237, -89.641113 35.892633, -89.641786 35.890644, -89.642306 35.889248, -89.642587 35.888566, -89.642808 35.888057, -89.643386 35.88681, -89.64378 35.885975, -90.060853 35.140433, -90.585556 34.404858, -90.888428 34.027973, -90.890265 34.026455, -90.890862 34.026091, -90.895918 34.023915, -90.896574 34.023654, -90.896965 34.023521, -91.090505 33.966621))",
            "POLYGON ((-90.29716937546225 35.18194480113967, -90.29596586203434 35.18172958540237, -90.34543219833212 34.998800268076835, -90.41002551098103 35.01051096325925, -90.29716937546225 35.18194480113967))",
            "POLYGON((-90.41002976544465 35.0105099574823,-90.40917743952937 35.01035545691778,-90.34543 34.9988,-90.29597 35.18173,-90.29717 35.18194,-90.40591861762248 35.0167550317294,-90.41002976544465 35.0105099574823))",
        },
        {
            // failed w "no rings"
            "POLYGON ((-149.845771 -17.472558, -149.888137 -17.477017, -149.929731 -17.480468, -149.934682 -17.50814, -149.920475 -17.541336, -149.895694 -17.571267, -149.861608 -17.600395, -149.832332 -17.611409, -149.791981 -17.611947, -149.774766 -17.577051, -149.753707 -17.535289, -149.744632 -17.494022, -149.765688 -17.465994, -149.805445 -17.46709, -149.845771 -17.472558))",
            "POLYGON ((-149.8839047803303 -17.58134141150439, -149.86106842049824 -17.474168045744268, -149.85203718167833 -17.473217512441664, -149.74468306149925 -17.494254193376246, -149.753707 -17.535289, -149.774766 -17.577051, -149.791981 -17.611947, -149.832332 -17.611409, -149.861608 -17.600395, -149.8839047803303 -17.58134141150439))",
            "POLYGON((-149.883905 -17.581341,-149.861608 -17.600395,-149.832332 -17.611409,-149.791981 -17.611947,-149.774766 -17.577051,-149.753707 -17.535289,-149.74468301819016 -17.494253996435646,-149.84639024198438 -17.474324481375792,-149.852037 -17.473218,-149.8610415727389 -17.47416522003122,-149.86106800032414 -17.474168001521154,-149.883905 -17.581341))",
        },

[peterstace]

Thanks! Those will be useful as additional regression tests once I've got the bug sorted out.

[peterstace]

A fix for this has been released in v0.46.0.