<div dir="ltr"><div>Hi</div><div><br></div>As far as I can see, there are some cases where your algorithm won't produce optimal solutions. E.g if you search for neighbours around origo, and there are lots points with coordinates like (1, 1, 1000), (1, 1000, 1), (1000, 1, 1), then your unions might fail include points like (5, 5, 5). Your result could be used as an upper bound for the distance where the optimal solution lies. By 3d-ordering all the points within a bounding box with side-lengths 2*(your upper bound) you should have a guaranteed optimal solution. The number of points within the bbox might (and should normally) be much more than the number of neighbours that you are searching for, so I'm not sure if I would recommend such a complicated approach out of performance considerations.<div>
<br></div><div>Speaking about performance, are you aware that your query probably doesn't make use of any spatial index? I think you would have to generate columns with 2d-versions of the_point in the xy, xz and yz-planes, and index each of those columns in order for the index to be used. This means that your current query would probably run about 3x slower than simply using st_3ddistance from the beginning.</div>
<div><br></div><div>My best attempt at an optimized 3d kNN-search would be something like:</div><div>1. Select all points within some reasonable bbox</div><div>2. If the number of points is k or more, then sort and return the first k points. Otherwise restart from 1 with an expanded bbox.</div>
<div><br></div><div>It could be possible to let the expansion of the bbox in step 2 depend on the number of points returned, but I would be careful not to have the algorithm repeat too many times.</div><div><br></div><div>
Hope this helps</div><div>Åsmund</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Jun 14, 2014 at 7:02 PM, hubert depesz lubaczewski <span dir="ltr"><<a href="mailto:depesz@gmail.com" target="_blank">depesz@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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>
<br>_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><br></blockquote></div><br></div>