<div dir="ltr"><div><div><div><div><div><div><div><div>Hi,<br>I'm looking for a fast kNN search in 3d space.<br><br></div>For simplicity sake, let's say I have table: <br><br>create table test (<br></div>    id serial primary key,<br>
</div>    the_point geometry<br>)<br><br></div>the_point is always single point in 3d space: POINT(x y z).<br><br></div>kNN gist searches can use <-> operator, but this operator doesn't handle 3d space.<br><br></div>
So, I wrote 3 functions, which convert 3d point to 2d points by removing one of dimensions:<br><br>translate_xy() -> returns POINT(x y)<br>translate_xz() -> returns POINT(x z)<br>translate_yz() -> returns POINT(y z)<br>
<br></div>Then, I create indexes (3) on translate_*( the_point ).<br><br>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.<br>
<br>Basically the query is something along the lines of:<br><br>select * from test where id in (<br></div><div>    ( select id from test order by translate_xy( the_point ) <-> translate_xy( 'POINT(50 50 50)' ) limit 10 )<br>
</div><div>    union<br><div>    ( select id from test order by translate_xz( the_point ) <-> translate_xz( 'POINT(50 50 50)' ) limit 10 )<br></div>    union<br><div>    ( select id from test order by translate_yz( the_point ) <-> translate_yz( 'POINT(50 50 50)' ) limit 10 )<br>
</div>)<br></div><div>order by st_3ddistance(the_point, translate_yz( 'POINT(50 50 50)' )<br></div><div>limit 10;<br><br></div><div>Is that good enough, or am I overlooking some case where it can go wrong?<br><br>
</div>Regards,<br><br>depesz<br></div>