Geometry Boost List: [geometry] relate() interface

Subject: [geometry] relate() interface
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-03-07 10:59:09

Hi,

I'd like to share my thoughts about the relate() function and talk about 
the interface.

INTRODUCTION

relate() is a function which can calculate/check the spatial relation 
between two geometries WRT some intersection model (IM). The IM used by 
the OGC standard is DE9IM (http://en.wikipedia.org/wiki/DE-9IM). In 
addition to the DE9IM there are also older 9IM and 4IM which doesn't 
take into account the information about the dimensionality of the 
intersection. 4IM doesn't describe the exteriors of geometries. Note 
that in those simplified cases we can optimize a little bit.

The relate() input should be 2 geometries and a mask describing the IM 
matrix. So the most naiive version of could calculate the matrix and 
then compare it with the mask. This of course wouldn't be optimal. We 
should be able to pass the mask to the function and interrupt 
calculation at some point if available. Furthermore, it should be 
possible to pass a compile-time mask, this way the compiler would know 
that some things musn't be calculated (some functions are empty) and 
hopefully optimize getting rid of large parts of the code.

REQUIREMENTS

A set of "requirements" for relate() that I can imagine would be:
1. three purposes:
     a) the calculation of a matrix describing the spatial relation
     b) the check of a run-time mask
     c) the check of a compile-time mask
2. the support of various intersection models (not more descriptive than 
DE9IM):
     - DE9IM
     - 9IM
     - 4IM
     * DE4IM - 4IM with the info about the dimensionality
     * GENERIC - the elements of a matrix which should be handled and 
dimensionality support defined per element at compile-time, e.g. we'd 
like to calculate only the I^I and dim(B^I) or check 2x3 mask.
3. the support of logically connected masks
     - some number of masks logically connected with OR
     - maybe even mix of compile- and run-time masks

Of course we musn't support all of them and in all cases. E.g. I don't 
know how big would be the performance difference between all IMs. Maybe 
it's not worth the effort of the implementation.

INTERFACE

The most straightforward interface supporting all of the above 
requirements would look like this:

relate(geometry1, geometry2, result);

The result could be an object storing the resulting matrix, run-time or 
compile-time mask.

Or there could be 2 overloads:

Matrix result = relate<Matrix>(geometry1, geometry2);
bool relate(geometry1, geometry2, Mask(...));

Or the copy of the 3rd parameter could be returned (like predicates in 
STL algorithms):

Result result = relate(geometry1, geometry2, Result(...));

Or the Result could define a type return_type/result_type and always 
return it from member function result(). The relate() would then just 
use this concept:

Result result = relate(geometry1, geometry2, Result(...));
//or
std::string str = relate(geometry1, geometry2, Matrix());
bool ok = relate(geometry1, geometry2, Mask(...));

The last one would probably be the most flexible interface.

INTERFACE - RESULTING MATRIX

The types similar to the ones below could be used to define this kind of 
result:

matrix9de, matrix4de, matrix9, matrix4

and probably the generic one:

matrix<II, IB, IE, BI, BB, BE, EI, EB, EE> // generic type defining 
which components should be handled and how
// or
matrix< mpl::vector_c<...> >

To get the data from it we could use one of the following ways:

const char * raw_data = result.data(); // similar to C++11 
std::vector::data()
std::string res1 = result.str();
std::string res2( boost::begin(result), boost::end(result)); // use 
Boost.Range
char ii = get<interior, interior>(result); // hi-level interface
// and probably a lot more

The complete example could look like this:

matrix9de result;
relate(g1, g2, result);
std::cout << result.str();

or

std::cout << relate<matrix9de>(g1, g2).str();

or

std::cout << relate(g1, g2, matrix9de()).str();
std::cout << relate<matrix9de>(g1, g2).str(); // also possible - default 
ctor used by default

or

std::cout << relate(g1, g2, matrix9de());
std::cout << relate<matrix9de>(g1, g2);// also possible - default ctor 
used by default

INTERFACE - MASK

Similar to the above but it would take the mask (probably std::string 
const&) as the parameter:

mask9("T*F**F***")
mask4("T***")

The GENERIC version probably wouldn't be needed in this case. e.g.:

mask<true, true, false, true, true, false, false, false, false, 
false>('T','*',0,'*','*') // same result as mask4(...)

because the user most likely would like to use the fully-static mask 
instead (see below). But maybe not, I can imagine that it could be 
needed to check the 2x3 mask in run-time.

and the result would be always bool.

bool res = result.result();

or as just returned from relate()

bool ok = relate(g1, g2, mask4("T***"));

INTERFACE - STATIC_MASK

Same as above but the mask would be defined at compile-time:

static_mask<'T', '*', 'F', '*', '*', 'F', '*', '*', '*'>

There is no need to define any other class for this because we can check 
in compile-time which components should be calculated and if the 
dimensions should be taken into account. Furthermore we can analyse the 
dimensions for one component and not analyse for some other one.

INTERFACE - ORed MASKS

We could do it in the similar way how predicates are passed to the rtree:

bool ok = relate(g1, g2, mask4("FT**") || mask4("F*T*"));

or passed them in e.g. boost::tuple()

bool ok = relate(g1, g2, boost::make_tuple(mask4("FT**"), mask4("F*T*")));

So, what do you think? What version of the relate() do you like the 
best? Which elements would you like to see, which aren't needed and 
which are bad ideas?

Regards,
Adam