I'd noted that following comment in the geoHashesForPolygon method.

• Note, the algorithm 'fills' the polygon from the inside with hashes. So, if a geohash partially falls outside the polygon, it is omitted. So, if you have a polygon with a lot of detail, this may result in large portions not
  being covered. To resolve this, manually choose a bigger geohash length. This results, in more but smaller
  geohashes around the edges.

not only 'fills', I want to 'intersect' the polygon with smaller hashes, I means that even if a point of geohash is included in the polygon, I will remain the geohash. How can I do it?

It seems that the last version (3.3.8) is build with Java 21, that breaks all applications using a previous version of it :

Caused by:
        java.lang.UnsupportedClassVersionError: com/jillesvangurp/geojson/FeatureCollection has been compiled by a more recent version of the Java Runtime (class file version 65.0), this version of the Java Runtime only recognizes class file versions up to 61.0

Can you rebuild it with the smallest version possible to be usable easily ?

Thanks a lot

Seems I never added tests for this.

The overlap method consider two polygons to overlap if any one of them contains the center of the other or if any one of them contains any vertex of the other. Unfortunately it is not always the case - see the example:

As you can see, their centers do not lie inside each other, and their vertexes also do not lie inside each other.

In my opinion, an algorithm would better assume that two polygons overlap if:
(polygonA crosses PolygonB) or (polygonA contains PolygonB) or (polygonB contains PolygonA),
where "crosses" means that any of the sides of the polygon A crosses any of the sides of the polygon B (linesCross method); and "contains" means that polygonA contains all points of polygonB.
Best regards,

In

You say you return [minlat, maxlat, minlon, maxlon] while in reality it is [maxlat, minlat, maxlon, minlon].

1st: Thanks for this great library...

We have a common use case to show clustered data because we cannot show thousands of POIs in a map window. The algorithms I found are using single points for that and are very slow on large data. Shouldn't it be possible to combine this clustering with the more performance oriented GeoHashes? In fact GeoHashes are already a grid clustering and aggregation. Do you know a lib or a algorithm?

Checking proximity to the poles is incorrect in method geoHashesForPolygon (see code snippet below). Since the coordinates (poligonPoints) are always expressed as lat-lon (and not lon-lat), the inequality condition should be applied to ds[0] and not ds[1].

public static Set<String> geoHashesForPolygon(int maxLength, double[]... polygonPoints) {
        for (double[] ds : polygonPoints) {
            // basically the algorithm can go into an endless loop. Best to avoid the poles.
            if(ds[1] < -89.5 || ds[1] > 89.5) {
                throw new IllegalArgumentException(
                        "please stay away from the north pole or the south pole; there are some known issues there. Besides, nothing there but snow and ice.");
            }
        }
        ...
}

Going to be painful to do but need to do this at some point.

Hi,
Can you please push the latest master to maven repository? There are some fixes in line cross utility which are not available in 2.11.

https://mvnrepository.com/artifact/com.jillesvangurp/geogeometry/2.11

• basic models are there already
• needs tests to verify we can parse any geojson

We currently rely on polygonContains to look for geohash bboxes that have all 4 of their corners fully inside.

We should experiment with a variant that checks whether any of the polygon segments crosses any of the polygon segments.

the GeoHashUtils.geoHashesForCircle is missing some big chunks of hashes because it seems to believe that is outside of the area. But my test show that it should be there.

   @Test
public void shouldCalculateHashesForCircleBrisbane2000() {
    double lat = -27.4669214;
    double lon = 153.02381279999997;
    double radius =  2000.0;
    int suitableHashLength = GeoHashUtils.suitableHashLength(radius, lat, lon);

    System.out.println(suitableHashLength);
    long start = System.currentTimeMillis();
    Set<String> hashesForCircle = GeoHashUtils.geoHashesForCircle(suitableHashLength, lat, lon, radius);
    long end = System.currentTimeMillis();
    System.out.println("time ms:" + (end-start));


    System.out.println("size: " + hashesForCircle.size());
    System.out.println(hashesForCircle);
    for (String hash : hashesForCircle) {
        double[] point = GeoHashUtils.decode(hash);
        double distance = GeoGeometry.distance(point, new double[]{lon,lat});
        assertThat(hash, distance, lessThan(radius));
        System.out.println( distance );            
    }

    String r7hg9y = "r7hg9y"; 
    double distance = GeoGeometry.distance( GeoHashUtils.decode(r7hg9y), new double[]{lon,lat});
    System.out.println( r7hg9y + ": "  +distance ); 
    assertThat(r7hg9y, distance, lessThan(radius));
    assertTrue( "this should be in circle", hashesForCircle.contains( r7hg9y ) );
 }

Hi,

I am calling com.jillesvangurp.geo.GeoGeometry.polygonContains(double latitude, double longitude, double[][][] polygonPoints)

params are:

latitude = 42.503615,
longitude = 1.641881
polygonPoints= [[[42.503320312499994, 1.7060546875], [42.4966796875, 1.678515625000017], [42.455957031249994, 1.58642578125], [42.441699218749996, 1.534082031250023], [42.434472656249994, 1.486230468750023], [42.437451171875, 1.448828125], [42.46132812499999, 1.428125], [42.497851562499996, 1.430273437500006], [42.530810546874996, 1.421972656250006], [42.548388671874996, 1.414843750000017], [42.5958984375, 1.428320312500006], [42.6216796875, 1.458886718750023], [42.642724609374994, 1.501367187500023], [42.635009765625, 1.568164062500017], [42.604443359375, 1.709863281250023], [42.575927734375, 1.739453125000011], [42.55673828125, 1.740234375], [42.525634765625, 1.713964843750006], [42.503320312499994, 1.7060546875]]]

the result is false shouldn't it be true?

on GeoHashUtils
function geoHashesForLinearRing

if (point.longitude < -89.5 || point.longitude > 89.5) (line 497)
should check latitude instead of longitude

Hi,
The following line segments do not actually intersect but the lineCross utility is returning a false positive.

{
        "type": "LineString",
        "coordinates": [
          [
            -71.1884310511,
            42.3219864254
          ],
          [
            -71.1884310511,
            42.321998793
          ]
        ]
      }

{
        "type": "LineString",
        "coordinates": [
          [
            -71.1884310515,
            42.3221529806
          ],
          [
            -71.1884310517,
            42.3222331303
          ]
        ]
      }

this is a test that illustrates the issue with latitudes for neighbors r7hg9z, r7hg9y

the south lat of 9z and north lat of 9y should be identical since r7hg9z is directly above r7hg9y.
However the north/south latitudes seems to around the wrong away.
the longitudes seem ok.

    @Test
public void shouldDecodeBoxwithSimilarEdge() {
    //north latitude, 0
    //south latitude, 1 
    //east longitude, 2 
    //west longitude, 3

    String geoHashz = "r7hg9z";
    String geoHashy = "r7hg9y";     
    double[] decodedy = decode_bbox(geoHashy);
    double[] decodedz = decode_bbox(geoHashz);

    //se 9z should equal ne 9y
    //south lat of 9z and north lat of 9y
    assertSimilar(decodedz[1], decodedy[0]);
    //north lat of 9z and south lat of 9y
    assertNotSimilar(decodedz[0], decodedy[1]); // should not be the same

    //east lng 
    assertSimilar(decodedz[2], decodedy[2]);
    //west lng
    assertSimilar(decodedz[3], decodedy[3]);


}

GeoJson specifies a different order of the doubles that go in a bounding box array than what is used in this library. This is obviously wrong and somewhat inconsistent.
The fix should be fairlyb straightforward with the port to Kotlin but will require updating a few of the algorithms that use bounding boxes as well.

• polygons need to be closed
• coordinates need to be within their boundaries

Hi,

Excellent job on this util - very helpful.

I think the order of return values in the decode_bbox array are incorrect. The code says:

 * @return double array representing the bounding box for the geohash of [north latitude, south latitude, east
 *         longitude, west longitude]

but really, it's [south,north,west,east] as seen in
return new double[] { latInterval[0], latInterval[1], lonInterval[0], lonInterval[1] };
where double[] latInterval = { -90.0, 90.0 };
, so latInterval[0] is really south (-90), I believe.

This manifest itself (though the code still works), in geoHashesForPolygon(). The comments say
// lets start at the top left:

    String rowHash = encode(bbox[0], bbox[2], hashLength);

bbox[0], bbox[2] REALLY is starting in the south west corner, rather than the NE corner (even though the comment says top left, which would be NW)

it appears that the east() method works correct, and the south() method really moves the bounding box north - so the result is correct.

If I'm reading it wrong -sorry! but in the debugger thats what it appeared to be, and was quite confusing :)

The current algorithm has a potential to blow up on edgecases.

Looks like lon/lat are getting confused somewhere

Review algorithm or remove it