Geometry Boost List: Re: [geometry] Index distance predicates names

Subject: Re: [geometry] Index distance predicates names
From: Barend Gehrels (barend_at_[hidden])
Date: 2012-08-27 16:59:10

Hi Adam,

Thanks for your efforts.

I'm afraid I can't follow all details:

On 26-8-2012 22:56, Adam Wulkiewicz wrote:
> Hi,
>
> I'm testing the r-tree implementation and have problem with some 
> names. I've been using near() and far() but these are macros defined 
> in windows.h. Since the r-tree isn't released yet, the simplest way of 
> fixing it is to change names. But first, I'll explain what are those 
> predicates.

Agree, near/far should then be avoided.

>
> R-tree allows to store volumetric values (boxes) and find some number 
> of them nearest to some point. It is possible to define which point of 
> volumetric object is taken in distance calculation. It may be the 
> nearest point, the centroid or the furthest point. This corresponds to 
> functions bgi::near(), bgi::centroid() and bgi::far().

Nice functionality, yes, this makes sense if you measure two polygons to 
a reference point (how does it work? calculate the furthest point on a 
polygon from a reference point, is that also indexed? done on the fly?).

I find the name "centroid" not so intuitive in this context. You mean 
here: "with_respect_to_its_centroid", or "relative_to_its_centroid". 
Maybe "centroid_relative"? or "furthest_point_measured"? or simply "to", 
so "to_nearest"?

>
> bgi stands for boost::geometry::index namespace.
>
> To complicate things. There is also a method rtree.nearest(Predicate) 
> and function bgi::nearest(rtree, Predicate). 

Are they both meant to be called by the library user? Within geometry, 
we normally use no methods on objects to be able to adapt other things. 
Maybe that rationale is not applicable to rtree, but are these methods 
synonyms?

> So knn query may look like this:
>
> tree.nearest(bgi::near(pt), output);
> bgi::nearest(tree, bgi::near(pt), output);
> tree | bgi::filters::nearest_filtered(bgi::near(pt))
>
> or this:
>
> bgi::nearest(
>   tree,
>   bgi::bounded(
>     bgi::near(pt),
>     bgi::centroid(10),
>     bgi::far(20)
>   ), output);

I'm failing to see what this exactly means. What is 10 doing in 
centroid, and 20 in far. Are those max. distances to the mentioned 
point? Or the 10 occurrences w.r.t. their centroids? I must admit I did 
not look up the docs.

If we have a suffix, e.g. "_relative", the user is probably less 
confused about its meaning.

>
> Some names may form non-intuitive query, e.g.:
>
> bgi::nearest(tree, bgi::nearest(pt), output);

So this means: the closest geometries to "pt", where from each geometry 
the point closest to "pt" is measured.

>
> What is more, I'd rather avoid furthest() because it is nice antonym 
> of nearest() and may be used as similar function name.
>
> To the point. Possible names are:
>
> near -> nearest, close, closest
> far -> furthest, distant, most_distant
>
> Do you have any preferences or other ideas? 

Nearest is commonly used in "nearest neighbor"
Oracle uses "sdo_nn" but without sdo this is probably too much an 
abbrevation

I think the most distant points are normally termed "farthest", see e.g. 
http://dl.acm.org/citation.cfm?id=142740

but furthest is also widely used.

Regards, Barend