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

Investigate faster polygon operations #218

Open
Huite opened this issue Mar 10, 2024 · 1 comment
Open

Investigate faster polygon operations #218

Huite opened this issue Mar 10, 2024 · 1 comment

Comments

@Huite
Copy link
Collaborator

Huite commented Mar 10, 2024

The current burn_vector_geometry relies on calling earcut to break a polygon down into a triangular mesh, which is then checked for overlap. I don't necessarily see a better way for all_touched=True since it relies on computing overlaps. But in case of all_touched=False, it's just searching for centroids.

In this case, it's just a point in polygon check. The ad hoc benchmarking seemed to show that is was beating geopandas points-in-polygon, but not massively so (something like one order of magnitude).

I came across these two:

https://github.com/dengwirda/inpoly
https://github.com/KlausC/PolygonInbounds.jl

They do some prior work so it should be more efficient to search collections of points. It would be worthwhile to investigate, although it should maybe end up in numba-celltree instead.

@Huite
Copy link
Collaborator Author

Huite commented Jul 22, 2024

The 10x speed up compared to geopandas is not that impressive -- I guess because it's building an intermediate celltree for the earcut polygons.

However, that tree could be re-used in case multiple operations are required for a polygon dataset. This a pretty convincing argument to add an earcut staticmethod which returns a UgridDataArray with the earcut topology as the mesh, and returns the polygon indices as the data.

This also gives a clean composing way of implementing: #234

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant