ENH: Add STRtree by caspervdw · Pull Request #58 · pygeos/pygeos

caspervdw · 2019-10-16T18:56:38Z

Closes #9

caspervdw · 2019-10-20T12:38:08Z

There was some design decision to make here. I chose to let the GEOS strtree store a pointer to the actual GeometryObject, so that it can DECREF it before deallocation.

The other options would be copying the GEOSGeometry object at the strtree init, and destroying it on deallocation. I think this copy would give unwanted overhead.

caspervdw · 2019-10-20T16:52:16Z

@jorisvandenbossche Do you know if there is any meaning to the order that is returned by tree.query? It might get inversed in my implementation.

pygeos/strtree.py

jorisvandenbossche · 2019-10-21T15:01:00Z

So the interface of rtree works like this:

In [1]: import pygeos   

In [2]: geometries = pygeos.points(np.random.rand(10, 2))       

In [3]: tree = pygeos.STRtree(geometries)         

In [4]: tree.query(pygeos.box(0, 0, 0.5, 0.5))  
Out[4]: 
array([<pygeos.Geometry POINT (0.0874 0.332)>,
       <pygeos.Geometry POINT (0.201 0.277)>,
       <pygeos.Geometry POINT (0.224 0.246)>,
       <pygeos.Geometry POINT (0.328 0.202)>,
       <pygeos.Geometry POINT (0.0253 0.195)>], dtype=object)

In [5]: import rtree  

In [6]: def bounds(geom): 
   ...:     coords = pygeos.get_coordinates(geom) 
   ...:     return coords[:, 0].min(), coords[:, 1].min(), coords[:, 0].max(), coords[:, 1].max() 
   ...:     

In [7]: stream = ((i, bounds(geom), str(i)) for i, geom in enumerate(geometries)) 

In [8]: index = rtree.index.Index(stream)   

In [9]: list(index.intersection(bounds(pygeos.box(0, 0, 0.5, 0.5))))   
Out[9]: [2, 1, 8, 3, 0]

By default, it gives you back the indices in the index (following creation order), but you can also optionally ask for full objects that hold extra information:

In [18]: res = list(index.intersection(bounds(pygeos.box(0, 0, 0.5, 0.5)), objects=True))  

In [19]: res[0]  
Out[19]: <rtree.index.Item at 0x7fea05b644f8>

In [20]: res[0].id  
Out[20]: 2

In [21]: res[0].object
Out[21]: '2'

In [23]: res[0].bbox 
Out[23]: 
[0.025262187255139068,
 0.194594674975633,
 0.025262187255139068,
 0.194594674975633]

including the "object" you stored attached to the specific geometry. In this example I used a string version of the index, but that could also be the original geometry itself (as in rtree you pass the bounds of the geometry).

To be clear: not saying we should copy the rtree interface (they have more features than we need, we can use the actual geometries, etc), but just as a reference point. In geopandas we mainly use the integer index. Eg in a spatial join, we need the indices to combine the attribute data.

Since there are probably good use cases of directly iterating over the geometries as well, it might make sense to return both? (eg with an option to toggle between both)

jorisvandenbossche · 2019-10-21T15:40:07Z

There was some design decision to make here. I chose to let the GEOS strtree store a pointer to the actual GeometryObject, so that it can DECREF it before deallocation.
The other options would be copying the GEOSGeometry object at the strtree init, and destroying it on deallocation. I think this copy would give unwanted overhead.

Yeah, I don't know how costly cloning the GEOSGeometry would be. The increasing/decreasing of the ref count in the current code seems relatively straightforward (I am trying to think of cases where this could give problems, but not directly thinking of something).

Since there are probably good use cases of directly iterating over the geometries as well, it might make sense to return both? (eg with an option to toggle between both)

Looking at the code, that might not be that easy, as the object that is returned is actually inserted in the tree. So either you need 2 implementations the tree creation (creating code duplication), or either you need to convert the integer to the geometry in the query method (giving additional indexing overhead in case you only want the geometry)

jorisvandenbossche

BTW, really cool start, thanks a lot for working on this

src/strtree.c

src/strtree.h

pygeos/test/test_strtree.py

caspervdw · 2019-10-28T09:26:20Z

@jorisvandenbossche I took another shot at this. Now query returns the indices, which can be used directly on tree.geometries to get the geometries.

To have the garbage collecting right, I still needed to insert the actual geometry objects into the tree. So I defined a struct STRtreeElem that contains the index (for returning) and the geometry object (for garbage collecting).

jorisvandenbossche · 2019-10-28T15:08:07Z

Did a quick experiment with combining the STRTree with a contains predicate (1 million points /1 polygon), and here I get a speed-up of 2-3x by using a spatial index (assuming we have a "warm" tree): https://nbviewer.jupyter.org/gist/jorisvandenbossche/66d1d81935cf6084d77ae6d1158f6fae
In practice, it will of course depend a lot on the specifics (how many elements are be returned by the query (in this experiment it is 1%), how costly is the actual operation, ...). But this modest speed-up at least indicates it's not totally useless ;) (and there will be cases where it can be much more interesting)

One thing I noticed is that the first usage of the tree is actually very slow (more than 100x slower). It might be that GEOS only constructs the actual tree on first use? (not sure how I would otherwise interpret that)

If that is correct, it seems that creation of the tree is actually quite slow .. (outside of our control of course, but can limit practical usage)

Anyway, the current interface certainly seems to be useful / practical!

jorisvandenbossche · 2019-10-28T15:09:51Z

To have the garbage collecting right, I still needed to insert the actual geometry objects into the tree. So I defined a struct STRtreeElem that contains the index (for returning) and the geometry object (for garbage collecting).

Why is that? I understand from the C API that the caller remains ownership on the GEOSGeometry objects? Do we need to keep the geometries alive as long as the STRTree is alive?

caspervdw · 2019-10-28T20:30:20Z

One thing I noticed is that the first usage of the tree is actually very slow (more than 100x slower). It might be that GEOS only constructs the actual tree on first use? (not sure how I would otherwise interpret that)

