rtree ?

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

rtree ?

Aleksandar Babic
Hi all,

Any pointers on the rtree within Boost.Geometry? (how to use it, some
examples, querying .... etc).

Regards
Aleksandar

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

Re: rtree ?

Mateusz Loskot
Administrator
On 20 October 2011 14:29, Aleksandar Babic <[hidden email]> wrote:
> Hi all,
>
> Any pointers on the rtree within Boost.Geometry? (how to use it, some
> examples, querying .... etc).

Check Adam's reply to my post:

http://lists.osgeo.org/pipermail/ggl/2011-October/001549.html

Best regards,
--
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
Member of ACCU, http://accu.org
_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
--
Mateusz Loskot
http://mateusz.loskot.net
Reply | Threaded
Open this post in threaded view
|

Re: rtree ?

Aleksandar Babic
Hei,

Thanks for the tip.
BTW. Do you (or anyone) know what is under
https://svn.boost.org/svn/boost/sandbox-branches/geometry/index_dyn.

Many thanks,
Aleksandar

On Thu, 2011-10-20 at 14:36 +0100, Mateusz Łoskot wrote:

> On 20 October 2011 14:29, Aleksandar Babic <[hidden email]> wrote:
> > Hi all,
> >
> > Any pointers on the rtree within Boost.Geometry? (how to use it, some
> > examples, querying .... etc).
>
> Check Adam's reply to my post:
>
> http://lists.osgeo.org/pipermail/ggl/2011-October/001549.html
>
> Best regards,


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

Re: rtree ?

Adam Wulkiewicz
Aleksandar Babic wrote:
> Hei,
>
> Thanks for the tip.
> BTW. Do you (or anyone) know what is under
> https://svn.boost.org/svn/boost/sandbox-branches/geometry/index_dyn.
>
> Many thanks,
> Aleksandar
>

Hi,

It is previous, outdated version of the rtree with min and max numbers
of nodes' children passed as run-time parameters instead of compile-time
template parameters. I've switched to static-size arrays instead of
dynamic-size vectors in nodes at some point but leave the old version.

Regards,
Adam

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

Re: rtree ?

Mateusz Loskot
Administrator
On 20 October 2011 17:02, Adam Wulkiewicz <[hidden email]> wrote:

> Aleksandar Babic wrote:
>> Thanks for the tip.
>> BTW. Do you (or anyone) know what is under
>> https://svn.boost.org/svn/boost/sandbox-branches/geometry/index_dyn.
>>
>
> It is previous, outdated version of the rtree with min and max numbers of
> nodes' children passed as run-time parameters instead of compile-time
> template parameters. I've switched to static-size arrays instead of
> dynamic-size vectors in nodes at some point but leave the old version.

Perhaps you could remove it or add README file with pointer to new version,
to not to confuse people :-)

Best regards,
--
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
Member of ACCU, http://accu.org
_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
--
Mateusz Loskot
http://mateusz.loskot.net
Reply | Threaded
Open this post in threaded view
|

Re: rtree ?

Aleksandar Babic
And some more comments would not hurt as well (pls don't think that I'm ungratefull).

Aleksandar

----- Original Message -----
Fra: "Mateusz Łoskot" <[hidden email]>
Til: "Generic Geometry Library Discussion" <[hidden email]>
Sendt: 20. oktober 2011 23:14:49
Emne: Re: [ggl] rtree ?

On 20 October 2011 17:02, Adam Wulkiewicz <[hidden email]> wrote:

> Aleksandar Babic wrote:
>> Thanks for the tip.
>> BTW. Do you (or anyone) know what is under
>> https://svn.boost.org/svn/boost/sandbox-branches/geometry/index_dyn.
>>
>
> It is previous, outdated version of the rtree with min and max numbers of
> nodes' children passed as run-time parameters instead of compile-time
> template parameters. I've switched to static-size arrays instead of
> dynamic-size vectors in nodes at some point but leave the old version.

Perhaps you could remove it or add README file with pointer to new version,
to not to confuse people :-)

Best regards,
--
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
Member of ACCU, http://accu.org
_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
Reply | Threaded
Open this post in threaded view
|

Re: rtree ?

Adam Wulkiewicz
In reply to this post by Mateusz Loskot
Mateusz Łoskot wrote:
> Perhaps you could remove it or add README file with pointer to new version,
> to not to confuse people :-)

Removed.

Regards,
Adam

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

Re: rtree ?

Adam Wulkiewicz
In reply to this post by Aleksandar Babic
Aleksandar Babic wrote:
> And some more comments would not hurt as well (pls don't think that I'm ungratefull).

Of course, I'm planning to do it. But first, I'd like to hear from you
all, do you like the interface? Maby something should be added or changed?

Regards,
Adam

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

Re: rtree ?

Mateusz Loskot
Administrator
On 21 October 2011 20:06, Adam Wulkiewicz <[hidden email]> wrote:
> Aleksandar Babic wrote:
>>
>> And some more comments would not hurt as well (pls don't think that I'm
>> ungratefull).
>
> Of course, I'm planning to do it. But first, I'd like to hear from you all,
> do you like the interface? Maby something should be added or changed?

I admit I haven't checked it yet.
I'll do my best to do it and post comments over this weekend.

Best regards,
--
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org
Member of ACCU, http://accu.org
_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
--
Mateusz Loskot
http://mateusz.loskot.net
Reply | Threaded
Open this post in threaded view
|

Re: rtree ?

Bernhard
In reply to this post by Adam Wulkiewicz
Adam Wulkiewicz wrote
Of course, I'm planning to do it. But first, I'd like to hear from you
all, do you like the interface? Maby something should be added or changed?
Hi Adam,

I have to admit I don't fully understand your interface. The only example I could find is the additional_sizes_and_times.cpp in the tests directory.
The rtree class provides one query method, which has a Predicates type as the first parameter. In additional... some predicates are used and I understand that. However, there is also query(intersects(B)) searching time test, which has a box as the first parameter. I don't understand why it compiles (how is Box a predicate?) and what it does - although I admit it is more of a curiosity question as I think I can achieve what I want with the given predicates.

I have one other question. Is it possible to iterate over every item in the rtree (without knowing their position, i.e. giving an appropriately large bounding box)? Unfortunately I need to do that in the project I'm working on.

Thanks & regards,
Bernhard
Reply | Threaded
Open this post in threaded view
|

Re: rtree ?

Bernhard
Adam Wulkiewicz wrote
Of course, I'm planning to do it. But first, I'd like to hear from you
all, do you like the interface? Maby something should be added or changed?
I have now noticed a strange effect: If I base my box geometries on model::point<double, 2, cartesian> everything works. However, if I use model::d2::point_xy<double, cartesian>, I get a series of compilation errors. It took me quite a time to figure this out, as I had thought those to be equivalent (other than the convenience functions) and used the latter, and with everything except the rtree they work indiscriminately.

Regards,
Bernhard

Reply | Threaded
Open this post in threaded view
|

Re: rtree ?

Adam Wulkiewicz
Bernhard wrote:

>
> Adam Wulkiewicz wrote
>>
>> Of course, I'm planning to do it. But first, I'd like to hear from you
>> all, do you like the interface? Maby something should be added or changed?
>>
>
> I have now noticed a strange effect: If I base my box geometries on
> model::point<double, 2, cartesian>  everything works. However, if I use
> model::d2::point_xy<double, cartesian>, I get a series of compilation
> errors. It took me quite a time to figure this out, as I had thought those
> to be equivalent (other than the convenience functions) and used the latter,
> and with everything except the rtree they work indiscriminately.

Hi,

Yes, I remember this issue. I've reported this earlier. If I use
point_xy instead of point as a base point type there is an compilation
error in geometry\algorithms\convert.hpp:

'boost::mpl::assertion_failed' : cannot convert parameter 1 from
'boost::mpl::failed ************(__thiscall
boost::geometry::dispatch::convert<UseAssignment,Tag1,Tag2,DimensionCount,Geometry1,Geometry2>::NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPES::*
***********)(boost::mpl::assert_::types<T1,T2>)' to
'boost::mpl::assert<false>::type'
D:\lib\boost_geometry\boost\geometry\algorithms\convert.hpp 226

Is this what you have in mind?

Inside rtree I use geometry::point as my basic point because user may
use whatever he/she wants. But conversion from
geometry::box< geometry::point<...> > to
geometry::box< geometry::point_xy<...> >
is not implemented in geometry::convert().

Please just use geometry::point for now.

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

Re: rtree ?

Adam Wulkiewicz
In reply to this post by Bernhard
Bernhard wrote:

>
> Adam Wulkiewicz wrote
>>
>> Of course, I'm planning to do it. But first, I'd like to hear from you
>> all, do you like the interface? Maby something should be added or changed?
>>
>
> Hi Adam,
>
> I have to admit I don't fully understand your interface. The only example I
> could find is the additional_sizes_and_times.cpp in the tests directory.
> The rtree class provides one query method, which has a Predicates type as
> the first parameter. In additional... some predicates are used and I
> understand that. However, there is also query(intersects(B)) searching time
> test, which has a box as the first parameter. I don't understand why it
> compiles (how is Box a predicate?) and what it does - although I admit it is
> more of a curiosity question as I think I can achieve what I want with the
> given predicates.

Box is a default case and it works just like intersects(Box).

index::intersects(Box) is a function generating object of type
index::detail::intersects<Box>. Internally there is
predicate_check<Predicate, ...>::apply(Predicate const& p, ...) checking
if some value should be returned by the query. Default predicate_check
as well as specialized for index::detail::intersects<Box>, both calls
geometry::intersects(Box, ...).

Other predicates:

intersects, disjoint, covered_by, overlaps, within

In addition you may pass negated predicates. As well as some number of
predicates:

std::make_pair(intersects(B1), !within(B2))

It works for boost::tuple too.

And there is value(some_fun) predicate where you may pass
function/functor some_fun. It must take one parameter of type Value and
return bool. True if current value should be returned.

> I have one other question. Is it possible to iterate over every item in the
> rtree (without knowing their position, i.e. giving an appropriately large
> bounding box)? Unfortunately I need to do that in the project I'm working
> on.

There is no iterator in the rtree and it possibly won't be any. You may
return all of the elements which are in rtree's Box, but this query will
traverse all nodes and copy all elements to some container, which is ok
if you do it rarely.

Some other possibilities:

1. You may store 2 copies of objects. One in rtree, second in some other
container.

2. You may e.g. store your objects in std::vector and std::pair<Box,
Index> in the rtree. Assuming you won't be erasing some random objects
to not mess with indexes.

3. Another possibility is to use vector to store objects, pass indexes
as Values in the rtree and
index::translator::index<std::vector<MyObject> > as rtree's Translator:

using namespace boost::geometry::index;

typedef translator::index< std::vector<MyObject> > MyTranslator;

rtree<
   size_t,
   bgi::quadratic<32, 8>,
   MyTranslator>
 > r(MyTranslator(my_vector));

4. You may store objects in some container which preserves iterators and
use pointers/iterators as rtree's Values.

It all depends on what do you want to do with your objects and how often.

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

Re: rtree ?

Barend
In reply to this post by Adam Wulkiewicz
Hi,

On 26-11-2011 23:34, Adam Wulkiewicz wrote:

