S2Cell(S2CellId(p)).Contains(p) requires expansion of (1.125 + eps) * eps

@ericveach

S2Cell(S2CellId(p)).Contains(p) should always hold, and there is a test to verify this, but there are counterexamples, causing flaky tests.

s2geometry/src/s2/s2cell_test.cc

Lines 494 to 500 in ead4b7a

    
           TEST(S2Cell, DISABLED_ConsistentWithS2CellIdFromPointExample1) { 
        
             // Failures can be generated for `ConsistentWithS2CellIdFromPoint` by 
        
             // increasing the number of iterations to 1M.  This is one such example. 
        
             S2Point p(0.38203141040035632, 0.030196609707941954, 0.9236558700239289); 
        
             S2Cell cell{S2CellId(p)}; 
        
             EXPECT_TRUE(cell.Contains(p)) << " point: " << p << " cell: " << cell.id(); 
        
           }

Is the expansion amount just wrong here?

s2geometry/src/s2/s2cell.cc

Lines 299 to 306 in ead4b7a

    
           // Expand the (u,v) bound to ensure that 
        
           // 
        
           //   S2Cell(S2CellId(p)).Contains(p) 
        
           // 
        
           // is always true.  To do this, we need to account for the error when 
        
           // converting from (u,v) coordinates to (s,t) coordinates.  At least in the 
        
           // case of S2_QUADRATIC_PROJECTION, the total error is at most DBL_EPSILON. 
        
           return uv_.Expanded(DBL_EPSILON).Contains(uv);

We can empirically determine the amount that makes it pass (I think it was around 1.5 ε, maybe smaller), but it would be good to have the correct error analysis.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

S2Cell(S2CellId(p)).Contains(p) requires expansion of (1.125 + eps) * eps #463

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	TEST(S2Cell, DISABLED_ConsistentWithS2CellIdFromPointExample1) {
	// Failures can be generated for `ConsistentWithS2CellIdFromPoint` by
	// increasing the number of iterations to 1M. This is one such example.
	S2Point p(0.38203141040035632, 0.030196609707941954, 0.9236558700239289);
	S2Cell cell{S2CellId(p)};
	EXPECT_TRUE(cell.Contains(p)) << " point: " << p << " cell: " << cell.id();
	}

	// Expand the (u,v) bound to ensure that
	//
	// S2Cell(S2CellId(p)).Contains(p)
	//
	// is always true. To do this, we need to account for the error when
	// converting from (u,v) coordinates to (s,t) coordinates. At least in the
	// case of S2_QUADRATIC_PROJECTION, the total error is at most DBL_EPSILON.
	return uv_.Expanded(DBL_EPSILON).Contains(uv);

S2Cell(S2CellId(p)).Contains(p) requires expansion of (1.125 + eps) * eps #463

Description

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions