flaky tests

[jmr]

Some tests are flaky due to use of randomness. Here are the failure counts for 1000 runs:

     10 TestCellContainsPointConsistentWithS2CellIDFromPoint
      1 TestCellDistanceToEdge
     24 TestCellUnionNormalizePseudoRandom
      2 TestChordAngleBetweenPoints
      3 TestConvexHullQueryPointsInsideHull
     12 TestEdgeClippingClipToPaddedFace
      2 TestPaddedCellShrinkToFit
     24 TestTestingFractal

[rsned]

Need to add a seed flag and plumb it through the tests.
If tests are still flaky after using a consistent seed throughout, will need to refactor the helpers that use the random generation to allow an optional rand.Source as needed.

[rsned]

If there are tests that are still flaky after using new seeded random in testing comes through, update the flagged flaky methods to create a specific random Source to pass into the calls to random things

e.g. r := rand.New(rand.NewSource(1))

[jmr]

e.g. r := rand.New(rand.NewSource(1))

This should always be considered a temporary workaround. Tests should pass with all possible seeds.

[jmr]

Now, out of 1k runs, I see:

      2 TestCellContainsPointConsistentWithS2CellIDFromPoint
      7 TestCellDistanceToEdge

=== RUN   TestCellDistanceToEdge
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:758: {4 29 2 11000670145955975532 {{0.9862056245871376 0.9862056295284304} {-0.38971637592477315 -0.38971637226702704}}}.DistanceToEdge((0.267375917282735797719795, 0.686078227799468698400176, 0.676614206322004418936444), (0.267375926952832576599661, 0.686078217696954650861585, 0.676614212744517828923563)) = 179.9999976, want 180.0000000
--- FAIL: TestCellDistanceToEdge (0.00s)
=== RUN   TestCellDistanceToEdge
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:758: {4 26 3 9556877047513654528 {{-0.06904137022373527 -0.06904134839468679} {-0.4024873254542941 -0.4024872959350345}}}.DistanceToEdge((0.372615487166876868663223, 0.925781986026771197551000, -0.063917236108254532611639), (0.372615480827304668132172, 0.925781988906149266860268, -0.063917231360653428695606)) = 179.9999976, want 180.0000000
--- FAIL: TestCellDistanceToEdge (0.00s)
=== RUN   TestCellDistanceToEdge
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:758: {3 29 0 8842001826768255220 {{-0.07966830116367281 -0.07966829839924419} {0.006045478339771722 0.006045480845718505}}}.DistanceToEdge((0.996823407456148169458743, 0.006026273905833879653005, -0.079415227572085633767074), (0.996823407695055063726386, 0.006026266183654568724115, -0.079415225159296345958104)) = 179.9999976, want 180.0000000
--- FAIL: TestCellDistanceToEdge (0.00s)
=== RUN   TestCellDistanceToEdge
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:758: {3 29 1 8921361455338558108 {{-0.23330310236446708 -0.23330309912643066} {0.3398573945985196 0.3398573981279007}}}.DistanceToEdge((0.924526646664121320995378, 0.314207216719537940630147, -0.215694934037303193141710), (0.924526646678424102177019, 0.314207218112570574319875, -0.215694931946737417094440)) = 179.9999976, want 180.0000000
--- FAIL: TestCellDistanceToEdge (0.00s)
=== RUN   TestCellDistanceToEdge
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:758: {4 27 1 10981155640602174656 {{0.9066021650982308 0.9066021842579453} {-0.15111907794184543 -0.15111906596575575}}}.DistanceToEdge((0.111262505947894135838183, 0.736257169376785869374658, 0.667492348504069132886229), (0.111262505938919648018626, 0.736257169402754541032152, 0.667492348476921182331978)) = 179.9999976, want 180.0000000
--- FAIL: TestCellDistanceToEdge (0.01s)
=== RUN   TestCellDistanceToEdge
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:758: {4 26 2 11434922374428377344 {{0.4987063433775232 0.49870637476753643} {-0.46248924825598936 -0.462489217556751}}}.DistanceToEdge((0.382417884354746773212241, 0.826868738584582430029002, 0.412364706148793724871382), (0.382417884491440707162013, 0.826868737862826774787095, 0.412364707469283109375624)) = 179.9999976, want 180.0000000
--- FAIL: TestCellDistanceToEdge (0.00s)
=== RUN   TestCellDistanceToEdge
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:758: {0 28 2 1183189571281627152 {{0.10346630437590645 0.10346631006182486} {0.06665937837939376 0.06665938382047898}}}.DistanceToEdge((-0.992510609445896863078929, -0.102691410122022236395267, -0.066160142264697643921245), (-0.992510609444993141536884, -0.102691410156553503130183, -0.066160142224656506848568)) = 179.9999976, want 180.0000000
--- FAIL: TestCellDistanceToEdge (0.00s)

