R-tree spacial predicates (intersects(Ring) ...) in boost 1.59 upwards

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

R-tree spacial predicates (intersects(Ring) ...) in boost 1.59 upwards

sonic
Good day to everyone,

Tried the latest boost versions, however *rtree insersects query* does not accept ring, polygon and multipolygon any more - since 1.59 - when applied on boxes. However it is still present in the documentation (http://www.boost.org/doc/libs/1_60_0/libs/geometry/doc/html/geometry/spatial_indexes/queries.html#geometry.spatial_indexes.queries.spatial_predicates).

One could run a query on R-tree of boxes using a ring in boost 1.58.0 but not any longer. I could not find any relevant discussion but perhaps there is a good reason for this?

Example:
----------------------------------------------------------------
#include <vector>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/index/rtree.hpp>

void testSpacialIndexing()
{
namespace bg = boost::geometry;
namespace bgm = boost::geometry::model;
namespace bgi = boost::geometry::index;

typedef bgm::d2::point_xy<double> P;
typedef bgm::box<P> B;

P qpt;
B qbox;
bgm::ring<P> qring;
bgm::polygon<P> qpoly;
bgm::multi_polygon<bgm::polygon<P>> qmpoly;
bgm::segment<P> qseg;
bgm::linestring<P> qls;

// spacial indexing example
typedef std::pair<B, int> Value_t;
bgi::rtree<Value_t, bgi::quadratic<8>> rtree1;

std::vector<Value_t> found;

// works for all versions
rtree1.query(bgi::intersects(qpt), back_inserter(found));
rtree1.query(bgi::intersects(qbox), back_inserter(found));
rtree1.query(bgi::intersects(qseg), back_inserter(found));
rtree1.query(bgi::intersects(qls), back_inserter(found));
    
// does not work for 1.59 to 1.61 beta
rtree1.query(bgi::intersects(qring), back_inserter(found));
rtree1.query(bgi::intersects(qpoly), back_inserter(found));
rtree1.query(bgi::intersects(qmpoly), back_inserter(found));
}

----------------------------------------------------------------

Best greetings,
Mike






_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: R-tree spacial predicates (intersects(Ring) ...) in boost 1.59 upwards

Adam Wulkiewicz
Hi Mike,

Mike Vasiljevs wrote:

> Good day to everyone,
>
> Tried the latest boost versions, however *rtree insersects query* does
> not accept ring, polygon and multipolygon any more - since 1.59 - when
> applied on boxes. However it is still present in the documentation
> (http://www.boost.org/doc/libs/1_60_0/libs/geometry/doc/html/geometry/spatial_indexes/queries.html#geometry.spatial_indexes.queries.spatial_predicates).
>
> One could run a query on R-tree of boxes using a ring in boost 1.58.0
> but not any longer. I could not find any relevant discussion but
> perhaps there is a good reason for this?
>

Thanks for the info! No, this is a bug. Could you please report it here
(https://svn.boost.org/trac/boost/newticket)?

As a workaround, instead of using
bgm::d2::point_xy<double>
you could use
bgm::point<double, 2, bg::cs::cartesian>
unfortunately this is also true for user-defined Point types.

Have in mind that typically running a query passing complex Geometries
like Polygons is not advised. Typically one would perform a query using
only boxes (so envelopes of Polygons) to perform intersection tests with
nodes and values as fast as posible. Then perform intersection tests for
Geometries represented by boxes returned by the query and the original
Polygon.

Furthermore, currently a copy of geometry is kept inside a predicate
object, so potentially big Polygon can be copied. Though I susspect that
compiler could optimize it.

But indeed if areas of polygons and their envelopes differed greately
and many nodes/values could be pruned when Polygon was passed instead of
its evelope then the speed might be better. So in other words if
polygons was "big" but had small areas, had wierd shapes (thin arms)
and/or big/many holes. Do you have such use case or are you passing
Polygons into a query from a different reason? E.g. have you measured
that this approach is faster?

Regards,
Adam
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: R-tree spacial predicates (intersects(Ring) ...) in boost 1.59 upwards

sonic
Adam, many thanks for the answer!

On 11 May 2016, at 11:43, Adam Wulkiewicz <[hidden email]> wrote:


Thanks for the info! No, this is a bug. Could you please report it here (https://svn.boost.org/trac/boost/newticket)?
reported! https://svn.boost.org/trac/boost/ticket/12189



As a workaround, instead of using
bgm::d2::point_xy<double>
you could use
bgm::point<double, 2, bg::cs::cartesian>
unfortunately this is also true for user-defined Point types.
Indeed it does compile with with bgm::point<..,2,..>.



Have in mind that typically running a query passing complex Geometries like Polygons is not advised. Typically one would perform a query using only boxes (so envelopes of Polygons) to perform intersection tests with nodes and values as fast as posible. Then perform intersection tests for Geometries represented by boxes returned by the query and the original Polygon.
Indeed I am doing now exactly this!



Furthermore, currently a copy of geometry is kept inside a predicate object, so potentially big Polygon can be copied. Though I susspect that compiler could optimize it.
Good point.


But indeed if areas of polygons and their envelopes differed greately and many nodes/values could be pruned when Polygon was passed instead of its evelope then the speed might be better. So in other words if polygons was "big" but had small areas, had wierd shapes (thin arms) and/or big/many holes. Do you have such use case or are you passing Polygons into a query from a different reason? E.g. have you measured that this approach is faster?
Good point too. In my case no holes (rings) and probably very few thin arms, if any. Though I will create more test cases do a few performance tests at some point.


Best regards,
Mike


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: R-tree spacial predicates (intersects(Ring) ...) in boost 1.59 upwards

Adam Wulkiewicz
Mike Vasiljevs wrote:
Adam, many thanks for the answer!

On 11 May 2016, at 11:43, Adam Wulkiewicz <[hidden email]> wrote:


Thanks for the info! No, this is a bug. Could you please report it here (https://svn.boost.org/trac/boost/newticket)?
reported! https://svn.boost.org/trac/boost/ticket/12189


FYI, fix is prepared: https://github.com/boostorg/geometry/pull/351

Regards,
Adam
 

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry