/* * Copyright Elasticsearch B.V. and/or licensed to Elasticsearch B.V. under one * or more contributor license agreements. Licensed under the "Elastic License * 2.0", the "GNU Affero General Public License v3.0 only", and the "Server Side * Public License v 1"; you may not use this file except in compliance with, at * your election, the "Elastic License 2.0", the "GNU Affero General Public * License v3.0 only", or the "Server Side Public License, v 1". */ package org.elasticsearch.search.aggregations.bucket.geogrid; import org.apache.lucene.geo.GeoEncodingUtils; import org.elasticsearch.common.geo.GeoPoint; import org.elasticsearch.common.geo.GeoUtils; import org.elasticsearch.geometry.Rectangle; import org.elasticsearch.test.ESTestCase; import org.hamcrest.Matchers; import static org.elasticsearch.common.geo.GeoUtils.normalizeLat; import static org.elasticsearch.common.geo.GeoUtils.normalizeLon; import static org.elasticsearch.search.aggregations.bucket.geogrid.GeoTileUtils.MAX_ZOOM; import static org.elasticsearch.search.aggregations.bucket.geogrid.GeoTileUtils.checkPrecisionRange; import static org.elasticsearch.search.aggregations.bucket.geogrid.GeoTileUtils.hashToGeoPoint; import static org.elasticsearch.search.aggregations.bucket.geogrid.GeoTileUtils.keyToGeoPoint; import static org.elasticsearch.search.aggregations.bucket.geogrid.GeoTileUtils.longEncode; import static org.elasticsearch.search.aggregations.bucket.geogrid.GeoTileUtils.stringEncode; import static org.hamcrest.Matchers.anyOf; import static org.hamcrest.Matchers.closeTo; import static org.hamcrest.Matchers.containsString; import static org.hamcrest.Matchers.equalTo; public class GeoTileUtilsTests extends ESTestCase { private static final double GEOTILE_TOLERANCE = 1E-5D; /** * Precision validation should throw an error if its outside of the valid range. */ public void testCheckPrecisionRange() { for (int i = 0; i <= 29; i++) { assertEquals(i, checkPrecisionRange(i)); } IllegalArgumentException ex = expectThrows(IllegalArgumentException.class, () -> checkPrecisionRange(-1)); assertThat(ex.getMessage(), containsString("Invalid geotile_grid precision of -1. Must be between 0 and 29.")); ex = expectThrows(IllegalArgumentException.class, () -> checkPrecisionRange(30)); assertThat(ex.getMessage(), containsString("Invalid geotile_grid precision of 30. Must be between 0 and 29.")); } /** * A few hardcoded lat/lng/zoom hashing expectations */ public void testLongEncode() { assertEquals(0x0000000000000000L, longEncode(0, 0, 0)); assertEquals(0x3C00095540001CA5L, longEncode(30, 70, 15)); assertEquals(0x77FFFF4580000000L, longEncode(179.999, 89.999, 29)); assertEquals(0x740000BA7FFFFFFFL, longEncode(-179.999, -89.999, 29)); assertEquals(0x0800000040000001L, longEncode(1, 1, 2)); assertEquals(0x0C00000060000000L, longEncode(-20, normalizeLat(100), 3)); assertEquals(0x71127D27C8ACA67AL, longEncode(13, -15, 28)); assertEquals(0x4C0077776003A9ACL, longEncode(-12, 15, 19)); assertEquals(0x140000024000000EL, longEncode(normalizeLon(-328.231870), 16.064082, 5)); assertEquals(0x6436F96B60000000L, longEncode(normalizeLon(-590.769588), 89.549167, 25)); assertEquals(0x6411BD6BA0A98359L, longEncode(normalizeLon(999.787079), 51.830093, 25)); assertEquals(0x751BD6BBCA983596L, longEncode(normalizeLon(999.787079), 51.830093, 29)); assertEquals(0x77CF880A20000000L, longEncode(normalizeLon(-557.039740), normalizeLat(-632.103969), 29)); assertEquals(0x7624FA4FA0000000L, longEncode(13, 88, 29)); assertEquals(0x7624FA4FBFFFFFFFL, longEncode(13, -88, 29)); assertEquals(0x0400000020000000L, longEncode(13, 89, 1)); assertEquals(0x0400000020000001L, longEncode(13, -89, 1)); assertEquals(0x0400000020000000L, longEncode(13, normalizeLat(95), 1)); assertEquals(0x0400000020000001L, longEncode(13, normalizeLat(-95), 1)); expectThrows(IllegalArgumentException.class, () -> longEncode(0, 0, -1)); expectThrows(IllegalArgumentException.class, () -> longEncode(-1, 0, MAX_ZOOM + 1)); } public void testLongEncodeFromString() { assertEquals(0x0000000000000000L, longEncode(stringEncode(longEncode(0, 0, 0)))); assertEquals(0x3C00095540001CA5L, longEncode(stringEncode(longEncode(30, 70, 15)))); assertEquals(0x77FFFF4580000000L, longEncode(stringEncode(longEncode(179.999, 89.999, 29)))); assertEquals(0x740000BA7FFFFFFFL, longEncode(stringEncode(longEncode(-179.999, -89.999, 29)))); assertEquals(0x0800000040000001L, longEncode(stringEncode(longEncode(1, 1, 2)))); assertEquals(0x0C00000060000000L, longEncode(stringEncode(longEncode(-20, normalizeLat(100), 3)))); assertEquals(0x71127D27C8ACA67AL, longEncode(stringEncode(longEncode(13, -15, 28)))); assertEquals(0x4C0077776003A9ACL, longEncode(stringEncode(longEncode(-12, 15, 19)))); assertEquals(0x140000024000000EL, longEncode(stringEncode(longEncode(normalizeLon(-328.231870), 16.064082, 5)))); assertEquals(0x6436F96B60000000L, longEncode(stringEncode(longEncode(normalizeLon(-590.769588), 89.549167, 25)))); assertEquals(0x6411BD6BA0A98359L, longEncode(stringEncode(longEncode(normalizeLon(999.787079), 51.830093, 25)))); assertEquals(0x751BD6BBCA983596L, longEncode(stringEncode(longEncode(normalizeLon(999.787079), 51.830093, 29)))); assertEquals(0x77CF880A20000000L, longEncode(stringEncode(longEncode(normalizeLon(-557.039740), normalizeLat(-632.103969), 29)))); assertEquals(0x7624FA4FA0000000L, longEncode(stringEncode(longEncode(13, 88, 29)))); assertEquals(0x7624FA4FBFFFFFFFL, longEncode(stringEncode(longEncode(13, -88, 29)))); assertEquals(0x0400000020000000L, longEncode(stringEncode(longEncode(13, 89, 1)))); assertEquals(0x0400000020000001L, longEncode(stringEncode(longEncode(13, -89, 1)))); assertEquals(0x0400000020000000L, longEncode(stringEncode(longEncode(13, normalizeLat(95), 1)))); assertEquals(0x0400000020000001L, longEncode(stringEncode(longEncode(13, normalizeLat(-95), 1)))); expectThrows(IllegalArgumentException.class, () -> longEncode("12/asdf/1")); expectThrows(IllegalArgumentException.class, () -> longEncode("foo")); } private void assertGeoPointEquals(GeoPoint gp, final double longitude, final double latitude) { assertThat(gp.lon(), closeTo(longitude, GEOTILE_TOLERANCE)); assertThat(gp.lat(), closeTo(latitude, GEOTILE_TOLERANCE)); } public void testHashToGeoPoint() { assertGeoPointEquals(keyToGeoPoint("0/0/0"), 0.0, 0.0); assertGeoPointEquals(keyToGeoPoint("1/0/0"), -90.0, 66.51326044311186); assertGeoPointEquals(keyToGeoPoint("1/1/0"), 90.0, 66.51326044311186); assertGeoPointEquals(keyToGeoPoint("1/0/1"), -90.0, -66.51326044311186); assertGeoPointEquals(keyToGeoPoint("1/1/1"), 90.0, -66.51326044311186); assertGeoPointEquals(keyToGeoPoint("29/536870000/10"), 179.99938879162073, 85.05112817241982); assertGeoPointEquals(keyToGeoPoint("29/10/536870000"), -179.99999295920134, -85.0510760525731); // noinspection ConstantConditions expectThrows(NullPointerException.class, () -> keyToGeoPoint(null)); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("a")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("0")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("0/0")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("0/0/0/0")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("0/-1/-1")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("0/-1/0")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("0/0/-1")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("a/0/0")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("0/a/0")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("0/0/a")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint("-1/0/0")); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint((MAX_ZOOM + 1) + "/0/0")); for (int z = 0; z <= MAX_ZOOM; z++) { final int zoom = z; final int max_index = (int) Math.pow(2, zoom); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint(zoom + "/0/" + max_index)); expectThrows(IllegalArgumentException.class, () -> keyToGeoPoint(zoom + "/" + max_index + "/0")); } } /** * Make sure that hash produces the expected key, and that the key could be converted to hash via a GeoPoint */ private void assertStrCodec(long hash, String key, int zoom) { assertEquals(key, stringEncode(hash)); final GeoPoint gp = keyToGeoPoint(key); assertEquals(hash, longEncode(gp.lon(), gp.lat(), zoom)); } /** * A few hardcoded lat/lng/zoom hashing expectations */ public void testStringEncode() { assertStrCodec(0x0000000000000000L, "0/0/0", 0); assertStrCodec(0x3C00095540001CA5L, "15/19114/7333", 15); assertStrCodec(0x77FFFF4580000000L, "29/536869420/0", 29); assertStrCodec(0x740000BA7FFFFFFFL, "29/1491/536870911", 29); assertStrCodec(0x0800000040000001L, "2/2/1", 2); assertStrCodec(0x0C00000060000000L, "3/3/0", 3); assertStrCodec(0x71127D27C8ACA67AL, "28/143911230/145532538", 28); assertStrCodec(0x4C0077776003A9ACL, "19/244667/240044", 19); assertStrCodec(0x140000024000000EL, "5/18/14", 5); assertStrCodec(0x6436F96B60000000L, "25/28822363/0", 25); assertStrCodec(0x6411BD6BA0A98359L, "25/9300829/11109209", 25); assertStrCodec(0x751BD6BBCA983596L, "29/148813278/177747350", 29); assertStrCodec(0x77CF880A20000000L, "29/511459409/0", 29); assertStrCodec(0x7624FA4FA0000000L, "29/287822461/0", 29); assertStrCodec(0x7624FA4FBFFFFFFFL, "29/287822461/536870911", 29); assertStrCodec(0x0400000020000000L, "1/1/0", 1); assertStrCodec(0x0400000020000001L, "1/1/1", 1); expectThrows(IllegalArgumentException.class, () -> stringEncode(-1L)); expectThrows(IllegalArgumentException.class, () -> stringEncode(0x7800000000000000L)); // z=30 expectThrows(IllegalArgumentException.class, () -> stringEncode(0x0000000000000001L)); // z=0,x=0,y=1 expectThrows(IllegalArgumentException.class, () -> stringEncode(0x0000000020000000L)); // z=0,x=1,y=0 for (int zoom = 0; zoom < 5; zoom++) { int maxTile = 1 << zoom; for (int x = 0; x < maxTile; x++) { for (int y = 0; y < maxTile; y++) { String expectedTileIndex = zoom + "/" + x + "/" + y; GeoPoint point = keyToGeoPoint(expectedTileIndex); String actualTileIndex = stringEncode(longEncode(point.lon(), point.lat(), zoom)); assertEquals(expectedTileIndex, actualTileIndex); } } } } /** * Ensure that for all points at all supported precision levels that the long encoding of a geotile * is compatible with its String based counterpart */ public void testGeoTileAsLongRoutines() { for (double lat = -90; lat <= 90; lat++) { for (double lng = -180; lng <= 180; lng++) { for (int p = 0; p <= 29; p++) { long hash = longEncode(lng, lat, p); if (p > 0) { assertNotEquals(0, hash); } // GeoPoint would be in the center of the bucket, thus must produce the same hash GeoPoint point = hashToGeoPoint(hash); long hashAsLong2 = longEncode(point.lon(), point.lat(), p); assertEquals(hash, hashAsLong2); // Same point should be generated from the string key assertEquals(point, keyToGeoPoint(stringEncode(hash))); } } } } /** * Make sure the polar regions are handled properly. * Mercator projection does not show anything above 85 or below -85, * so ensure they are clipped correctly. */ public void testSingularityAtPoles() { double minLat = -GeoTileUtils.LATITUDE_MASK; double maxLat = GeoTileUtils.LATITUDE_MASK; double lon = randomIntBetween(-180, 180); double lat = randomBoolean() ? randomDoubleBetween(-90, minLat, true) : randomDoubleBetween(maxLat, 90, true); double clippedLat = Math.min(Math.max(lat, minLat), maxLat); int zoom = randomIntBetween(0, MAX_ZOOM); String tileIndex = stringEncode(longEncode(lon, lat, zoom)); String clippedTileIndex = stringEncode(longEncode(lon, clippedLat, zoom)); assertEquals(tileIndex, clippedTileIndex); } public void testPointToTile() { int zoom = randomIntBetween(0, MAX_ZOOM); int tiles = 1 << zoom; int xTile = randomIntBetween(0, zoom); int yTile = randomIntBetween(0, zoom); Rectangle rectangle = GeoTileUtils.toBoundingBox(xTile, yTile, zoom); // check corners assertThat(GeoTileUtils.getXTile(rectangle.getMinX(), tiles), equalTo(xTile)); assertThat(GeoTileUtils.getXTile(rectangle.getMaxX(), tiles), equalTo(Math.min(tiles - 1, xTile + 1))); assertThat(GeoTileUtils.getYTile(rectangle.getMaxY(), tiles), anyOf(equalTo(yTile - 1), equalTo(yTile))); assertThat(GeoTileUtils.getYTile(rectangle.getMinY(), tiles), anyOf(equalTo(yTile + 1), equalTo(yTile))); // check point inside double x = randomDoubleBetween(rectangle.getMinX(), rectangle.getMaxX(), false); double y = randomDoubleBetween(rectangle.getMinY() + GeoTileUtils.LUCENE_LAT_RES, rectangle.getMaxY(), false); assertThat(GeoTileUtils.getXTile(x, tiles), equalTo(xTile)); assertThat(GeoTileUtils.getYTile(y, tiles), equalTo(yTile)); } public void testEncodingLuceneLonConsistency() { final double qLon = GeoEncodingUtils.decodeLongitude(randomIntBetween(Integer.MIN_VALUE, Integer.MAX_VALUE)); for (int zoom = 0; zoom <= MAX_ZOOM; zoom++) { final int tiles = 1 << zoom; final int x = GeoTileUtils.getXTile(qLon, tiles); final Rectangle rectangle = GeoTileUtils.toBoundingBox(x, randomIntBetween(0, tiles - 1), zoom); // max longitude belongs to the next tile except the last one assertThat( GeoTileUtils.getXTile(GeoUtils.quantizeLon(rectangle.getMaxX()), tiles), Matchers.anyOf(equalTo(x + 1), equalTo(tiles - 1)) ); // next encoded value down belongs to the tile assertThat(GeoTileUtils.getXTile(GeoUtils.quantizeLonDown(rectangle.getMaxX()), tiles), equalTo(x)); // min longitude belongs to the tile assertThat(GeoTileUtils.getXTile(GeoUtils.quantizeLon(rectangle.getMinX()), tiles), equalTo(x)); if (x != 0) { // next encoded value down belongs to the previous tile assertThat(GeoTileUtils.getXTile(GeoUtils.quantizeLonDown(rectangle.getMinX()), tiles), equalTo(x - 1)); } } } public void testEncodingLuceneLatConsistency() { final double qLat = GeoEncodingUtils.decodeLatitude(randomIntBetween(Integer.MIN_VALUE, Integer.MAX_VALUE)); for (int zoom = 0; zoom <= MAX_ZOOM; zoom++) { final int tiles = 1 << zoom; final int y = GeoTileUtils.getYTile(qLat, tiles); final Rectangle rectangle = GeoTileUtils.toBoundingBox(randomIntBetween(0, tiles - 1), y, zoom); // max latitude belongs to the tile assertThat(GeoTileUtils.getYTile(GeoUtils.quantizeLat(rectangle.getMaxLat()), tiles), equalTo(y)); if (y != 0) { // next encoded value up belongs to the previous tile assertThat(GeoTileUtils.getYTile(GeoUtils.quantizeLatUp(rectangle.getMaxLat()), tiles), equalTo(y - 1)); } // min latitude belongs to the next tile except the last one assertThat( GeoTileUtils.getYTile(GeoUtils.quantizeLat(rectangle.getMinLat()), tiles), Matchers.anyOf(equalTo(y + 1), equalTo(tiles - 1)) ); // next encoded value up belongs to the tile assertThat(GeoTileUtils.getYTile(GeoUtils.quantizeLatUp(rectangle.getMinLat()), tiles), equalTo(y)); } } }