apache / apache/sedona-db

Need a more robust polygon-polygon related function in the GPU-based spatial join

Open
#415 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
503
Forks
61
Avg merge
2d 4h
Merged PRs (30d)
90

Description

This PR https://github.com/apache/sedona-db/pull/310 will implement GPU-based spatial join. Currently, the relate function of polygon-polygon is a port of [PGStrom](https://heterodb.github.io/pg-strom/), which is not robust and may produce inconsistent results compared to GEOS. These are failed tests. In addition, the polygon-polygon relate functions are not performant because they do not use something like prepared geometry to index line segments of every single polygon.

```c++
// FIXME: wkt1 is a closed polyline, which has no boundary according to JTS's
// Mod2BoundaryNodeRule We have to implement a similar rule in gpuspatial to handle this
// case correctly
TEST(RelateTest, LinesClosedEmpty) {
MultiLineString m_ls1;
LineString ls2;
std::string wkt1 = "MULTILINESTRING ((0 0, 0 1), (0 1, 1 1, 1 0, 0 0))";
std::string wkt2 = "LINESTRING EMPTY";
Context ctx1, ctx2;

ParseWKTMultiLineString(ctx1, wkt1.c_str(), m_ls1);
ParseWKTLineString(ctx2, wkt2.c_str(), ls2);
TestRelate(wkt1.c_str(), wkt2.c_str(), m_ls1, ls2);
}
```

```c++
/**
* Case from https://github.com/locationtech/jts/issues/270
* Strictly, the lines cross, since their interiors intersect
* according to the Orientation predicate.
* However, the computation of the intersection point is
* non-robust, and reports it as being equal to the endpoint
* POINT (-10 0.0000000000000012)
* For consistency the relate algorithm uses the intersection node topology.
*/
TEST(RelateTest, LineStringLineString10) {
LineString ls1;
LineString ls2;
std::string wkt1 = "LINESTRING (0 0, -10 0.0000000000000012)";
std::string wkt2 = "LINESTRING (-9.999143275740073 -0.1308959557133398, -10 0.0000000000001054)";
Context ctx1, ctx2;

ParseWKTLineString(ctx1, wkt1.c_str(), ls1);
ParseWKTLineString(ctx2, wkt2.c_str(), ls2);
TestRelate(wkt1.c_str(), wkt2.c_str(), ls1, ls2);
}
```

```c++
// FIXME: IM__EXTER_BOUND_1D should not be set
TEST(RelateTest, PolygonsNestedWithHole) {
Polygon poly1;
Polygon poly2;
std::string wkt1 =
"POLYGON ((40 60, 420 60, 420 320, 40 320, 40 60), (200 140, 160 220, 260 200, 200 140))";
std::string wkt2 = "POLYGON ((80 100, 360 100, 360 280, 80 280, 80 100))";
Context ctx1, ctx2;

ParseWKTPolygon(ctx1, wkt1.c_str(), poly1);
ParseWKTPolygon(ctx2, wkt2.c_str(), poly2);
TestRelate(wkt1.c_str(), wkt2.c_str(), poly1, poly2);
}
```

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the GPU-based spatial join work in PR #310 and the existing polygon-polygon relate implementation, then reproduce the listed RelateTest cases, especially PolygonsNestedWithHole. Done means the relate results are consistent with GEOS for these cases and the polygon-polygon path addresses the stated line-segment indexing performance concern.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases, performance
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.