[postgis-users] Is my query planner failing me, or vice versa?

[strk at refractions.net]

On Tue, Dec 13, 2005 at 05:35:39PM -0800, Martin Davis wrote:
> > Martin, postgis worst case for Distance is O(nm), what should 
> > we expect from JTS ?
> 
> In JTS distance uses essentially the same algorithm as PostGIS, so it's
> O(nm).  I think you can do better than this with some fancy algorithms,
> but I haven't implemented those ideas yet.
> 
> It's worth noting that what is really being asked is whether
> g.isWithinDistance(h, 5000) = true.  IsWithinDistance allows even more
> optimization than distance - but unfortunately JTS doesn't implement
> those optimizations yet (apart from a simple bounding box check).
> 
> The convex hull idea is a good one.  By the way, I've been doing some
> work on the JTS convex hull routines recently, and made a huge speedup
> over the old one.  Strk, might be work taking a look at that code to see
> about porting it to GEOS.  Shouldn't be too hard to do - the algorithm
> is basically the same, it's just more carefully implemented.

Thanks for the info, I will after GEOS-3.0.0 is out (which will
follow PostGIS-1.1.0).
All performance improvements await for interface stabilization.

--strk;