> Bernhard wrote:
>>
>> Adam Wulkiewicz wrote
>>>
>>> Of course, I'm planning to do it. But first, I'd like to hear from you
>>> all, do you like the interface? Maby something should be added or
>>> changed?
>>>
>>
>> I have now noticed a strange effect: If I base my box geometries on
>> model::point<double, 2, cartesian>  everything works. However, if I use
>> model::d2::point_xy<double, cartesian>, I get a series of compilation
>> errors. It took me quite a time to figure this out, as I had thought
>> those
>> to be equivalent (other than the convenience functions) and used the
>> latter,
>> and with everything except the rtree they work indiscriminately.
>
> Hi,
>
> Yes, I remember this issue. I've reported this earlier. If I use
> point_xy instead of point as a base point type there is an compilation
> error in geometry\algorithms\convert.hpp:
>
> 'boost::mpl::assertion_failed' : cannot convert parameter 1 from
> 'boost::mpl::failed ************(__thiscall
> boost::geometry::dispatch::convert<UseAssignment,Tag1,Tag2,DimensionCount,Geometry1,Geometry2>::NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPES::*
> ***********)(boost::mpl::assert_::types<T1,T2>)' to
> 'boost::mpl::assert<false>::type'
> D:\lib\boost_geometry\boost\geometry\algorithms\convert.hpp    226

Ah, was that the problem. You reporterd earlier that point_xy was not
working in index for area, but not that this was the reason. Thanks for
this new report and with this it is fixed now.

Besides this I also updated/extended the linestring/polygon intersection
(which is working for intersection and difference now, in all cases that
I tested. Will do some more test next week.)

Regards, Barend


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

Re: rtree ?

Adam Wulkiewicz
Barend Gehrels wrote:
>
> Ah, was that the problem. You reporterd earlier that point_xy was not
> working in index for area, but not that this was the reason. Thanks for this
> new report and with this it is fixed now.
>
> Besides this I also updated/extended the linestring/polygon intersection
> (which is working for intersection and difference now, in all cases that I
> tested. Will do some more test next week.)
>

Ok, thanks.

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

Re: rtree ?

Adam Wulkiewicz
Adam Wulkiewicz wrote:

> Barend Gehrels wrote:
>>
>> Ah, was that the problem. You reporterd earlier that point_xy was not
>> working in index for area, but not that this was the reason. Thanks for this
>> new report and with this it is fixed now.
>>
>> Besides this I also updated/extended the linestring/polygon intersection
>> (which is working for intersection and difference now, in all cases that I
>> tested. Will do some more test next week.)
>>
>
> Ok, thanks.

Btw, I've added some basic version of BoostBook doc with generated html.

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

Re: rtree ?

Adam Wulkiewicz
> Btw, I've added some basic version of BoostBook doc with generated html.

Ok, I've improved it and added nearest neighbor query description. I
should have done it earlier. Feel free to report errors, ambiguities
etc. I hope that using of the rtree will be simpler task now.

I still wait for your opinion Mateusz ;)

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

Re: rtree ?

Barend
In reply to this post by Adam Wulkiewicz
Hi Adam,

On 28-11-2011 5:19, Adam Wulkiewicz wrote:

> Adam Wulkiewicz wrote:
>> Barend Gehrels wrote:
>>> Ah, was that the problem. You reporterd earlier that point_xy was not
>>> working in index for area, but not that this was the reason. Thanks for this
>>> new report and with this it is fixed now.
>>>
>>> Besides this I also updated/extended the linestring/polygon intersection
>>> (which is working for intersection and difference now, in all cases that I
>>> tested. Will do some more test next week.)
>>>
>> Ok, thanks.
> Btw, I've added some basic version of BoostBook doc with generated html.
>

Great, of course. I did have a quick scan.

My first (and major) question is, why BoostBook? QuickBook is the
popular and recommended way, and besides that using QuickBook would
interoperate much better with Boost.Geometry documentation...

I do realize that Boost.Geometry itself is not following the default
Boost path (if there is one). So I will explain a bit more (summarize,
there is more on this on this list).

Before review we used Doxygen for our documentation. Many reviews
criticized that and favoured QuickBook. QuickBook is also great. So we
wanted to move to Quickbook, but at the same time not loose automatic
documentation, which Doxygen does very well. So we first tried using the
existing XSLT templates to go from Doxygen to BoostBook. This is used by
e.g. ASIO. However, that did not always too well, for us. And I wanted
more possibilities without having to fight against XSLT each time...
Therefore we created a (quite simple) tool to translate from Doxygen to
Quickbook.