=== RUN   TestCellContainsPointConsistentWithS2CellIDFromPoint
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:574: For p=(-0.370762717941454711390037, -0.350223940409457201727861, -0.860161728135318992549685), CellFromCellID(cellIDFromPoint(p)).ContainsPoint(p) was false
--- FAIL: TestCellContainsPointConsistentWithS2CellIDFromPoint (0.00s)
=== RUN   TestCellContainsPointConsistentWithS2CellIDFromPoint
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:574: For p=(0.808990606873618012251370, -0.390616995366782127074856, -0.439263657637281756951353), CellFromCellID(cellIDFromPoint(p)).ContainsPoint(p) was false
    third_party/golang/github.com/golang/geo/v/v0/s2/cell_test.go:574: For p=(-0.350835790694997651240072, 0.009349383896125742360317, -0.936390322989392509533957), CellFromCellID(cellIDFromPoint(p)).ContainsPoint(p) was false
--- FAIL: TestCellContainsPointConsistentWithS2CellIDFromPoint (0.00s)

[flwyd]

If I understand TestCellContainsPointConsistentWithS2CellIDFromPoint correctly, it's uncovering a bug, so the RNG occasionally produces points which correctly fail the assertion. My annotated thinking:

for iter := 0; iter < 1000; iter++ {
        cell := CellFromCellID(randomCellID())
        i1 := randomUniformInt(4) // i1 is a random conrer
        i2 := (i1 + 1) & 3 // i2 is the next corner, counterclockwise
        v1 := cell.Vertex(i1) // v1 is a random corner of the given cell
        v2 := samplePointFromCap( // pick a random point in a cap
          CapFromCenterAngle(cell.Vertex(i2), // centered at the second corner
             s1.Angle(epsilon))) // with a radius of 1e-15
        // if the corner is a right angle, there's a 25% chance that v2 is in the interior of the cell and a 75% chance it's outside
        // v2 is within 0.0 and 1e-15 of the true vertex, with likelihood increasing proportional to the square of the radius
        p := Interpolate(randomUniformFloat64(0, 1.0), v1, v2) // p is a random point between v1 and v2
        // p could be outside cell by at most 1e-15, but that's larger than dblEpsilon of approx. 2.2e-16
        if !CellFromCellID(
          cellIDFromPoint(p) // this could be adjacent to cell, since p can be on or over the edge
        ).ContainsPoint(p) { // cellIdFromPoint says this should always be true
                t.Errorf("For p=%v, CellFromCellID(cellIDFromPoint(p)).ContainsPoint(p) was false", p)
        }
}

Regardless of what p is, CellFromPoint(p).ContainsPoint(p) should be true. ContainsPoint expands by dblEpsilon to handle points that are very close to the edge, but v2 could be slightly more than dblEpsilon away from a cell vertex. cellIDFromPoint is supposed to return a cell that contains the point, since points on the edge are contained by both adjacent cells (and thus vertex points are contained by four cells). So perhaps cellIDFromPoint has a looser tolerance than dblEpsilon when identifying a potential cell match, but ContainsPoint then applies a tighter constraint.