[geos-devel] Update to 3.9?
Joris Van den Bossche
jorisvandenbossche at gmail.com
Sun Nov 29 00:26:59 PST 2020
On Sat, 28 Nov 2020 at 22:24, Paul Ramsey <pramsey at cleverelephant.ca> wrote:
>
> > On Nov 28, 2020, at 1:13 PM, Paul Ramsey <pramsey at cleverelephant.ca>
> wrote:
> >
> >> On Nov 28, 2020, at 1:11 PM, Paul Ramsey <pramsey at cleverelephant.ca>
> wrote:
> >>
> >>> On Nov 28, 2020, at 1:05 PM, Joris Van den Bossche <
> jorisvandenbossche at gmail.com> wrote:
> >>>
> >>> On Sat, 28 Nov 2020 at 21:53, Paul Ramsey <pramsey at cleverelephant.ca>
> wrote:
> >>>
> >>>> On Nov 28, 2020, at 12:44 PM, Joris Van den Bossche <
> jorisvandenbossche at gmail.com> wrote:
> >>>>
> >>>> 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.
> >>>> 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):
> >>>
> >>> Nope still not seeing it... one small mistake in your query
> >>>
> >>> Also not if you try my original code *with* the mistake?
> >>
> >> Well, with the mistake the code is saying "here's a null pointer"
> (since that's what casting 0 to a void* will get you) index this. I'll see!
> It shouldn't really matter from an index point-of-view, it should still
> index it and return a null pointer out the back end.
> >
> > And indeed it does not work. So, something to examine... why can we not
> index with a null item?
>
> Because I was using a non-null item pointer as a cue that the node was a
> leaf node, so it wasn't picking up null items as leaves.
> So, I've pushed that fix, does that change your test suite all that much?
>
> Yes, thanks, that fixes our tests.
Now, as mentioned on the commit comments on github (
https://github.com/libgeos/geos/commit/ad0122541f85886cf9eb9dd65d8246e0144f7ffa#commitcomment-44623679),
if you rather not support this on the GEOS side, I am fine with having to
fix this in PyGEOS to have it working correctly with GEOS 3.9.
I quickly started looking at a fix in PyGEOS at
https://github.com/pygeos/pygeos/pull/261 (it's not yet working though, I
suppose because we need to keep track of the inserted items)
> P
>
>
> >
> > P
> >
> >>
> >>> Because your version indeed passes for me as well, but I *think* the
> version I wrote resembles more closely the PyGEOS code (so it might be an
> issue in our C code on how we use the tree).
> >>>
> >>> , trying to cast the int to a void, instead of passing in a the
> pointer to the address, here's one that works. Unfortunately that leaves us
> no closer to knowing why the SimpleSTRtree is unhappy in the python
> context. I fear I may just have to revert the CAPI to the old tree.
> >>>
> >>>
> >>> // querying tree with box
> >>> template<>
> >>> template<>
> >>> void object::test<9>
> >>> ()
> >>> {
> >>> GEOSSTRtree* tree = GEOSSTRtree_create(10);
> >>>
> >>> GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
> >>> int payload = 876;
> >>> GEOSSTRtree_insert(tree, g, &payload);
> >>>
> >>> GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0 10,
> 0 0))");
> >>>
> >>> typedef std::vector<int*> IList;
> >>> IList items;
> >>> ensure_equals(items.size(), 0);
> >>> GEOSSTRtree_query(
> >>> tree,
> >>> q,
> >>> [](void* item, void* userdata) {
> >>> IList* items = (IList*)userdata;
> >>> items->push_back((int*)item);
> >>> },
> >>> &items);
> >>>
> >>> ensure_equals(items.size(), 1);
> >>>
> >>> ensure_equals(*(items[0]), payload);
> >>>
> >>> GEOSGeom_destroy(q);
> >>> GEOSGeom_destroy(g);
> >>> GEOSSTRtree_destroy(tree);
> >>> }
> >>>
> >>>
> >>>
> >>>
> >>>>
> >>>> --- a/tests/unit/capi/GEOSSTRtreeTest.cpp
> >>>> +++ b/tests/unit/capi/GEOSSTRtreeTest.cpp
> >>>> @@ -268,10 +268,11 @@ void object::test<8>
> >>>> {
> >>>> GEOSSTRtree* tree = GEOSSTRtree_create(10);
> >>>> GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
> >>>> - GEOSSTRtree_insert(tree, g, g);
> >>>> + int idx = 0;
> >>>> + GEOSSTRtree_insert(tree, g, (void*)idx);
> >>>> GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0
> 10, 0 0))");
> >>>>
> >>>> - typedef std::vector<GEOSGeometry*> GList;
> >>>> + typedef std::vector<int> GList;
> >>>> GList geoms;
> >>>> ensure_equals(geoms.size(), 0);
> >>>> GEOSSTRtree_query(
> >>>> @@ -279,23 +280,16 @@ void object::test<8>
> >>>> q,
> >>>> [](void* item, void* userdata) {
> >>>> GList* geoms = (GList*)userdata;
> >>>> - geoms->push_back((GEOSGeometry*)item);
> >>>> + geoms->push_back(*((int *)item));
> >>>> },
> >>>> &geoms);
> >>>>
> >>>> ensure_equals(geoms.size(), 1);
> >>>> - const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
> >>>> -
> >>>> - double x = -1;
> >>>> - double y = -1;
> >>>> - GEOSCoordSeq_getXY(seq, 0, &x, &y);
> >>>> - ensure_equals(x, 2.0);
> >>>> - ensure_equals(y, 3.0);
> >>>> + ensure_equals(geoms.at(0), 0);
> >>>>
> >>>>
> >>>> On Sat, 28 Nov 2020 at 20:55, Paul Ramsey <pramsey at cleverelephant.ca>
> wrote:
> >>>>
> >>>>
> >>>>> On Nov 28, 2020, at 8:11 AM, Joris Van den Bossche <
> jorisvandenbossche at gmail.com> wrote:
> >>>>>
> >>>>> Hi all,
> >>>>>
> >>>>> 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 https://github.com/pygeos/pygeos/runs/1465460418#step:9:86).
> Looking at the commits of the last days, this might be related to the
> SimpleSTRtree work?
> >>>>>
> >>>>> 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:
> >>>>>
> >>>>> Using released version of GEOS:
> >>>>>
> >>>>>>>> import pygeos
> >>>>>>>> pygeos.geos_version
> >>>>> (3, 8, 1)
> >>>>>>>> point = pygeos.Geometry("POINT (2 3)")
> >>>>>>>> tree = pygeos.STRtree([point])
> >>>>>>>> tree.query(pygeos.box(0, 0, 10, 10))
> >>>>> array([0])
> >>>>>
> >>>>> 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:
> >>>>>
> >>>>>>>> import pygeos
> >>>>>>>> pygeos.geos_version
> >>>>> (3, 9, 0)
> >>>>>>>> point = pygeos.Geometry("POINT (2 3)")
> >>>>>>>> tree = pygeos.STRtree([point])
> >>>>>>>> tree.query(pygeos.box(0, 0, 10, 10))
> >>>>> array([], dtype=int64)
> >>>>>
> >>>>> 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
> https://github.com/pygeos/pygeos/blob/master/src/strtree.c)
> >>>>
> >>>> 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.
> >>>>
> >>>> 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.
> >>>>
> >>>> 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.
> >>>>
> >>>>
> >>>> // querying tree with box
> >>>> template<>
> >>>> template<>
> >>>> void object::test<8>
> >>>> ()
> >>>> {
> >>>> GEOSSTRtree* tree = GEOSSTRtree_create(10);
> >>>> GEOSGeometry* g = GEOSGeomFromWKT("POINT (2 3)");
> >>>> GEOSSTRtree_insert(tree, g, g);
> >>>> GEOSGeometry* q = GEOSGeomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0
> 10, 0 0))");
> >>>>
> >>>> typedef std::vector<GEOSGeometry*> GList;
> >>>> GList geoms;
> >>>> ensure_equals(geoms.size(), 0);
> >>>> GEOSSTRtree_query(
> >>>> tree,
> >>>> q,
> >>>> [](void* item, void* userdata) {
> >>>> GList* geoms = (GList*)userdata;
> >>>> geoms->push_back((GEOSGeometry*)item);
> >>>> },
> >>>> &geoms);
> >>>>
> >>>> ensure_equals(geoms.size(), 1);
> >>>> const GEOSCoordSequence* seq = GEOSGeom_getCoordSeq(geoms[0]);
> >>>>
> >>>> double x = -1;
> >>>> double y = -1;
> >>>> GEOSCoordSeq_getXY(seq, 0, &x, &y);
> >>>> ensure_equals(x, 2.0);
> >>>> ensure_equals(y, 3.0);
> >>>>
> >>>> GEOSGeom_destroy(q);
> >>>> GEOSGeom_destroy(g);
> >>>> GEOSSTRtree_destroy(tree);
> >>>> }
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>>
> >>>>> Best,
> >>>>> Joris
> >>>>>
> >>>>>
> >>>>> On Wed, 25 Nov 2020 at 00:44, Paul Ramsey <pramsey at cleverelephant.ca>
> wrote:
> >>>>> Hey all, just truing up what's underway and nearly there...
> >>>>>
> >>>>> - Am I right that Z coordinates are nearly done? What's the status
> there?
> >>>>>
> >>>>> I've been trying to address some performance issues, with some
> success and some ... other things.
> >>>>>
> >>>>> 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.
> >>>>>
> >>>>> 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.
> >>>>>
> >>>>> 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).
> https://github.com/pramsey/geos/tree/monotone-chain-builder
> >>>>>
> >>>>> I've put that work to the side for now.
> >>>>>
> >>>>> 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.
> >>>>>
> >>>>> I think we're close, looking forward to release :)
> >>>>>
> >>>>> P
> >>>>> _______________________________________________
> >>>>> geos-devel mailing list
> >>>>> geos-devel at lists.osgeo.org
> >>>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
> >>>>> _______________________________________________
> >>>>> geos-devel mailing list
> >>>>> geos-devel at lists.osgeo.org
> >>>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
> >>>>
> >>>> _______________________________________________
> >>>> geos-devel mailing list
> >>>> geos-devel at lists.osgeo.org
> >>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
> >>>> _______________________________________________
> >>>> geos-devel mailing list
> >>>> geos-devel at lists.osgeo.org
> >>>> https://lists.osgeo.org/mailman/listinfo/geos-devel
> >>>
> >>> _______________________________________________
> >>> geos-devel mailing list
> >>> geos-devel at lists.osgeo.org
> >>> https://lists.osgeo.org/mailman/listinfo/geos-devel
> >>> _______________________________________________
> >>> geos-devel mailing list
> >>> geos-devel at lists.osgeo.org
> >>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20201129/38f1477b/attachment-0001.html>
More information about the geos-devel
mailing list