<div dir="ltr"><div>Thanks for trying to reproduce it in C/C++. One obvious difference that I can spot is that we use an integer for the "item" that gets inserted, and not the geometry itself, but I wouldn't expect that to influence the result. <br></div><div>Although, trying to update your test case to do that, the test fails. But that might also be an issue on my side due to my limited C++ experience (it already fails on the "geoms.size()" check):</div><div><br></div><div>--- a/tests/unit/capi/GEOSSTRtreeTest.cpp<br>+++ b/tests/unit/capi/GEOSSTRtreeTest.cpp<br>@@ -268,10 +268,11 @@ void object::test<8><br> {<br> GEOSSTRtree* tree = GEOSSTRtree_create(10);<br> GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");<br>- GEOSSTRtree_insert(tree, g, g);<br>+ int idx = 0;<br>+ GEOSSTRtree_insert(tree, g, (void*)idx);<br> GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");<br> <br>- typedef std::vector<GEOSGeometry*> GList;<br>+ typedef std::vector<int> GList;<br> GList geoms;<br> ensure_equals(geoms.size(), 0);<br> GEOSSTRtree_query(<br>@@ -279,23 +280,16 @@ void object::test<8><br> q,<br> [](void* item, void* userdata) {<br> GList* geoms = (GList*)userdata;<br>- geoms->push_back((GEOSGeometry*)item);<br>+ geoms->push_back(*((int *)item));<br> },<br> &geoms);<br> <br> ensure_equals(geoms.size(), 1);<br>- const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);<br>-<br>- double x = -1;<br>- double y = -1;<br>- GEOSCoordSeq_getXY(seq, 0, &x, &y);<br>- ensure_equals(x, 2.0);<br>- ensure_equals(y, 3.0);<br>+ ensure_equals(<a href="http://geoms.at">geoms.at</a>(0), 0);<br> <br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, 28 Nov 2020 at 20:55, Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca">pramsey@cleverelephant.ca</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
<br>
> On Nov 28, 2020, at 8:11 AM, Joris Van den Bossche <<a href="mailto:jorisvandenbossche@gmail.com" target="_blank">jorisvandenbossche@gmail.com</a>> wrote:<br>
> <br>
> Hi all,<br>
> <br>
> On the CI of PyGEOS we have a build testing against GEOS master, and somewhere in the last 4 days, a lot of the STRtree tests started failing (see eg <a href="https://github.com/pygeos/pygeos/runs/1465460418#step:9:86" rel="noreferrer" target="_blank">https://github.com/pygeos/pygeos/runs/1465460418#step:9:86</a>). Looking at the commits of the last days, this might be related to the SimpleSTRtree work?<br>
> <br>
> A small (python) example of a tree consisting of a single point, which no longer is returned when querying the tree with a big polygon that certainly contains the point:<br>
> <br>
> Using released version of GEOS:<br>
> <br>
> >>> import pygeos<br>
> >>> pygeos.geos_version<br>
> (3, 8, 1)<br>
> >>> point = pygeos.Geometry("POINT (2 3)") <br>
> >>> tree = pygeos.STRtree([point]) <br>
> >>> tree.query(pygeos.box(0, 0, 10, 10)) <br>
> array([0])<br>
> <br>
> This is correctly returning the index of the single point. But when running with the latest GEOS master, the query doesn't find any point of the tree:<br>
> <br>
> >>> import pygeos<br>
> >>> pygeos.geos_version<br>
> (3, 9, 0)<br>
> >>> point = pygeos.Geometry("POINT (2 3)")<br>
> >>> tree = pygeos.STRtree([point])<br>
> >>> tree.query(pygeos.box(0, 0, 10, 10))<br>
> array([], dtype=int64)<br>
> <br>
> Are there changes expected in how the STRtree C API functions or required changes in user code? Or maybe we are using it in some incorrect/unexpected way? (code is at <a href="https://github.com/pygeos/pygeos/blob/master/src/strtree.c" rel="noreferrer" target="_blank">https://github.com/pygeos/pygeos/blob/master/src/strtree.c</a>)<br>
<br>
There are changes, I don't think you're mis-using anything. I swapped the CAPI to use the SimpleSTRtree, figuring it would be good to share the performance win with downstream. However, I can swap it back to the original STRtree if this remains a problem.<br>
<br>
One thing I noticed when trying to construct GEOS envelopes directly was that annoyingly they were xmin xmax, ymin ymax, but I doubt that would be a problem in your pre-existing working test. <br>
<br>
I just reconstructed your test in the GEOS CAPI suite, and it works as one would expect. (Namely, it finds the one point.) So I'm not sure why your test is getting different results.<br>
<br>
<br>
// querying tree with box<br>
template<><br>
template<><br>
void object::test<8><br>
()<br>
{<br>
GEOSSTRtree* tree = GEOSSTRtree_create(10);<br>
GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");<br>
GEOSSTRtree_insert(tree, g, g);<br>
GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");<br>
<br>
typedef std::vector<GEOSGeometry*> GList;<br>
GList geoms;<br>
ensure_equals(geoms.size(), 0);<br>
GEOSSTRtree_query(<br>
tree,<br>
q,<br>
[](void* item, void* userdata) {<br>
GList* geoms = (GList*)userdata;<br>
geoms->push_back((GEOSGeometry*)item);<br>
},<br>
&geoms);<br>
<br>
ensure_equals(geoms.size(), 1);<br>
const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);<br>
<br>
double x = -1;<br>
double y = -1;<br>
GEOSCoordSeq_getXY(seq, 0, &x, &y);<br>
ensure_equals(x, 2.0);<br>
ensure_equals(y, 3.0);<br>
<br>
GEOSGeom_destroy(q);<br>
GEOSGeom_destroy(g);<br>
GEOSSTRtree_destroy(tree);<br>
}<br>
<br>
<br>
<br>
<br>
<br>
> <br>
> Best,<br>
> Joris<br>
> <br>
> <br>
> On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca" target="_blank">pramsey@cleverelephant.ca</a>> wrote:<br>
> Hey all, just truing up what's underway and nearly there...<br>
> <br>
> - Am I right that Z coordinates are nearly done? What's the status there?<br>
> <br>
> I've been trying to address some performance issues, with some success and some ... other things. <br>
> <br>
> The success is the SimpleSTRtree, which is just the current STRtree but without the inheritance structure and with the nodes stored all next to each other in contiguous memory for more locality. For at least one use case I've seen 20% speed-ups on overlays, using the SimpleSTRtree in place of the STRtree inside the MCIndexNoder. I have not seen any slow-downs. I have pushed the SimpleSTRtree into master.<br>
> <br>
> While I have implemented the nearestNeighbor() functionality on the SimpleSTRtree, I haven't hooked it up to anything yet. It could go into the IndexedFacetDistance, if anyone is super enthusiastic about it. From there it would affect searching in PreparedGeometry of various sorts.<br>
> <br>
> I also tried using a similar trick with the MonotoneChainBuilder that sits inside the MCIndexNoder, replacing individual heap allocations with slabs by putting objects onto a std::deque, and incidentally stripping out some book-keeping. While that seems to pick up about 3-5% speedwise, unfortunately something about my implementation is incorrect (and in a wonderfully subtle way) as it fails testing on some platforms (not mine). <a href="https://github.com/pramsey/geos/tree/monotone-chain-builder" rel="noreferrer" target="_blank">https://github.com/pramsey/geos/tree/monotone-chain-builder</a><br>
> <br>
> I've put that work to the side for now.<br>
> <br>
> All the performance talk is mostly because JTS still runs a lot faster than GEOS for some bulk processing. My current test is a big union of watershed boundaries, about 6MB of data, which takes about 20s under GEOS and about 25% of that under JTS. It's a big gap, and in theory the two code bases are pretty aligned right now. Same overlayNG engine, etc. So I figure there has to be a big implementation ball of performance hiding under the covers somewhere. No luck thus far.<br>
> <br>
> I think we're close, looking forward to release :)<br>
> <br>
> P<br>
> _______________________________________________<br>
> geos-devel mailing list<br>
> <a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
> <a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
> _______________________________________________<br>
> geos-devel mailing list<br>
> <a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
> <a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
<br>
_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
</blockquote></div></div>