You're correct, it gets constructed on the first query. There's one sentence in the docs from which you can derive that However, once the tree has been built (explicitly or on the first call to query), items may not be added or removed. (see https://geos.osgeo.org/doxygen/classgeos_1_1index_1_1strtree_1_1STRtree.html)

Why is that? I understand from the C API that the caller remains ownership on the GEOSGeometry objects? Do we need to keep the geometries alive as long as the STRTree is alive?

We can't ensure that the caller doesn't dereference the geometry array with which the STRtree is constructed. If that happens, we we get a crash. You need to keep references to the geometries on the tree object to solve this issue.

jorisvandenbossche · 2019-10-29T08:05:19Z

Hmm, it's a pity that a trigger to construct the tree is not included in the C-API (as I think it can be useful to control as a user when the tree gets build. So eg that you can do it in advance, and the first query will already be fast).

We can't ensure that the caller doesn't dereference the geometry array with which the STRtree is constructed. If that happens, we we get a crash. You need to keep references to the geometries on the tree object to solve this issue.

It seems that you both keep a reference to the array, and then also store each geometry of that array inside the tree. Is the first (keeping a reference to the array) not enough?

But to understand: so the geometries need to be kept alive as long as the tree exists?
I don't fully understand why that is. From the code, when inserting an item in the tree, it seems it only uses the envelope of the geometry, and for the rest does not store or reference it (https://github.com/libgeos/geos/blob/master/capi/geos_ts_c.cpp#L5939)

caspervdw · 2019-11-05T19:16:37Z

It seems that you both keep a reference to the array, and then also store each geometry of that array inside the tree. Is the first (keeping a reference to the array) not enough?
But to understand: so the geometries need to be kept alive as long as the tree exists?
I don't fully understand why that is. From the code, when inserting an item in the tree, it seems it only uses the envelope of the geometry, and for the rest does not store or reference it (https://github.com/libgeos/geos/blob/master/capi/geos_ts_c.cpp#L5939)

I did some tests, and it appears that you need to keep a reference to the geometry object until the first query has been executed. In no case I got a hard crash, worst case there are geometries missing from the result of the query. See below:

geometries = pygeos.points(np.arange(10), np.arange(10))
tree = pygeos.STRtree(geometries)
geometries[1] = None
tree.query(pygeos.box(0, 0, 2, 2))
>>> [0, 2]  # unexpected

geometries = pygeos.points(np.arange(10), np.arange(10))
tree = pygeos.STRtree(geometries)
tree.query(pygeos.box(0, 0, 2, 2))
geometries[1] = None
tree.query(pygeos.box(0, 0, 2, 2))
>>> [0, 1, 2]  # correct

Keeping the objects in the tree.geometries array is not 100% foolproof, as it could be changed inplace. But I think it is good enough, as long as we document that changing the array after constructing the tree will lead to bogus results (as is done in scipy.KDTree)>

jorisvandenbossche · 2019-11-11T07:28:21Z

But I think it is good enough, as long as we document that changing the array after constructing the tree will lead to bogus results

That sounds good to me as well

jorisvandenbossche

Added some small doc / test comments, ready to be merged otherwise?

jorisvandenbossche · 2019-11-11T07:29:43Z

pygeos/strtree.py

+    algorithm.
+
+    For two-dimensional spatial data.
+    """


Maybe add a Parameters section here (for geometries and leafsize of the init)

And maybe also a small example?

>>> geoms = pygeos.points(np.arange(10), np.arange(10)) >>> tree = pygeos.STRtree(geoms) >>> tree.query(pygeos.box(2, 2, 4, 4)) array([2, 3, 4])

jorisvandenbossche · 2019-11-11T07:33:58Z

pygeos/strtree.py

+
+        Parameters
+        ----------
+        envelope : Geometry


You can pass whatever geometry, and the envelope is taken under the hood? (it's not that you first need to take the envelope yourself, but the current doc is not fully clear about it)

jorisvandenbossche · 2019-11-11T07:37:04Z

pygeos/test/test_strtree.py

+
+
+def test_init_with_none():
+    pygeos.STRtree(np.array([None]))


Maybe also do an actual query here? (since the tree is actually only created on first query, that seems relevant for the all-None case that also this query doesn't segfault or so)

jorisvandenbossche · 2019-11-20T20:49:43Z

So the problem is that it is failing with creating/querying the tree if it was empty (not geometries or all None), and for older GEOS?

It might be this is a bug in GEOS that was fixed?
We could maybe return try to detect this case and return an error in that case when creating the tree? (eg keep a counter while inserting into the tree, and raise an error if the counter is 0 ?)

caspervdw · 2019-11-20T20:52:47Z

I did the work already to keep track of the count, only forgot to put the logic in place at the query()

Will have a look next time around (might take a while- feel free to wrap this up)

jorisvandenbossche · 2019-11-20T20:57:58Z

Ah, yes, I see there is already a count. Yep, I can wrap this up.

But do we always want to raise an error for an empty tree? Or only for older GEOS versions? Always is the easiest, but it could be useful to have it also work for empty trees (with recent GEOS it does the right thing).

caspervdw · 2019-11-20T21:04:13Z

I think it is best to return an empty array (of the correct type) when the tree count is zero. Checking the count is very cheap so I would not make a version conditional there.

jorisvandenbossche · 2019-11-20T21:07:19Z

Ah, I missed that as well ;) You are already using the count to return this empty array. OK, yes, that's a much better solution!

jorisvandenbossche · 2019-11-20T21:34:41Z

It turned out you already had everything in place, but it was not used because the count was not initialized ..

jorisvandenbossche · 2019-11-20T21:53:33Z

This is all green now. So going to merge! (we can always further refine with follow-up PRs if needed)

…o version 2.0.0 0phoff (1): to_shapely and from_shapely updates (pygeos/pygeos#312) Adam J. Stewart (1): Add Python 3.10 wheels for additional platforms (#1373) Alan D. Snow (2): REF: Use pkg_resources instead of distutils (pygeos/pygeos#393) CI: Use pushd/popd when installing GEOS (pygeos/pygeos#405) Ariel Kadouri (4): Update segmentize tolerance parameter to max segment length (#1506) Alias geometry.base buffer styles to geometry.constructive enums (#1508) ENH: Remove Repeated Points (#1546) ENH: Add directed parameter to line merge (#1592) Bas Couwenberg (1): Fix versioneer configuration (#1654) Ben Beasley (1): MAINT: Remove descartes from requirements-dev.txt (#1591) Brendan Ward (42): ENH: include predicates in STRtree.query() (pygeos/pygeos#87) ENH: Added total_bounds() (pygeos/pygeos#107) ENH: query tree with multiple input geometries (pygeos/pygeos#108) Remove compiler warnings (pygeos/pygeos#115) ENH: only add non-empty geometries to STRtree (pygeos/pygeos#147) Add shapely-rfc link for latest proposal on integration (pygeos/pygeos#170) ENH: Add more predicates to STRtree query (pygeos/pygeos#157) Drop Python 3.5 from Travis-CI matrix (pygeos/pygeos#211) ENH: set up Cython support + get parts of multipart geometries (pygeos/pygeos#197) TST: Add Github Action for CI testing using conda (pygeos/pygeos#222) API change: return 0 for None values in geometry counting functions (pygeos/pygeos#220) Integrate previously prepared geometries into tree query ENH: Reduce compiler warnings from Cython extensions (pygeos/pygeos#228) Update changelog CLN: remove Cythonized and compiled extension files on python setup.py clean (pygeos/pygeos#239) CNL: Remove unnecessary filtering of counts from get_num_geometries (pygeos/pygeos#248) ENH: Adds reverse function for GEOS >= 3.7 (pygeos/pygeos#254) CLN: Migrate resizeable vector types and functions to dedicated files (pygeos/pygeos#247) ENH: Add STRtree benchmarks (pygeos/pygeos#270) ENH: STRtree: use addresses of tree geometries to calculate their index (pygeos/pygeos#265) ENH: Add get / set precision ufuncs (pygeos/pygeos#257) ENH: Add fixed precision set operations for GEOS >= 3.9 (pygeos/pygeos#276) Fix signed char portability issue (pygeos/pygeos#293) TST: Handle GEOS version strings with dev / beta qualifiers in the tests (pygeos/pygeos#301) ENH: Add densify ufunc (pygeos/pygeos#299) ENH: add STRtree nearest neighbor(s) function (pygeos/pygeos#272) DOC: clarify overlaps versus crosses predicates (pygeos/pygeos#288) ENH: Consolidate validation of enum values and raise ValueError on invalid values (pygeos/pygeos#263) Add box ufunc based on create_box C function (pygeos/pygeos#308) Allow s390x to fail; not yet handled in GEOS (pygeos/pygeos#316) raise error on nonscalar inputs to STRtree::nearest_all (pygeos/pygeos#313) TST: Really allow s390x to fail on Travis CI (pygeos/pygeos#319) Raise warning and return None on invalid WKB/WKT instead of raising exception (pygeos/pygeos#321) ENH: add dwithin to STRtree (pygeos/pygeos#425) BUG: Fix STRtree memory leaks (pygeos/pygeos#434) TST: Update benchmarks for pygeos=>shapely (#1424) ENH: Update STRtree API (merge query / query-bulk, return only indices) (#1422) ENH: Remove "shapely" name and duplicate WKT type from __repr__ (#1412) ENH: Update STRtree nearest neighbor API (#1428) ENH: Remove Geometry() constructor usage and use concrete geometry type constructors or from_wkt (#1414) Fix: update geometry repr used in docstrings to pass doctests (#1451) DOC: Improve STRtree docstrings (#1626) Casper van der Wel (256): First commit to pygeos Fix indentation in README Add Gd_G functions (e.g. simplify) Redo the list of functions WIP on uint32 functions Implement integer fucntions Clean Changes for distribution Changes for distribution WIP Add extension type Working contains2 New Geometry constructor Working intersection2 Working YY_b and YY_Y funcs Refactor Add Y_b functions Some tests Add Y_Y functions Y_d functions Add Y_l functions Y_B functions Distance functions Add Yd_Y functions Add Yl_Y More strict int types Project functions Add special functions Add normalize Clean and readme Bump to 0.2 Fix readme and geometry construction Add point construction ufunc Minor fixes Rename Point to points Point from tuples Make use of generalized ufunc Added test for dimensionality Implement points, linearrings, linestrings and improve exception handling Finish linearring Polygons Polygeons and collections Readme Package static files NaN / None handling Deal with nan for predicates Version to dev Skip NaN in collection creation Optimization WKT and WKB writers Finish WKB/WKT IO Typo Tests and safety for GEOSGeometry Readme and bump Setup travis and code formatting Version to dev Add numpy include Add pygeos.ufuncs as package Add build_ext Setup Travis and attempt to set up Appveyor (pygeos/pygeos#13) Rewrite setup.py enabling compilation on windows Readme Repair build, remove construction from ptr Also deallocate arrays Fix warnings Use master badge Attempt fix for win Simplify appveyor Fix RAISE_NO_MALLOC Haussdorf distance Buffer with style Refactor Refactor + buffer Docstrings Fix readme Refactor functions into separate modules Refactor into submodules Add voronoi and delaunay functions Free WKT and WKB buffers; tested with valgrind Appveyor fix attempt Add documentation for Y_b functions Add documentation to unary predicates Finish unary predicates Fix doctests PyPI badge Skip doctest on Py3.5 WIP Docs for predicates Update README.rst (pygeos/pygeos#20) RTD docs build Install . on RTD Fix indentation Only install GEOS using conda Try with setup.py install Typos and fixes in docs Document the boundary function Document buffer Document centroid and remove clone Document convex_hull Add constructive to API docs Add envelope docs Simplify and snap Finish constructive docs Pin numpydoc to 0.7.0 on RTD Rewrite constructive tests + fixes Fix travis Syntax fix for Py3.5 Docs WIP Finish setop docs Fix tests Simplify Fix Tests for set operations Integrate get element functions Finish element counters and getters Also fix get_exterior_ring Move has_z, remove normalize, finish get_x and get_y Docs Unittests Document and test measurement funcs Tests for pygeos.length Fix doctest rounding WIP On separating Missing and Empty Fix and finish Fix readme Some docs PR Changes after review Return NaN for distance to EMPTY Added is_valid_input Docstrings Setup versioneer Add geos_version Add LICENSE to MANIFEST RLS: 0.4 ENH: Get and set coordinates as a array of floats (pygeos/pygeos#44) Finish API docs (pygeos/pygeos#53) Moved to pygeos org (pygeos/pygeos#56) Rewrite Travis CI script (pygeos/pygeos#59) Add extern in header files (pygeos/pygeos#79) ENH: Add STRtree (pygeos/pygeos#58) [ENH] Add bounds function (pygeos/pygeos#69) ENH: Implement from_shapely (pygeos/pygeos#61) Textual changes + test Fix strtree header file (pygeos/pygeos#91) CI: Test on python 3.8 (pygeos/pygeos#101) Gitignore ENH: Add any pygeos/*.dll files for Windows binary .whl files (pygeos/pygeos#103) Benchmarking suite (asv) (pygeos/pygeos#96) BUG: Check types in create_collections (pygeos/pygeos#86) Fix segfault in strtree test_flush_geometries (pygeos/pygeos#100) ENH: Implement hash, eq, neq (pygeos/pygeos#102) Include GEOS license info (pygeos/pygeos#118) RLS: 0.7.1 Version conditional: make_valid (pygeos/pygeos#120) Eliminate global GEOS context and release GIL (pygeos/pygeos#113) Add release notes (pygeos/pygeos#158) Fix memleak in strtree creation (introduced in pygeos/pygeos#144) (pygeos/pygeos#162) Fix memory leak in from_shapely (introduced in pygeos/pygeos#144) (pygeos/pygeos#163) Release the GIL for geometry-creating operations (pygeos/pygeos#156) Memory leak testing using valgrind (pygeos/pygeos#159) DOC: Update docs, add multithreading section (pygeos/pygeos#169) FIX: Accept linearrings in pygeos.multilinestrings (pygeos/pygeos#168) Raise ValueError on to_wkt of multipoint with empty point (pygeos/pygeos#171) [DONE] Fix POINT EMPTY to_wkb (pygeos/pygeos#179) Fix segfault on linestring/linearring/polygon creation (pygeos/pygeos#187) Accept multi geometries in boundary() (pygeos/pygeos#188) Update classifiers in setup.py RLS: 0.8 Fix release date in changelog Add Zenodo badge Limit WKT length in repr (pygeos/pygeos#189) Support pickling (pygeos/pygeos#190) Fix bug when setting coordinates on an empty point (pygeos/pygeos#199) Implement is_ccw for GEOS >= 3.7.0 (pygeos/pygeos#201) Minor doc changes (pygeos/pygeos#202) Re-add GeometryType -1 (but name it MISSING) (pygeos/pygeos#204) Format C code using clang-format with Google style (pygeos/pygeos#203) Release GIL for is_geometry, is_missing and is_valid_input (pygeos/pygeos#207) Fix line_interpolate_point for multilinestrings (pygeos/pygeos#208) Add Cython to RTD build (pygeos/pygeos#236) CI: Cull windows tests and shorten name (pygeos/pygeos#237) FIX: Consistent behaviour for all reduction set_operations (pygeos/pygeos#249) ENH: Add is_prepared (pygeos/pygeos#252) [API] Set None as default axis for reduction operations (pygeos/pygeos#266) Update changes (pygeos/pygeos#282) Fix mistake in changes RLS: 0.9 Prepare 0.10 Add travis for different CPU archs (pygeos/pygeos#296) NaN equality tests for GEOS 3.10 (pygeos/pygeos#304) Pin endianness in to_wkb tests (pygeos/pygeos#305) Also clean build/lib.*/pygeos in setup.py clean (pygeos/pygeos#307) Fix badges Fix creation error handling and release GIL (pygeos/pygeos#310) Accept indices in collection constructors (pygeos/pygeos#290) Enable "return_index" in get_coordinates (pygeos/pygeos#318) Create simple geometries from coordinates and indices (pygeos/pygeos#322) Fix the badges Only run doctests on conda-forge, latest Py38 (pygeos/pygeos#325) Add flake8 linter and format repo (pygeos/pygeos#328) DOC: Add kwargs where necessary and document it (pygeos/pygeos#327) Release the GIL in shared_paths (missing decorator) (pygeos/pygeos#331) Create polygons from indices (pygeos/pygeos#326) Show docstrings for functions decorated with requires_geos (pygeos/pygeos#341) Merge polygons_1d into collections_1d + finish implementation for rls 0.10 (pygeos/pygeos#346) Remove minimum_rotated_rectangle duplicate + fix docstrings (pygeos/pygeos#350) Exclude Cythonized .c files from distributions (pygeos/pygeos#351) Contributors RLS: 0.10 Back to 0.11 dev FIX: Testing on Pypy (pygeos/pygeos#353) FIX: Handle NULL in object-dtype arrays (pygeos/pygeos#374) Build wheels on CI with cibuildwheel (pygeos/pygeos#365) RLS: 0.10.2a1 RLS: 0.10.2a2 Fix requires_geos with methods (pygeos/pygeos#376) RLS: 0.10.2 Back to 0.11dev [skip ci] Handle linearrings in is_closed (pygeos/pygeos#379) Handle 'out' keyword argument in constructors if indices are given (pygeos/pygeos#380) Add pygeos.empty (pygeos/pygeos#381) Replace appveyor with gh actions (pygeos/pygeos#382) Fix WKB/WKT of empty (multi)points on GEOS 3.9 (pygeos/pygeos#392) Write docs for runtime library finding + clean CI runners (pygeos/pygeos#387) Trigger build Disallow linearrings with 3 coordinates in GEOS 3.10 (pygeos/pygeos#378) CI: Fix GEOS main caching (pygeos/pygeos#399) Force 2D/3D (pygeos/pygeos#396) Fix 3D empty WKT serialization (pygeos/pygeos#403) Fix GEOS 3.10 tests for linearring construction (pygeos/pygeos#408) Update docstring of STRTree assert_geometries_equal (pygeos/pygeos#401) Adapt set_precision API and fix remaining GEOS 3.10 tests (pygeos/pygeos#410) Fix segfault when getting coordinates from empty points (pygeos/pygeos#415) Revert GEOS 3.8 version in test runner wheels: Add Python 3.10 and GEOS 3.10.0 (pygeos/pygeos#416) RLS: 0.11 Back to 0.12 development [ci skip] RLS: 0.11.1 GeoJSON IO for GEOS 3.10 (pygeos/pygeos#413) Fix tests for GEOS main (pygeos/pygeos#419) Revert Win32 CI version for faster builds (pygeos/pygeos#420) Reinstate may_segfault for from_geojson (pygeos/pygeos#418) dwithin for GEOS 3.10.0 (pygeos/pygeos#417) Revert changes from pygeos/pygeos#418 (pygeos/pygeos#426) OSX arm64 and universal2 wheels (pygeos/pygeos#427) Fix error handling in STRtree (pygeos/pygeos#432) Change linearring closing logic (pygeos/pygeos#431) Documentation fixes (pygeos/pygeos#430) Solve RuntimeWarnings in tests (pygeos/pygeos#441) Arm64 wheel builds on Travis (pygeos/pygeos#444) Clean the NoticeHandler (#1329) CI: Fix the release workflows (GHA and travis CI) (#1253) Fix segfault in reduction functions (#1517) ENH: Check signals every 10000 ufunc iteration (#1370) COMPAT: Add compat for unpickling shapely<2 geometries (#1657) Ewout ter Hoeven (4): CI: Enable Python 3.11, update used actions (#1560) release CI: Update used actions to latest versions / Python 3.11 wheels (#1561) Add Dependabot configuration for GitHub Actions updates (#1597) release CI: Use release/v1 branch for PyPI publish action (#1646) Geir Arne Hjelle (1): ENH: Add concave_hull() function (#1518) James Gaboardi (1): CI: flake8 has migrated to GH – update .pre-commit (#1614) James Myatt (1): DOC: Fix docstring for get_coordinates (pygeos/pygeos#340) Joris Van den Bossche (199): Split single ufuncs.c file in multiple files cleanup init_geom_type signature + remove unreachable code in GeometryObject_new Add LICENSE BLD: use angle bracket include for numpy Update README to include conda-forge installation instructions Refactor ufuncs module into lib module (pygeos/pygeos#48) ENH: add wkt / wkb ufuncs (pygeos/pygeos#45) ENH: add equals_exact predicate (pygeos/pygeos#57) Ensure to only use GEOS reentrant API (pygeos/pygeos#63) RLS: 0.5 Small updates to the README (pygeos/pygeos#68) RLS: 0.6 RLS: 0.7 ENH: add normalize (pygeos/pygeos#123) Fix spacing in README (pygeos/pygeos#173) Rename get_coordinate_dimension (dimensions -> dimension) (pygeos/pygeos#176) ENH: ability to get z-coordinates in get_coordinates (pygeos/pygeos#178) Release the GIL for STRtree bulk_query (pygeos/pygeos#174) ENH: Add get_z ufunc (pygeos/pygeos#175) ENH: Add subclass registry (enable subclassing pygeos.Geometry) (pygeos/pygeos#182) ENH: add relate() function (pygeos/pygeos#186) Delay shapely import (pygeos/pygeos#193) BLD: allow GEOS_CONFIG env variable to override PATH (pygeos/pygeos#200) BUG: Fix error handling for line_locate_point (GEOSProject(Normalized)) (pygeos/pygeos#216) ENH: add minimum_clearance (pygeos/pygeos#223) TST: Fix make_valid tests for OverlayNG (normalize result/expected) (pygeos/pygeos#232) ENH: offset_curve (pygeos/pygeos#229) ENH: support z-coordinates in apply (coordinate transformation) (pygeos/pygeos#221) CI: move Travis linux builds to Github Actions (pygeos/pygeos#240) ENH: prepared geometry as additional (cached) attribute on GeometryObject (pygeos/pygeos#92) CLN: deduplicate some code with macros in geometry-creating ufuncs (pygeos/pygeos#230) ENH: relate_pattern (pygeos/pygeos#245) ENH: clip_by_rect (pygeos/pygeos#273) Update for compatibility with numpy 1.20 (builtin type aliases, array coercion) (pygeos/pygeos#269) TST: fix from_shapely test for numpy 1.20 (pygeos/pygeos#278) CI: add GEOS 3.9.0 build to linux CI (pygeos/pygeos#279) DOC: fix style issue with numpydoc parameter names and sphinx_rtd_theme (pygeos/pygeos#283) Update ASV configuration (pygeos/pygeos#285) ENH: add contains_properly predicate function (pygeos/pygeos#267) Change default STRtree leaf size (node capacity) to 10 (pygeos/pygeos#286) Update pin for numpy version for Python 3.9 in pyproject.toml (pygeos/pygeos#295) ENH: add polygonize ufunc (pygeos/pygeos#275) Add back pygeos.strtree.VALID_PREDICATES for now (pygeos/pygeos#309) ENH: add polygonize_full (pygeos/pygeos#298) Add pre-commit configuration (pygeos/pygeos#330) DOC: clarify that set_coordinates modifies array of geometries in place (pygeos/pygeos#335) Explode polygons into rings: get_rings (pygeos/pygeos#342) Fix use of C logical operator (pygeos/pygeos#348) ENH: Add shortest_line (nearest_points) ufunc (pygeos/pygeos#334) Fix multi-threaded STRtree query by ensuring it is built on creation (pygeos/pygeos#362) BUG: fix no inplace output check for box and set_precision (pygeos/pygeos#367) RLS: update changelog for bug-fix release (pygeos/pygeos#369) Release workflow: automate sdist creation / GitHub release (pygeos/pygeos#370) Fix tag selector for release workflow RLS: 0.10.1 CI: Fix failing Windows github actions (pygeos/pygeos#406) [2.0] Remove mutability of geometries (#960) [2.0] Remove deprecated asShape / adapter classes (#961) [2.0] Remove public ctypes and array interface (#977) [2.0] Remove iteration / getitem from multi-part geometries (#982) Refactor Geometry classes to subclass the C extension type (#983) Refactor affine_transform: use general function apply on coordinates (#1019) Clean-up use of impl/lgeos/delegated/exceptNull in shapely/geometry/ (#1020) Remove cython code: remove the speedups module + refactor the vectorized module (#1036) Refactor shapely.prepared to use prepared base geometries (#1039) Clean-up impl: remove impl.py + all helper classes (#1052) Remove usage of lgeos in shapely.validation (#1067) [2.0] Remove len() (__len__) for multi-part geometries (#1114) Refactor shapely.ops to not use lgeos (#1065) Refactor pickling of LinearRing to not use lgeos (#1162) [2.0] Disallow setting custom attributes on geometry objects (#1181) Refactor strtree to not use lgeos / ctypes (#1161) [2.0] Remove shapely.geos.lgeos ctypes interface to GEOS (#1163) TST: fix tests on Windows for python >= 3.8 (#1213) Update GEOS url (pygeos/pygeos#435) Clean-up old/unused files and scripts (#1219) PERF: Use GEOSCoordSeq_copyFromBuffer for creating simple geometries (pygeos/pygeos#436) Migration to Shapely: rename conflicting files Move pygeos/* files into shapely/ python package Rename pygeos -> shapely in the python package Minimal changes (setup.py, rename geometry.py(x)) for working package Remove PyGEOS/Shapely conversion layer (from/to_shapely functions) (#1238) Minimal pygeos->shapely renaming in C code to get cython API working (#1240) TST: fix search/replace mistake in test_empty (#1244) BUG: fixup the hashability of geometries (#1239) Remove now unused shapely._buildcfg module (#1222) CI: consolidate the build scripts and github actions tests workflow (#1241) Replace Toblerity/Shapely -> shapely/shapely (#1255) Linting: blacken shapely code (#1242) TST: Move + clean-up tests for the scalar geometry subclasses (#1257) Update .gitignore for Shapely->shapely repo rename Linting: update pre-commit and setup.cfg configuration + pass black / flake8 / isort (#1265) CLN: remove deprecation warning for setattr (which now raises) (#1266) BUG: Polygon constructor with multiple variable-sized holes (#1229) Fix doctests to be more robust with different versions of GEOS (#1228) TST: test that Geometry subclasses properly return NotImplemented in comparison with non-geometry (#1282) BUG: fix Polygon() constructor from a LineString (#1277) BUG: fix linestring/linearring creation (copyFromBuffer usage) to check for dimension (#1274) TST: Move + clean-up more geometry-class specific tests (#1275) TST: remove filterwarnings for numpy 1.21 (#1304) Pickling: fix SRID handling + update linearring test (#1245) PERF: speed-up bounds function with GEOSGeom_getXMin et al (GEOS >= 3.7.0) (#1299) CLN: remove no longer used custom error classes (#1306) REF: Move ShapelyError base class to C, GEOSException becomes subclass (#1314) Consolidate error class for unsupported GEOS version functionality (#1305) Remove logging related tests (#1308) Expose the geometry subclasses in the top-level namespace (#1339) Deprecate calling the BaseGeometry constructor + EmptyGeometry class (#1303) CI: update black to fix click compat issue (#1355) TST: update tests to pass with numpy 1.22 and pytest 8 (#1356) Remove deprecation warning from GeometryTypeError (#1358) API: update STRtree interface (merge shapely/pygeos features) (#1251) TST: fix tests for GEOS main (#1357) Update repr for the Geometry classes (#1302) CI: only build Travis on the main branch (not PRs) (#1382) CI: fix Travis tests (#1384) DOC: Move pygeos doc pages into shapely docs (#1377) DEPR: deprecate the GeometryType attribute (#1375) CI: fix tests with latest setuptools (#1388) CLN: remove unused vendored packaging, consolidate gitignore, remove old pygeos pyproject.toml (#1389) DOC: replace pygeos -> shapely in the reference docs (#1394) DOC: update class (init/new) docstrings of Geometry subclasses (#1395) DOC: fix / consolidate the readthedocs configuration (#1397) Update LICENSE file and copyright holder (#1403) Add aliases for project/interpolate/representative_point methods (#1340) Change simplify() preserve_topology default to True (match the Geometry method) (#1392) API: change the bounds of an empty geometry from empty tuple to tuple of NaNs (#1416) API: all-empty GeometryCollection .geoms to return empty subgeoms (#1420) API: remove __geom__, keep _geom read-only access to GEOS pointer (#1417) Consolidate setup.py metadata, remove old setup.py files (#1376) DOC: restructure the combined docs + new theme (#1402) DOC: update the installation documentation (#1396) Rename shapely.apply to shapely.transform (#1393) CLN: removed unused shape_factory + HeterogeneousGeometrySequence (#1421) CLN: remove unused _geos.pxi GEOS cython declarations (#1419) Consolidate README files (#1378) DOC: update examples in manual.rst (#1391) DOC: fix repr in example (#1452) RLS: 2.0a1 ENH: expose fixed precision overlay (grid_size keyword) in the Geometry methods as well (#1468) CLN: actually remove the base class Geometry() constructor (#1476) DOC: add changelog for Shapely 2.0 (#1442) PERF: use GEOSCoordSeq_copyToBuffer for get_coordinates (GEOS >= 3.10) (#1511) DOC/CLN: clean-up conf.py and unused docs files (#1519) ENH: expose dwithin on the Geometry subclasses (#1496) DOC/RLS: update CHANGES.txt with last releases, move old releases to docs (#1520) PERF: use GEOSGeom_getExtent for GEOS>=3.11 in bounds ufunc (#1477) API: use quad_segs for buffer keyword instead of resolution (#1512) RLS/CI: update GEOS to 3.11.0 for wheels (#1527) COMPAT: keep old exception sublcasses as (deprecated) ShapelyError aliases (#1538) COMPAT: keep (deprecated) geom_factory for downstream packages (cartopy) (#1534) Add unary_union alias for top-level union_all (#1536) CLN: remove custom minimum_rotated_rectangle implementation + add oriented_envelope alias (#1532) DOC: update offset_curve (parallel_offset) documentation regarding direction of the resulting line (#1537) DOC: autogenerate separate reference pages per function with autosummary (#1529) ENH: shapely.plotting module with basic matplotlib-based functionality (+ updated docs to use this) (#1497) DOC/CI: fix doc build for latex + re-enable epub and htmlzip (#1549) PERF: improve performance of Point(x, y) constructor (#1547) Make Geometry objects weakref-able (#1535) CI: add PyPI token for travis wheel uploads (splitted secret) (#1554) API: restore unary_union behaviour on empty list to return empty GeometryCollection (#1553) DOC: various small fixes to sphinx building (#1558) PERF: reintroduce global context and use in GeometryObject dealloc (#1530) DOC: add migration guide for PyGEOS users (#1557) Refactor reducing set operations as gufuncs + return emtpy collection for empty/all-None input (#1562) CI: update cibuildwheel version in travis as well (#1574) RLS: 2.0b1 BUG: move weakref-able implementation to base C extension type (fix PyPy) (#1577) CI: fix Travis deploy step for non-wheel jobs + try avoid building sdist (#1576) API: rename 'radius' -> 'distance' keyword in shapely.buffer() for consistency (#1589) Allow passing len-1 array for x and y coordinates in Point(..) (compat with 1.8) (#1590) RLS: 2.0b2 DOC: automatically fill in correct version (#1595) CI: ensure doctests are running (#1596) Document Point(..) constructor change no longer allowing coordinate sequence of len > 1 (#1600) ENH: allow Geometry methods to return arrays if passed array as argument (#1599) ENH: Add node function (#1431) PERF: restore speed of LineString(..) from numpy array of coordinates (#1602) ENH: expose contains_properly on the Geometry subclasses (#1605) ENH: faster contains_xy/intersects_xy predicates special casing for point coordinates (#1548) CLN: clean c code - remove unused variables / functions (#1619) CI/TST: fix tests for voronoi_diagram for latest GEOS (#1625) CI/TST: fix tests for changed numpy error from creating ragged array (#1627) ENH: convert to / construct from ragged array (flat coordinates and offset arrays) (#1559) ENH: expose flavor keyword in to_wkb (#1628) CI/RLS: set up CircleCI to build Linux aarch64 wheels (instead of Travis CI) (#1624) RLS: 2.0rc1 CI/RLS: ensure to run CircleCI on tags (#1634) TST: fix test_to_wkb_flavor to use fixed byte_order to pass on big endian machine (#1635) CI: fix circle config syntax CLN: remove shapely/examples submodule (#1645) TST: fix tests for GEOS changes in M handling (#1647) RLS: 2.0rc2 DEV: update valgrind Dockerfile (#1649) DOC: add note about prepare + touches to contains_xy/intersects_xy docstrings (#1631) RLS: 2.0rc3 TST: skip intermittent remove_repeated_points failure for GEOS 3.11 (#1656) DOC/RLS: update release notes for final 2.0.0 (#1659) RLS: 2.0.0 Keith Jenkins (1): fix typo (#1465) Kian Meng Ang (1): Fix typos (#1212) Krishna Chaitanya (5): Implement constructive.build_area (GEOS 3.8.0+) (pygeos/pygeos#141) Implement wrappers for Fréchet distance under measurement module (3.7.0+) (pygeos/pygeos#144) Fix typo in haussdorf -> hausdorff (pygeos/pygeos#151) Refactor GEOS_SINCE_3X0 to GEOS_SINCE_3_X_0 (pygeos/pygeos#152) Implement GEOSCoverageUnion_r under set_operations (GEOS 3.8.0+) (pygeos/pygeos#142) Kyle Barron (1): DOC: Fix typo in `from_ragged_array` docstring (#1658) Martin Fleischmann (3): DOC: add missing modules (pygeos/pygeos#136) ENH: add minimum_bounding_circle and minimum_bounding_radius (pygeos/pygeos#315) ENH: add oriented_envelope (minimum rotated rectangle) (pygeos/pygeos#314) Martin Lackner (1): Fix typos in docstring of pygeos.creation.box (pygeos/pygeos#191) Mike Taves (38): MAINT,DOC: change RTD channel to just 'defaults', pin versions (pygeos/pygeos#106) Rename normalize -> normalized in linear referencing functions (pygeos/pygeos#209) TST: Use native CI build tools to allow flexible GEOS versions (pygeos/pygeos#219) FIX: handle non-integer GEOS_VERSION_PATCH like 0beta1 as 0 (pygeos/pygeos#262) CI: bump versions to latest GEOS-3.9.1 (pygeos/pygeos#300) TST: ubuntu-16.04 about to reach EOL; upgrade to ubuntu-latest (pygeos/pygeos#347) TST: rename head branch for GEOS from 'master' to 'main' (pygeos/pygeos#360) Increment testing for geos, python and numpy versions for 2021 (pygeos/pygeos#409) Update README for 'main' branch (#1209) CI: upgrade GEOS versions, fix "Run doctests" (pygeos/pygeos#422) DOC: Update URLs for GEOS, PostGIS and use HTTPS for Code of Conduct TST: linearring closing logic was changed with pygeos (#1232) BUG/TST: fix hashing for Polygon + update tests (#1250) Update MANIFEST.in to enable 'python -m build` to work (#1249) Fix GitHub Actions badge svg, remove appveyor placeholder (#1273) CI: upgrade GEOS patch versions for tests and release (#1408) CI: add testing for 2022, including GEOS-3.11 (#1437) PERF: use numpy matmul for affine transformation (#1418) Require Python 3.7+, NumPy 1.14+ (#1453) CI: macOS-10.15 is deprecated, upgrade to macOS-11 (#1458) Move static metadata from setup.py to pyproject.toml, add sdist check (#1426) MAINT: remove workarounds when numpy was optional (#1461) MAINT: use modern Python coding styles (from pyupgrade) (#1462) CLN: Rename `__p__`→`_parent`, clean-up `gtag`, `_factory` and `__rings__` (#1467) DEPR: deprecate the type attribute (#1492) DOC: update migration guide to use 'packaging' instead of 'distutils' (#1502) TST: change WKT tests with inconsistent dimensionality for GEOS 3.12 (#1542) Add CITATION.cff, remove CITATION.txt (#1455) TST: clean-up test_doctests (with binascii_hex), refactor test_hash (#1586) Raise ValueError for non-finite distance to buffer/offset_curve (#1522) ENH: add `__format__` specification for geometry types (#1556) MAINT: Add Python 3.11 classifier and upgrade to GEOS 3.11.1; other CI upgrades (#1607) MAINT: remove requirements-dev.txt; expand optional dependencies in pyproject.toml (#1606) DOC: clean-up docstrings and Sphinx markup for deprecated functions (#1611) DEP: remove 'preserve_topology' from 'set_precision()' (#1612) DEP: change `almost_equals()` to be removed from version 2.0 to 2.1 (#1604) CLN/DOC: credits, miscellaneous clean-up, file modes, doc touchup (#1629) BLD: pin to Cython~=0.29, ignore .c and .pyx files in wheels (#1632) Phil Chiu (1): PERF: vectorized implementation for signed area (#1323) Tom Clancy (1): Add additional benchmarks (pygeos/pygeos#145) dependabot[bot] (4): Bump actions/setup-python from 2 to 4 (#1640) Bump actions/checkout from 2 to 3 (#1644) Bump pre-commit/action from 2.0.0 to 3.0.0 (#1642) Bump pypa/cibuildwheel from 2.10.2 to 2.11.2 (#1643) enrico ferreguti (3): TST: rewrite tests using pytest assert (#1505) Make parallel_offset an alias for offset_curve (#1510) TST: assert rewriting in tests (#1514) gpapadok (2): ENH: Add segmentize method to BaseGeometry (#1434) ENH: Add reverse method to BaseGeometry (#1457) mattijn (1): Reintroduce shared_paths (pygeos/pygeos#77) odidev (1): Add linux aarch64 wheel build support (pygeos/pygeos#386)

Add STRtree class

81b5ce7

caspervdw changed the title ~~Add STRtree~~ [WIP] Add STRtree Oct 16, 2019

caspervdw added 3 commits October 18, 2019 20:19

Insert geometries

0b42c8c

Fix init / dealloc

4a5f0c5

Implement tree.query

9c8301b

caspervdw changed the title ~~[WIP] Add STRtree~~ [Ready for review] Add STRtree Oct 20, 2019

caspervdw requested a review from jorisvandenbossche October 20, 2019 12:36

Merge branch 'master' into strtree

af3ba23

caspervdw added this to the 0.5 milestone Oct 21, 2019

Tests and docs

6f272da

jorisvandenbossche reviewed Oct 21, 2019

View reviewed changes

pygeos/strtree.py Show resolved Hide resolved

jorisvandenbossche reviewed Oct 21, 2019

View reviewed changes

src/strtree.c Outdated Show resolved Hide resolved

src/strtree.h Outdated Show resolved Hide resolved

pygeos/test/test_strtree.py Outdated Show resolved Hide resolved

caspervdw modified the milestones: 0.5, 0.6 Oct 25, 2019

caspervdw added 5 commits October 28, 2019 10:03

Return indices, not geometries

eb14da7

Merge branch 'master' into strtree

1bb5196

Some tests

fd271ff

Handle query of None

4c41168

Raise and cleanup on init with no geometry

f7c3fc1

Simplify reference keeping

9b1be45

jorisvandenbossche mentioned this pull request Nov 10, 2019

include shared_paths function #73

Closed

jorisvandenbossche changed the title ~~[Ready for review] Add STRtree~~ ENH: Add STRtree Nov 11, 2019

jorisvandenbossche approved these changes Nov 11, 2019

View reviewed changes

caspervdw added 5 commits November 12, 2019 21:34

PR fixes

290d009

Doc

fb45f74

Fix test

6d8d274

Comment out test

8a02486

Attempt to fix segfault with geos < 3.7

f5bfc9a

correctly initialize count

59fc590

jorisvandenbossche merged commit c7854c8 into pygeos:master Nov 20, 2019

jorisvandenbossche pushed a commit to jorisvandenbossche/shapely that referenced this pull request Nov 29, 2021

ENH: Add STRtree (pygeos/pygeos#58)

0459284

Conversation

caspervdw commented Oct 16, 2019 • edited by jorisvandenbossche Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

caspervdw commented Oct 20, 2019

Uh oh!

caspervdw commented Oct 20, 2019

Uh oh!

Uh oh!

jorisvandenbossche commented Oct 21, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jorisvandenbossche commented Oct 21, 2019

Uh oh!

jorisvandenbossche left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

caspervdw commented Oct 28, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jorisvandenbossche commented Oct 28, 2019

Uh oh!

jorisvandenbossche commented Oct 28, 2019

Uh oh!

caspervdw commented Oct 28, 2019

Uh oh!

jorisvandenbossche commented Oct 29, 2019

Uh oh!

caspervdw commented Nov 5, 2019

Uh oh!

jorisvandenbossche commented Nov 11, 2019

Uh oh!

jorisvandenbossche left a comment

Choose a reason for hiding this comment

Uh oh!

jorisvandenbossche Nov 11, 2019

Choose a reason for hiding this comment

Uh oh!

jorisvandenbossche Nov 11, 2019

Choose a reason for hiding this comment

Uh oh!

jorisvandenbossche Nov 11, 2019

Choose a reason for hiding this comment

Uh oh!

jorisvandenbossche Nov 11, 2019

Choose a reason for hiding this comment

Uh oh!

jorisvandenbossche commented Nov 20, 2019

Uh oh!

caspervdw commented Nov 20, 2019

Uh oh!

jorisvandenbossche commented Nov 20, 2019

Uh oh!

caspervdw commented Nov 20, 2019

Uh oh!

jorisvandenbossche commented Nov 20, 2019

Uh oh!

jorisvandenbossche commented Nov 20, 2019

Uh oh!

jorisvandenbossche commented Nov 20, 2019

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

caspervdw commented Oct 16, 2019 •

edited by jorisvandenbossche

Loading

jorisvandenbossche commented Oct 21, 2019 •

edited

Loading

caspervdw commented Oct 28, 2019 •

edited

Loading