Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Simplify header-only point-in-polygon API #707

Closed
Tracked by #703
isVoid opened this issue Sep 29, 2022 · 1 comment · Fixed by #1192
Closed
Tracked by #703

Simplify header-only point-in-polygon API #707

isVoid opened this issue Sep 29, 2022 · 1 comment · Fixed by #1192
Assignees
Labels
improvement Improvement / enhancement to an existing function libcuspatial Relates to the cuSpatial C++ library tech debt Related to improving software quality

Comments

@isVoid
Copy link
Contributor

isVoid commented Sep 29, 2022

With introduction of multi*_range classes, point-in-polygon API can be simplified to just accepting a multipoint_range and a multipolygon_range.

Note that this refactor will "augment" the existing API to support multi* geometries.

For pairwise_point_in_polygon, a simple way is to add additional loops on top of the current kernel. This can allow the API to support geometry collections, while maintaining performance for non-multi geometry inputs.

For point_in_polygon, the all-pairs version, it can be simplified to a multipoint_ref to a multipolygon_ref. In multipolygon we require that the input to be order-aware. Alternatively it can be a multipoint_range and multipolygon_range, while limiting the geometry offset iterators to be only counting iterators.

@isVoid isVoid added improvement Improvement / enhancement to an existing function c++ labels Sep 29, 2022
@isVoid isVoid self-assigned this Sep 29, 2022
@isVoid
Copy link
Contributor Author

isVoid commented Sep 29, 2022

Depends on #703

@isVoid isVoid added this to cuSpatial Oct 3, 2022
@jarmak-nv jarmak-nv moved this to Todo in cuSpatial Nov 3, 2022
@harrism harrism added libcuspatial Relates to the cuSpatial C++ library and removed c++ labels Nov 16, 2022
@jarmak-nv jarmak-nv added the tech debt Related to improving software quality label Jun 5, 2023
@isVoid isVoid moved this from Todo to In Progress in cuSpatial Jun 9, 2023
@isVoid isVoid moved this from In Progress to Review in cuSpatial Jun 9, 2023
rapids-bot bot pushed a commit that referenced this issue Jun 22, 2023

Verified

This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
closes #707 

This PR simplifies `point_in_polygon` and `pairwise_point_in_polygon` API using `multipoint_range` and `multipolygon_range`. While these range methods supports a pair of multi geometry semantics, in this PR I'm not really targeting to create an API that works with multipoint-in-multipolygon semantics (such as "any point in any polygon", or "all points in any polygon", that sort of semantics). Therefore, this PR introduces `contains_only_single_geometry` method in `multipoint_range` and `multipolygon_range` that provides compile-time check for API that only want to work single-type geometry ranges. There are caveats to this introduction, see *caveats* section below.

This refactor results in a net decrease in LOC, and the compatibility layer for `is_point_in_polygon` is removed. The API dries up to a point where there's no raw kernel anymore.

In addition, previous `pairwise_point_in_polygon` API stores the row wise result in an int32_t per pair. Since it's only storing booleans, this PR uses `uint8_t` instead. This saves memory and increases throughputs.

### Caveats
`contains_only_single_geometry` method is an over-constrained method comparing to what it's really testing. A multipoint range can have a materialized column of integer sequences and still represent a single geometry column. The reason behind this refactor is that the original point-in-polygon test explicitly requires (by the number of arguments) that only single geometry columns accepted by the API. This means developers know at compile time that the geometry used in the API are constructed this way. `contains_only_single_geometry` is a `constexpr` method and verifies developers construction at compile time as well. This maintains the developer expectation while allowing `multi*_range` to be retrofit into the modern APIs.

Authors:
  - Michael Wang (https://github.com/isVoid)

Approvers:
  - Mark Harris (https://github.com/harrism)

URL: #1192
@github-project-automation github-project-automation bot moved this from Review to Done in cuSpatial Jun 22, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
improvement Improvement / enhancement to an existing function libcuspatial Relates to the cuSpatial C++ library tech debt Related to improving software quality
Projects
Status: Done
Development

Successfully merging a pull request may close this issue.

3 participants