On Sun, Jun 15, 2014 at 1:23 AM, Åsmund Tokheim <[email protected]> wrote:
> 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. > Sorry, but I fail to see such case - if point is close, it will be also close on at least one of 3 planes (x,y), (x,z), (y,z) Speaking about performance, are you aware that your query probably doesn't > make use of any spatial index? > It does. Tested. > 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. > As far as I was able to test, "select * from table order by st_3ddistance(geometry, '') limit 20" doesn't use index. > My best attempt at an optimized 3d kNN-search would be something like: > 1. Select all points within some reasonable bbox > 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. > 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. > We thought about it, but deciding what is reasonable box might be complicated. And in my approach, I'm merely getting 3x number of rows from 3 different indexes, and it was (in my tests) VERY fast. depesz
_______________________________________________ postgis-users mailing list [email protected] http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
