[postgis-users] Will it work, or am I overlooking something?

[hubert depesz lubaczewski]

Hi,
I'm looking for a fast kNN search in 3d space.

For simplicity sake, let's say I have table:

create table test (
    id serial primary key,
    the_point geometry
)

the_point is always single point in 3d space: POINT(x y z).

kNN gist searches can use <-> operator, but this operator doesn't handle 3d
space.

So, I wrote 3 functions, which convert 3d point to 2d points by removing
one of dimensions:

translate_xy() -> returns POINT(x y)
translate_xz() -> returns POINT(x z)
translate_yz() -> returns POINT(y z)

Then, I create indexes (3) on translate_*( the_point ).

Then, when I need to find nearest neighbors (let's say - 10), I search
using all of above 3 indexes, union results (getting at most 3x number of
rows), reorder using st_3ddistance(), and limit to 10.

Basically the query is something along the lines of:

select * from test where id in (
    ( select id from test order by translate_xy( the_point ) <->
translate_xy( 'POINT(50 50 50)' ) limit 10 )
    union
    ( select id from test order by translate_xz( the_point ) <->
translate_xz( 'POINT(50 50 50)' ) limit 10 )
    union
    ( select id from test order by translate_yz( the_point ) <->
translate_yz( 'POINT(50 50 50)' ) limit 10 )
)
order by st_3ddistance(the_point, translate_yz( 'POINT(50 50 50)' )
limit 10;

Is that good enough, or am I overlooking some case where it can go wrong?

Regards,

depesz
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20140614/4d523e46/attachment.html>