I changed the code to use points, but order the items are returned is not understandable by me. I request the 5 NNs of the query point (0, 0), in a dataset of points (0, 0), (1, 1), .., (9, 9). The output I receive is this: knn query result: POINT(4 4) POINT(3 3) POINT(2 2) POINT(0 0) POINT(1 1) If you need the code, let me know. I remember that I read that the order is not specified, but does that mean that there is no logic in the results? I mean, clearly the 1st NN is (0, 0). Thanks for the reply, George On Mon, Apr 14, 2014 at 5:19 PM, Adam Wulkiewicz wrote:

Hi Georgios,

Georgios Samaras wrote:

...

I am running the code found here http://www.boost.org/doc/libs/1_54_0_beta1/libs/geometry/ doc/html/geometry/spatial_indexes/rtree_examples/quick_start.html

(not the intersect query, only the nn).

The output is this: " knn query point: POINT(0 0) knn query result: POLYGON((4 4,4 4.5,4.5 4.5,4.5 4,4 4)) - 4 POLYGON((3 3,3 3.5,3.5 3.5,3.5 3,3 3)) - 3 POLYGON((2 2,2 2.5,2.5 2.5,2.5 2,2 2)) - 2 POLYGON((0 0,0 0.5,0.5 0.5,0.5 0,0 0)) - 0 POLYGON((1 1,1 1.5,1.5 1.5,1.5 1,1 1)) - 1 "

What are the integers on the right? Indices of the polygons? Actually is not really clear to me what are we inserting in the tree..I tried finding some documentation on these methods, but I only found info on how to call them...

In the rtree we're storing values defined in the line:

typedef std::pair value;

so it's a pair of a Box and some number. This is the classic approach where in the spatial index you store AABB (Axis-Aligned Bounding Box) of some geometry and an ID of this geometry.

So why Polygons are printed when you're storing Boxes? Those lines are generated by this code:

std::cout << bg::wkt<box>(v.first) << " -" << v.second << std::endl;

First the Box is printed in WKT format, then " - " and the ID. But WKT standard (http://en.wikipedia.org/wiki/Well-known_text) doesn't define how Boxes should be described. Boost.Geometry uses WKT Polygons for this. That's just a text output.

What I want, is simply inserting some points in the tree and then search

...

for nn of a query point.

If you don't need any additional data, instead of std::pair just use point type from the same example.

Regards, Adam _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I do not have a big experience with NNs, but it seems a very very interesting problem to me! However, I thought that this would be the case (that you do not care about the order, maybe an argument for sorted results or not, would be nice). The query iterators worked as expected, but what is the difference? I mean, why the iterators return sorted results and the other method doesn't? Is the other method faster than iterators (in datasets with really many points or really high dimensions)? On Tue, Apr 15, 2014 at 12:38 PM, Adam Wulkiewicz

wrote:

Georgios Samaras wrote:

...

I changed the code to use points, but order the items are returned is not understandable by me.

I request the 5 NNs of the query point (0, 0), in a dataset of points (0, 0), (1, 1), .., (9, 9).

The output I receive is this: knn query result: POINT(4 4) POINT(3 3) POINT(2 2) POINT(0 0) POINT(1 1)

If you need the code, let me know. I remember that I read that the order is not specified, but does that mean that there is no logic in the results? I mean, clearly the 1st NN is (0, 0).

If the kNN query using query() function is performed, the order of returned Values isn't specified. The function returns 5 NNs, not sorted 5NNs. This way we save a call of sort() or sort_heap(). AFAIK the most typical use case would be to perform a kNN query and then to process all of those neighbours so it's not needed to sort them prematurely.

On the other hand in the case of query iterators ( http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/ geometry/spatial_indexes/queries.html#geometry.spatial_ indexes.queries.breaking_or_pausing_the_query ) you should get closer Values first.

Regards, Adam _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users