Skip to main content
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [List Home]
Re: [jts-dev] best way to find all points (indexed in an SRTtree) and a polygon.
  • From: Phil Scadden <P.Scadden@xxxxxxxxxx>
  • Date: Fri, 6 Dec 2019 20:41:54 +0000
  • Accept-language: en-US
  • Arc-authentication-results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=gns.cri.nz; dmarc=pass action=none header.from=gns.cri.nz; dkim=pass header.d=gns.cri.nz; arc=none
  • Arc-message-signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=7j7ZED/E/XMDiq6tcOO5K3qMEOtxR18+1qsqgRgENoM=; b=iBYiNIc3cv0kwrRcSAC6DBqGC2g74ugmYB+tfEEfDB1WIhbFfVc97RH/9YtoHANtY8YieR8X/Fp4z0o3FlXSTjnxzlwUEsH7uol4j3afW+sV9YKNmT7tn/BFmsvmAnWOFs/HfQ4HAgHXUT7MGFQ0aviePYc720uGNoPyiaShPQ9rLMe8JX+p3JpaBIZ84/QHK+/bRq8bBztooG0kzLclJeGHeskIcqLKpd+3M1xxkNeOH6vPqfQoaMKraT4HxC7xWFKv6S7ubDx1XZWnYy0TShqOJpJ01twKqyCNl0xCZuiwPyhN61TE41WD/k8Xib7AzlmdnrJ3EH/DiNzLo934pg==
  • Arc-seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=KOsP+2MhuOs1vf1gAv3dVtXbaWa2yd/p3KanNhnz9FhmXe7i42O2TfRgvVs3Hye4uJkEHMs/beJsXoztA9BAmmTProO7wGSxsR82++9AtQvPPSlmK9ZJoYkxMMhAhYg8YJdrrurGQm5ldy/6C3h+qApfdg/IzDwxD3ea1BOayKaGNbRxZzDMja+ux89947EFANpBKTpE9ELIfVjrJLxwSsmuJ6onuW2lH6GdFRWNnNjp6kj3Kr6CNtPZYKD0lwItjGuyPnr3uOLBxiOFd68eisxhnpmyQKiLh5KUNRh0uTaWNSJffZP0MJdIC7EmjSVJX+YAHZnOJPbf1A7RQjyY4g==
  • Delivered-to: jts-dev@xxxxxxxxxxx
  • List-archive: <https://dev.eclipse.org/mailman/private/jts-dev>
  • List-help: <mailto:jts-dev-request@eclipse.org?subject=help>
  • List-subscribe: <https://dev.eclipse.org/mailman/listinfo/jts-dev>, <mailto:jts-dev-request@eclipse.org?subject=subscribe>
  • List-unsubscribe: <https://dev.eclipse.org/mailman/options/jts-dev>, <mailto:jts-dev-request@eclipse.org?subject=unsubscribe>
  • Thread-index: AdWrIan9NR6W7lilQQCXrQPrbupfuwAB83aAAADzuQAAGBSsgAAGbeLQAAXmyIAAJGGGgAAJMoyg
  • Thread-topic: [jts-dev] best way to find all points (indexed in an SRTtree) and a polygon.

Now that is really good to know. I will use STRtree for static indices. Later in the same process I have be also using kdtree (on the z data) to facilitate gridding. This is all about fast nearest neighbour search and having a fast in-memory build time. From what I read, kdtree is the one to use.

Thanks very much for that.

 

From: jts-dev-bounces@xxxxxxxxxxx <jts-dev-bounces@xxxxxxxxxxx> On Behalf Of Martin Davis
Sent: Saturday, 7 December 2019 05:16
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.

 

I did some performance testing of STRtree, KdTree and HPRtree, running on a dataset of 1 M points.  I was a bit surprised by the results, which seem to show that KdTree is a bit *slower* than the other indexes in query time (by ~20%).  STRtree and HPRtree had similar query times.  HPRtree had a slower build time, which was also a bit surprising.  

 

Overall, STRtree was the performance winner.   There may still be better choices if memory is the biggest concern, but it's nice to know that STRtree is holding up as the best JTS index to use.  

 

On Thu, Dec 5, 2019 at 2:54 PM Martin Davis <mtnclimb@xxxxxxxxx> wrote:

 

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.  

 

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.

Back to the top