[postgis-devel] Re: Fixing r-tree semantics

[Mark Cave-Ayland]

Hi Tom,

> What needs more discussion is that it seems to me to make sense to extend
the standard 
> opclasses to handle the four Y-direction operators comparable to the
X-direction 
> operators that are already there, that is "above", "below", "overabove",
and 
> "overbelow".

As part of PostGIS (http://postgis.refractions.net), I submitted a patch a
while back to add additional Y-direction operators to the code which is a
slightly modified version of rtree_gist (and yes, the PostGIS implementation
will suffer from the same issues you've found with the existing R-tree
implementations).

The operators I went for were as follows:

	A &<| B - true if A's bounding box overlaps or is below B's bounding
box
	A |&> B - true if B's bounding box overlaps or is above B's bounding
box
	A <<| B - true if A's bounding box is strictly below B's bounding
box
	A |>> B - true if A's bounding box is strictly above B's bounding
box

Since the rtree_gist implementation and operators were 2D, my thoughts were
to use another op-class only if the indexing were upgraded to 3D. So with
this in mind, I created the following new GiST strategies:

	#define RTOverBelowStrategyNumber		9
	#define RTBelowStrategyNumber			10
	#define RTAboveStrategyNumber			11
	#define RTOverAboveStrategyNumber		12

This is basically what you are suggesting but with a | instead of a ^ in the
operator name (my original choice was to try and use } to indicate the
positive sense of the Y-axis but this was not accepted as a valid operator
character which is why I changed to |).

It would be harder for us to change these operators since they already
exist, but then again it would be useful from a maintenance point of view to
keep the strategy numbers and operators the same across both
implementations. Of course strategy numbers are just used internally so
these aren't such a big issue - it's more the choice of operators that would
be useful to agree on.


Kind regards,

Mark.

------------------------
WebBased Ltd
17 Research Way
Tamar Science Park
Plymouth
PL6 8BT 

T: +44 (0)1752 797131
F: +44 (0)1752 791023
W: http://www.webbased.co.uk