It is written in more detail on my blog:
http://barendgehrels.blogspot.com/search/label/quickbook

I would favour this for Boost.Geometry's Index, especially to be able to
integrate it better. If else, use QuickBook but... if it is one library
why not one toolset?

Now that I downloaded the tree again, for completeness I repeat the URL:

https://svn.boost.org/svn/boost/sandbox-branches/geometry/index

I have the same question for tests, why not the pattern Boost.Geometry
is using?

And for samples (there are not yet, no problem, but it would often be
helpful) please also conform to Boost.Geometry's current approach (i.e.
a sort of unit-samples, which can be very nicely integrated with
QuickBook and our conversion tool...)

Regards, Barend


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

Re: rtree ?

Adam Wulkiewicz
2011/11/29 Barend Gehrels <[hidden email]>:
>
> Great, of course. I did have a quick scan.
>
> My first (and major) question is, why BoostBook? QuickBook is the popular
> and recommended way, and besides that using QuickBook would interoperate
> much better with Boost.Geometry documentation...

I just wanted to start from more native interface since I've never
used any of them. I've switched to QuickBook already. New version is
available.

> Before review we used Doxygen for our documentation. Many reviews criticized
> that and favoured QuickBook. QuickBook is also great. So we wanted to move
> to Quickbook, but at the same time not loose automatic documentation, which
> Doxygen does very well. So we first tried using the existing XSLT templates
> to go from Doxygen to BoostBook. This is used by e.g. ASIO. However, that
> did not always too well, for us. And I wanted more possibilities without
> having to fight against XSLT each time... Therefore we created a (quite
> simple) tool to translate from Doxygen to Quickbook.
>
> It is written in more detail on my blog:
> http://barendgehrels.blogspot.com/search/label/quickbook

Ok, thanks.

> I have the same question for tests, why not the pattern Boost.Geometry is
> using?
>
> And for samples (there are not yet, no problem, but it would often be
> helpful) please also conform to Boost.Geometry's current approach (i.e. a
> sort of unit-samples, which can be very nicely integrated with QuickBook and
> our conversion tool...)

Should tests use hardcoded data or may it be randomized? Or should
there be 2 types od tests, if I want to use this kind of input? First,
using not changing data for regression tests and the other one, using
arbitrary data, for local testing only?

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

Re: rtree ?

Barend
Hi Adam,

On 30-11-2011 4:39, Adam Wulkiewicz wrote:
> 2011/11/29 Barend Gehrels<[hidden email]>:
>> Great, of course. I did have a quick scan.
>>
>> My first (and major) question is, why BoostBook? QuickBook is the popular
>> and recommended way, and besides that using QuickBook would interoperate
>> much better with Boost.Geometry documentation...
> I just wanted to start from more native interface since I've never
> used any of them. I've switched to QuickBook already. New version is
> available.

OK, cool. I see them indeed.

If you think about the full Doxygen->Quickbook chain, and I still
encourage that, I'll be happy to help you.
>> I have the same question for tests, why not the pattern Boost.Geometry is
>> using?
>>
>> And for samples (there are not yet, no problem, but it would often be
>> helpful) please also conform to Boost.Geometry's current approach (i.e. a
>> sort of unit-samples, which can be very nicely integrated with QuickBook and
>> our conversion tool...)
> Should tests use hardcoded data or may it be randomized?
It should be verifiable, so this is usually hardcoded.

Besides that they should run fast.

> Or should
> there be 2 types od tests, if I want to use this kind of input? First,
> using not changing data for regression tests and the other one, using
> arbitrary data, for local testing only?
>

Two types is perfect. I'm doing that for Boost.Geometry as well. Most is
hardcoded. But I've also robustness tests with high volumes random data,
which is not in the normal unit test jamfile. So not called
automatically. Also because that would take too long.

Regards, Barend


_______________________________________________
ggl mailing list
[hidden email]
http://lists.osgeo.org/mailman/listinfo/ggl
12