| Re: [jts-dev] best way to find all points (indexed in an SRTtree) and a polygon. |
_______________________________________________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?
On Wed, Dec 4, 2019 at 9:34 PM Phil Scadden <P.Scadden@xxxxxxxxxx> wrote:
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.
From: jts-dev-bounces@xxxxxxxxxxx <jts-dev-bounces@xxxxxxxxxxx> on behalf of Martin Davis <mtnclimb@xxxxxxxxx>
Sent: Thursday, December 5, 2019 6:04:27 PM
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.
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.
On Wed, Dec 4, 2019 at 8:20 PM Phil Scadden <P.Scadden@xxxxxxxxxx> wrote:
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-devNotice: 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