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