At moment, I am ignoring secondary filter – primary results for distance from the envelope segment are “good enough for a government job”. I will look at the kdtree serialization. A packed Kdtree
would be beyond my resources at moment. Sadly, no publications. Because JTS use is so deep in the engine room, that level of detail doesn’t surface in any the published science. Sometimes in internal reports/ workflow guides but not much help. Ditto for commercial
contract reports.
From: jts-dev-bounces@xxxxxxxxxxx <jts-dev-bounces@xxxxxxxxxxx>
On Behalf Of Martin Davis
Sent: Friday, 6 December 2019 11:54
To: JTS project developer mailing list <jts-dev@xxxxxxxxxxx>
Subject: Re: [jts-dev] best way to find all points (indexed in an SRTtree) and a polygon.
Your KdTree code should work identically for STRtree. Followed by secondary filter using either PreparedGeometry, or more directly IndexedPointInAreaLocator. With deduplication required, but it sounds like you are doing that already.
There's no particular issue with making KdTree serializable that I'm aware of - just never got around to it and nobody pushed for it. It would be great if you can try that out. I"m happy to commit the code once it works, or you can make
a PR if you're able to.
This is right in the KdTree sweet spot, so I would expect it to be more performant than STRtree. A report on performance would be interesting to hear if you try them both out. Also, the KdTree might be more memory efficient.
It also occurs to me that for a static query like this, there's a potential for a more efficient Packed KdTree implementation, where all points are provided at the outset, and the tree is build by repeated sorting and partioning. This
should support an array-based implementation which would be a LOT more memory efficient (i.e. like the recenltly-commited HPRtree code. I'd suggest trying the HPRtree, but it's not (yet) serializable, and I'm not sure it's faster than the STRtree for points).
Thanks for the info about the application. Always interesting to hear about different problem domains which JTS is being used for. One of these days it would be really nice to collect some of these into a gallery... Are there any publications
in this area which reference the use of JTS?
That approach is actually what I am doing with a kdtree.
for (int i=1; i<NO_OF_SEGMENTS; i++) {
Coordinate p = LinearLocation.pointAlongSegmentByFraction(coordinates[0],coordinates[1], i*1.0/NO_OF_SEGMENTS);
Envelope search = new Envelope(lastp,p);
search.expandBy(maxD,maxD);
List<KdNode> npts = index.query(search);
for (KdNode kpt:npts) {
SpatialIndexPoint pt = (SpatialIndexPoint) kpt.getData();
if (pts.indexOf(pt)<0) pts.add(pt);
}
lastp = p;
}
Was going to change to SRTree as application will benefit from storing the index on disc as point no.s increase. I could look at serializing kdtree but I suspect it would have been
done already if it was easy. “All points in a polygon” seemed like a common application so I started looking an alternative approach by buffering a line.
The application is airborne geophysics, in this case TEM for mapping aquifers but many similar setups. The data inversions are done at about 10m intervals along the flight lines
with about 200m between lines. Each point will have as associated set of vertical measurements down to around 300m, but this vertical set is irrelevant to the problem. The full dataset will be many million points covering the region of survey. Users would
expect to be able to draw an arbitrary line on a map and view a section constructed from data points “close” to the line. Detailed investigation would draw lines of 100m to a few kilometres but regional overviews spanning 10s of kilometres are reasonable
too. I am anticipating doing binning to create multiresolution datasets since really require the spatial index to fit easily in memory. It would also result in more representative data being used for large scale portrayal. Buffer distance is work-in-progress
but less than 200m.
In terms of generalized presentation within JTS, then IndexedPointsInPolygon seems obvious. I do this all day long in numerous applications though many of those are against a spatial
database. Would probably have handed over my firstborn for application in DGGS (https://www.opengeospatial.org/pressroom/pressreleases/2656) so I didn’t have to worry
about the antemeridian and poles within the polygon, but in meantime, JTS is doing a lot of heavy lifting for me.
From:
jts-dev-bounces@xxxxxxxxxxx <jts-dev-bounces@xxxxxxxxxxx>
On Behalf Of Martin Davis
Sent: Friday, 6 December 2019 06:01
To: JTS project developer mailing list <jts-dev@xxxxxxxxxxx>
Subject: Re: [jts-dev] best way to find all points (indexed in an SRTtree) and a polygon.
Chopping the lines into sections seems like a good approach.
If the query is truly for a buffer of that line, you can query simply using the envelope of the section expanded by the buffer distance. And then just test IsWithinDistance rather
than computing the actual buffer.
You will have to deal with duplicate points returned when query envelopes overlap.
I'm thinking there should be a more clever solution to this, using the same approach used by IndexedFacetDistance. That is, create an STRtree of the points, and one of the segments
of the line. Then mutually recurse through the trees, discarding any node pairs which cannot contain any items closer than the buffer distance. This is effectively the same as doing repeated queries to the point tree by the line segment buffer envelopes,
but should be faster and won't return duplicates. The IndexedFacetDistance code is slightly different, because it is finding the closest pari. But it should be possible to modify this so that is accepts a distance tolerance (i.e. for withinDistance), and
also so it finds all candidate pairs. That's an interesting application - I will think about how to provide this as a standard feature.
Out of interest, what are the dimensions of the geometries involved? I.e. # of points, and extent of points compared to length of line and buffer distance? And what's the real-world
domain, if you are able to say?
Thanks for that. I will try segmenting (since the polygon is more or less a thin rectangle). I would like to use kdtree
but need to serialize.
The spatial indexes in JTS generally only support range rectangle queries. So there's no way to get any more out of the index than by querying using the envelope of the polygon
(a so-called "primary filter"). The secondary filter tests whether the retrieved points actually lie in the query polygon. That can be done most efficiently by using a PreparedGeometry and its intersects() method.
You might also consider using the KdTree class - it should be faster for indexing points.
I have a rather large no. of points which I have indexed as an SRTree. I want to find list of all of points which lie inside a polygon (which is derived by buffering a line). An envelope query on the tree would obviously reduce the no. of points to check
well for an EW or NS line, but what would be the best way to exploit the index for a diagonal line?
Notice: This email and any attachments are confidential and may not be used, published or redistributed without the
prior written consent of the Institute of Geological and Nuclear Sciences Limited (GNS Science). If received in error please destroy and immediately notify GNS Science. Do not copy or disclose the contents.
_______________________________________________
jts-dev mailing list
jts-dev@xxxxxxxxxxx
To change your delivery options, retrieve your password, or unsubscribe from this list, visit
https://dev.eclipse.org/mailman/listinfo/jts-dev
Notice: This email and any attachments are confidential and may not be used, published or redistributed without the prior written consent of the Institute of Geological and
Nuclear Sciences Limited (GNS Science). If received in error please destroy and immediately notify GNS Science. Do not copy or disclose the contents.
_______________________________________________
jts-dev mailing list
jts-dev@xxxxxxxxxxx
To change your delivery options, retrieve your password, or unsubscribe from this list, visit
https://dev.eclipse.org/mailman/listinfo/jts-dev
Notice: This email and any attachments are confidential and may not be used, published or redistributed without the prior written consent of the Institute of Geological and Nuclear Sciences Limited (GNS Science). If received in error please destroy and immediately
notify GNS Science. Do not copy or disclose the contents.
|
