Corners are not inside

[tspoke]

From this test, corner2 and corner3 are outside the area. If we change the longitude to 0.95 instead of 0.99 it works. The -0.05 is the same value as the increment variable in the build() function.

Looks like incrementing latitude and longitude in the TileAreaPolygonalBuilder.build() method from the center of an edge put the location outside the bbox.

testValidPolygonSquare

  //defining a large, axis-aligned area; locations within, even close to the edge,
  //should be contained
  const coords: Coordinate[] = [];
  coords.push(new Coordinate(0.0, 0.0));
  coords.push(new Coordinate(0.0, 1.0));
  coords.push(new Coordinate(1.0, 1.0));
  coords.push(new Coordinate(1.0, 0.0));

  const corner1 = OpenGeoTile.buildFromLatitudeAndLongitude(0.01, 0.01, TileSize.NEIGHBORHOOD);
  const corner2 = OpenGeoTile.buildFromLatitudeAndLongitude(0.01, 0.99, TileSize.NEIGHBORHOOD); // here 
  const corner3 = OpenGeoTile.buildFromLatitudeAndLongitude(0.99, 0.99, TileSize.NEIGHBORHOOD); // here
  const corner4 = OpenGeoTile.buildFromLatitudeAndLongitude(0.99, 0.01, TileSize.NEIGHBORHOOD);
  const center = OpenGeoTile.buildFromLatitudeAndLongitude(0.5, 0.5, TileSize.NEIGHBORHOOD);

  const testTileArea = new TileAreaPolygonalBuilder()
    .setPrecision(TileSize.DISTRICT)
    .setCoordinatesList(coords)
    .build();

  expect(testTileArea).to.not.equal(null);
  
  expect(testTileArea.contains(corner1)).to.equal(true, "Contains area near corner 1");
  expect(testTileArea.contains(corner2)).to.equal(true, "Contains area near corner 2");
  expect(testTileArea.contains(corner3)).to.equal(true, "Contains area near corner 3");
  expect(testTileArea.contains(corner4)).to.equal(true, "Contains area near corner 4");
  expect(testTileArea.contains(center)).to.equal(true, "Contains center");

[bocops]

I think this might get fixed once I get to implement an [INCLUSIVE/EXCLUSIVE] edge strategy that makes sure that all tiles along the edge are really included.

Currently, the polygonal area we define is aligned exactly with a REGION-sized area (basically a 4-char OLC like XXXX0000+). The way OLC is defined, this includes the southern and western edges (0.0), but excludes the northern and eastern edges (1.0).

By just running the scanline algorithm, what I think happens here is that the final "column" of tiles checks out as outside of the polygon (due to rounding and/or the way OLC generally returns its center coordinate?).

If that is the problem, using slightly larger values in the polygon definition (like 1.05 instead of 1.0) might fix this test for the time being. I assume that this is less of a problem with arbitrarily defined polygons, but it definitely still needs to be resolved.

[tspoke]

I confirm the theory (if it was).
I tested a small polygon (square) like this one :

const coords = [];
coords.push(new Coordinate(47.475062, -0.552563));
coords.push(new Coordinate(47.469938, -0.552563));
coords.push(new Coordinate(47.469938, -0.547438));
coords.push(new Coordinate(47.475062, -0.547438));

Filtering resulting GeoTiles for 2 TileSize :

8CVXFCCW : 20 // EXTRA PINPOINT
8CVXFC : 2 // NEIGHBORHOOD
8CVXFF : 2 // NEIGHBORHOOD
8CVXFCFW : 20 // EXTRA PINPOINT

LENGTH NEIGHBORHOOD => 4
LENGTH PINPOINT => 40

We should have 4 NEIGHBORHOOD tiles (we are good here) but 160 extras PINPOINT not 40 (only the tiles the left side are included). What I don't understand is why I don't have 80 tiles (southern and western edges)...

[bocops]

I'm not at my PC right now, but will check in my implementation later. What I think causes the just 40 extra tiles is that we're doing scanlines, and then check individual tiles along those scanlines. The "missing" tiles are the first and last scanline, plus the final tiles of each scanline.

The latter is expected - but the former could be caused by some off-by-one error or at least slight imprecision when defining the first scanline.

[bocops]

@tspoke I can confirm that it is the same in my implementation: 4 bigger and 40 smaller tiles.

Changing the definition of the latitude for-loop like this:

//loop through latitude ("scanlines")
for (double latitude=minLatitude-(increment*0.1); latitude<maxLatitude; latitude+=increment) {
//...
}

leads to 81 smaller tiles instead (40 below, 40 to the left, 1 in the lower-left corner of the big tiles). We can apply similar "wiggle room" elsewhere to include the remaining 83 border tiles (right/top) as well. I'll be looking for the cleanest approach here over the weekend. :)