apache / apache/lucene

Spatial3d: Wrong intersection detected between small polygons

Open
#11,883 17 comments 0 reactions 1 assignee Claimed by @kwrightapache View on GitHub
type:bug
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

The following polygon corresponds to the uber h3 boundary cell "8cc373cb54069ff":
```
POLYGON((-64.2102198418716 -39.14233318389477,-64.21016450005413 -39.142267144439614,-64.21021077465937 -39.1421844504783,-64.21031239098929 -39.142167795785085,-64.2103677330169 -39.14223383513698,-64.21032145850448 -39.14231652928534,-64.2102198418716 -39.14233318389477))
```

And this polygon corresponds to the uber h3 boundary cell "8cc373cb54065ff":

```
POLYGON((-64.20991499254879 -39.14238314705201,-64.20985965132967 -39.14231710755475,-64.20990592624541 -39.142234413886875,-64.21000754228744 -39.142217759529174,-64.21006288371667 -39.14228379892317,-64.21001660889377 -39.14236649277811,-64.20991499254879 -39.14238314705201))"
```
The cells are close to each other but they are not neighbours:

image

Still if you construct them with spatial3d library, the library detects and intersection between them:

```
public void testH3CellsWrongIntersection() {
final List points1 = new ArrayList<>();
addToList(points1, PlanetModel.SPHERE, -64.2102198418716, -39.14233318389477);
addToList(points1, PlanetModel.SPHERE, -64.21016450005413, -39.142267144439614);
addToList(points1, PlanetModel.SPHERE, -64.21021077465937, -39.1421844504783);
addToList(points1, PlanetModel.SPHERE, -64.21031239098929, -39.142167795785085);
addToList(points1, PlanetModel.SPHERE, -64.2103677330169, -39.14223383513698);
addToList(points1, PlanetModel.SPHERE, -64.21032145850448, -39.14231652928534);
final List points2 = new ArrayList<>();
addToList(points2, PlanetModel.SPHERE, -64.20991499254879, -39.14238314705201);
addToList(points2, PlanetModel.SPHERE, -64.20985965132967, -39.14231710755475);
addToList(points2, PlanetModel.SPHERE, -64.20990592624541, -39.142234413886875);
addToList(points2, PlanetModel.SPHERE, -64.21000754228744, -39.142217759529174);
addToList(points2, PlanetModel.SPHERE, -64.21006288371667, -39.14228379892317);
addToList(points2, PlanetModel.SPHERE, -64.21001660889377, -39.14236649277811);

final GeoPolygon polygon1 = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points1);
final GeoPolygon polygon2 = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points2);
assertFalse(polygon1.intersects(polygon2));
}

private static void addToList(List points, PlanetModel planetModel, double lon, double lat) {
points.add(
new GeoPoint(
planetModel,
Geo3DUtil.fromDegrees(lat),
Geo3DUtil.fromDegrees(lon)));
}
```
A quick look make me think the issue is related with the current vector minimum resolution.

Taking into account that those cells are at H3 resolution 12 which means the [average area](https://h3geo.org/docs/core-library/restable/#average-area-in-m2) of those hexagons is 307.092 m2, I think we should be able to detect spatial relationships properly.


### Version and environment details

_No response_

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.