Geometry Boost List: Re: [geometry] Rtree changes

Subject: Re: [geometry] Rtree changes
From: Mats Taraldsvik (mats.taraldsvik_at_[hidden])
Date: 2013-02-20 06:51:02

Hi Adam,

> -----Opprinnelig melding-----
> Fra: Geometry [mailto:geometry-bounces_at_[hidden]] På vegne av 
> Adam Wulkiewicz
> Sendt: 18. februar 2013 18:16
> Til: Boost.Geometry library mailing list
> Emne: Re: [geometry] Rtree changes
> 
> Mateusz Loskot wrote:
> > On 18 February 2013 16:35, Mats Taraldsvik 
> > <mats.taraldsvik_at_[hidden]>
> wrote:
> >>
> >> - Will it be possible to use rtree queries on external (indexable) objects?
> >> For example, if I have a rtree-indexed boundary, and a set of 
> >> not-indexed objects, and want to check if the objects intersect 
> >> with my
> boundary.
> >> Essentially a kind of prepared query like the PreparedGeometry in GEOS.
> >
> > Assuming geos::geom:: types are adapted as boost::geometry models, 
> > I'd expect it should be possible. But, I'm also curious Adam's opinion here.
> 
> Spatial predicates which may be passed to the query may take arbitrary 
> Geometry type. To compile properly there must be an algorithm, e.g.
> geometry::intersects() which is able to calculate the result for 
> Indexable and Geometry. So for example it's possible to query for 
> Values intersecting MultiPolygon. If you store border segments in the 
> rtree e.g. as std::pair<SegmentBox, SegmentId> and define MultiPolygon 
> containing other geometries it should return intersected Values. Does 
> it meet your requirements?
> 
> Additionally, if new Geometries were added to the Boost.Geometry and 
> algorithms implemented for them the rtree should automatically work 
> for them.
> 
> For example, it should be possible to add some CompoundGeometry or 
> IndexedGeometry concept which stores some number of Geometries and a 
> SpatialIndex inside (or just the SpatialIndex) and implement 
> geometry::intersects(Box, CompoundGeometry) which uses this stored 
> internally SpatialIndex to calculate the result. And this should 
> automatically work in the rtree.
> 
> In the docs there are some basic examples of geometries for which 
> query may be performed:
> 
> https://svn.boost.org/svn/boost/sandbox-
> branches/geometry/index/doc/html/geometry_index/r_tree/queries.html
> 

Thanks for the thorough answer! :) It looks like this will at least make it easier to implement functionality similar to GEOS' PreparedGeometries. GEOS use "noding" algorithms (that use indexes) to pre-compute the PreparedGeometries. I haven't looked into how complicated these "noding" algorithms are to implement, however.

> Regards,
> Adam
> 

Regards,
Mats Taraldsvik
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry