You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2022/10/27 08:28:56 UTC
[GitHub] [lucene] iverase opened a new issue, #11883: Spatial3d: Wrong intersection detected between small polygons
iverase opened a new issue, #11883:
URL: https://github.com/apache/lucene/issues/11883
### 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:
<img width="177" alt="image" src="https://user-images.githubusercontent.com/29038686/198230964-f8fe118b-5b78-4780-a04d-b9558d07063c.png">
Still if you construct them with spatial3d library, the library detects and intersection between them:
```
public void testH3CellsWrongIntersection() {
final List<GeoPoint> 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<GeoPoint> 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<GeoPoint> 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.
<br class="Apple-interchange-newline">
### Version and environment details
_No response_
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327738427
On a whim I decided to verify that the point it finds for the intersection is actually within both shapes. But (guess what) it's not.
final GeoPoint intersectionPoint = new GeoPoint(0.3374386757253078,-0.6983427934019486,-0.6312309268629938);
if (polygon1.isWithin(intersectionPoint)) {
System.out.println("IntersectionPoint "+intersectionPoint+" is within polygon1");
}
if (polygon2.isWithin(intersectionPoint)) {
System.out.println("IntersectionPoint is within polygon2");
}
... prints nothing.
So it may be that the bounds planes it chooses are not the best / correct ones. There is logic in the construction of the GeoConvexPolygon that attempts to deal with linear lines of points and it's conceivable that that logic is failing us here.
I agree with idea that creating explicit bounds planes would likely solve this issue and could be done regardless of linearity of points. That makes it attractive indeed. We'd basically want to construct them so that we get a plane perpendicular to the edge plane that goes through the center of the planet and through the endpoint. Since precision is an issue using the correct construction technique would be important.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327889864
Committed a (working) fix to branch GITHUB-11883
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] DaddyWri commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
DaddyWri commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1331740074
If not - I may have time this weekend, we'll see. Perhaps we should also look at GeoConcavePolygon first though.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] iverase commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
iverase commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327681907
A possible fix would be to create perpendicular planes for the bounds instead of using the previous and next edges:
```
final SidedPlane boundPlane1 = new SidedPlane(notableEdgePoints[bound1Index][0], edge, notableEdgePoints[bound2Index][1]);
final SidedPlane boundPlane2 = new SidedPlane(notableEdgePoints[bound2Index][1], edge, notableEdgePoints[bound1Index][0]);
```
But it means we would need to create two more planes for each edge.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327742871
Specifically, I need to write this method:
/**
* Given a plane and one point that is on that plane, find a perpendicular plane that goes through
* both the origin and the point.
*
* @param plane is the original plane
* @param M is the point on that plane
* @return a plane that goes through M, the origin, and is perpendicular to the original plane
*/
public static Plane constructPerpendicularCenterPlaneOnePoint(final Plane plane, final Vector M) {
// MHL
}
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327428559
I've created a branch GITHUB-11883 to work on the restructuring needed to support the fix for this ticket.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327953754
Fix pulled up to main.
This ticket can be closed I think.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] iverase commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
iverase commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1330777875
Should we backport it to branch_9x?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] DaddyWri commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
DaddyWri commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1331472645
Feel free to. It should be a simple cherry-pick. I'm tied up with work escalations myself.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1336165599
Ok, GeoConcavePolygon has been updated on main, and all changes have been pulled to branch_9x as well.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327489468
Hmm. This logic already exists. It is why we have "notable points" in the intersection method - these are supposed to be the points we check (on the plane) when the intersecting plane is identical to the current one. I've verified that they are being correctly created. The logic looks correct as well, at least at first glance. Looking deeper.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327649597
The intersection code does not recognize the two planes as being identical. It finds a point of intersection, and that point does sit within all the bounds it has been given. This is then odd because, given the geometry, that shouldn't happen.
One thing I notice is that the sidedness of both near-identical planes is the same. That may be fine but only if the plane has the same sense relative to both polygons.
The next thing to check is whether the bounding planes are correct. Theoretically, that is where the intersecting point should be kicked out. If the bounding planes aren't doing that then they have been created incorrectly. Looking at the graphic, this seems like the most likely situation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327419070
The basic question that needs to be answered mathematically is: is there any point on that plane's intersection with the surface of the planet that is within all the other bounds? I believe this can be computed readily by the following process:
(1) For each bound, find the intersection(s) of the bound with the plane and with the world.
(2) Check if that point is within all other bounds. If not, use the intersection of the next bound and the plane, and verify that it still works with previous bounds. If those fail, move the point again and retry. If we begin to repeat, give up; there is no point that qualifies.
A better way of stating the same process is as follows:
(1) For the plane and for all the bounds, get a list of intersection points to look at.
(2) We ONLY need to consider points from this list. If we don't find any that work, there is no intersection.
The issue here is that the bounds given are Membership objects. Unfortunately we cannot assume they are planes. So we need a new primitive for Membership objects: void Membership.getIntersectionPoints(List<Vector>, Plane). This is easy to implement for sidedPlanes but that's not at all the only object that needs to have this support. A major chunk of work is therefore needed, and the contract for Membership will change.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327229254
I cannot seem to assign this to myself but I am planning on looking into this today. I agree that this is a bug.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327386634
The exact cause of the failure is this:
1> Checking convex edge [A=0.4548646850534976, B=-0.4661406124151235, C=0.7588221450039768, D=0.0, side=1.0] for intersection against plane [A=0.45486468505219513, B=-0.46614061241598176, C=0.7588221450042301, D=0.0, side=1.0]
1> intersects!
These two planes are nearly identical, which is what leads to this problem. The tests for whether a point is within the edge should be bounded on either side by cutoff planes (which are adjoining edges), so I need to look further into why they intersect within the bounds of both shapes. That should not be possible.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327396690
So when two planes intersect over a broad area (e.g. they are truly identical within the resolution we have), the logic for intersection cannot determine a precise point of intersection.
The solution is unclear. It's not correct to assume that the intersection exists, and it's not correct to deny the possibility that it exists.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] kwrightapache commented on issue #11883: Spatial3d: Wrong intersection detected between small polygons
Posted by GitBox <gi...@apache.org>.
kwrightapache commented on issue #11883:
URL: https://github.com/apache/lucene/issues/11883#issuecomment-1327800343
Ok, the math is worked out. I'll push appropriate modifications to the branch in pieces over the next day.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org