Re: [jts-dev] best way to find all points (indexed in an SRTtree) and a

[Martin Davis <mtnclimb@xxxxxxxxx>]

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-dev