Adam, of course I used optimizations O3 is on, I didn't mean to say polygons are in the rtree, I wasn't even aware that you could use anything but boxes. As for how the polygons and points look, the polygons are medium size, 100's - 1000's of points, a over 2.5k polygons, for the points being checked every point will always be in exactly one polygon. Regarding the log n point in poly algorithm hopefully someone will implement it at some point, I certainly don't have the time or geometry expertise.


On Tue, May 20, 2014 at 12:00 PM, <geometry-request@lists.boost.org> wrote:
Send Geometry mailing list submissions to
        geometry@lists.boost.org

To subscribe or unsubscribe via the World Wide Web, visit
        http://lists.boost.org/mailman/listinfo.cgi/geometry
or, via email, send a message with subject or body 'help' to
        geometry-request@lists.boost.org

You can reach the person managing the list at
        geometry-owner@lists.boost.org

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Geometry digest..."


Today's Topics:

   1. Re: Buffer/Offsetting Polygon with holes (Barend Gehrels)
   2. Re: PreparedPolygon performance (was: Geometry Digest, Vol
      29, Issue 15) (Adam Wulkiewicz)
   3. Why reverse_dispatch returns bool rather than     mpl::bool_<T> ?
      (Samuel Debionne)
   4. Re: Why reverse_dispatch returns bool rather than
      mpl::bool_<T> ? (Adam Wulkiewicz)
   5. Re: Why reverse_dispatch returns bool rather than
      mpl::bool_<T> ? (Samuel Debionne)


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

Message: 1
Date: Mon, 19 May 2014 22:22:33 +0200
From: Barend Gehrels <barend@xs4all.nl>
To: "Boost.Geometry library mailing list" <geometry@lists.boost.org>
Subject: Re: [geometry] Buffer/Offsetting Polygon with holes
Message-ID: <537A6809.9010306@xs4all.nl>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

Hi Heiko, (cc Yohann)

Hunk wrote On 19-5-2014 11:02:
> Hello,
>
> i found an answer for your buffer algorithm
>
> http://stackoverflow.com/questions/14592093/boost-geometry-buffer-algorithm-does-it-work-for-general-case-polygons
>
> Can u tell me what is the current state of the algorithm?
>
> I want to use it to offset the polygon with a disc of a specific radius that
> i can use this for motion planning.
>


Alas it is not ready for release yet. Yohann, also for you because you
asked this a few months ago. At that time I was still positive about
including it in coming release. That is now quite improbable, sorry for
that.

Regards, Barend



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

Message: 2
Date: Mon, 19 May 2014 22:55:04 +0200
From: Adam Wulkiewicz <adam.wulkiewicz@gmail.com>
To: "Boost.Geometry library mailing list" <geometry@lists.boost.org>
Subject: Re: [geometry] PreparedPolygon performance (was: Geometry
        Digest, Vol 29, Issue 15)
Message-ID: <537A6FA8.7080301@gmail.com>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"

Hi Aaron,

Aaron Josephs wrote:
>  I'm curious how did you compare the libraries?
>  What was the test case?
>  Many tests for Points within only one Polygon?
>  If yes, then have you tried to first calculate the bounding box of a
>  Polygon and use it for the first check to eliminate this difference
> between
>  libraries?
>  Are the benchmarksavailablesomewhere?
> Adam -
> The situation: I have multiple polygons that don't change, and I am
> querying to which one of those polygons contains various points. The
> program works by first creating an rtree containing all the polygons
> (using the packing method) and when a range of polygons is returned
> covered_by() is called to check if the point is indeed in the polygon
> (no reason to check the bounding box in this case since that is what
> the rtree is for). The fact that this program ran slower than the JTS
> version prompted me to narrow down the cause. From running the
> covered_by query of boost side by side with JTS's (different name in
> JTS) I found that JTS had a far better performance when the
> PreparedPolygon class was used. Looking further into that it seems
> that JTS's prepared polygon does something where it creates a data
> structure called an edge graph to reduce the computation of
> intersections to log(n). I don't think boost has anyway to do this,
> unfortunately I can't post any of my code or the geometries I'm using,
> hopefully this explanation helps enough.
>

Thanks for the explanation! Yes indeed the complexity of the algorithm
is "better" but there are other aspects which influences the speed, e.g.
data locality. How many Points do your Polygons have more or less?

What C++ compiler did you use and which optimization level? As Bruno
wrote template-based libraries are much faster when the optimizations
are enabled.

Aside from your findings I'm worried about something else. You wrote
that the rtree contains Polygons. Is it some kind of mental shortcut or
indeed Polygons are stored in the rtree and e.g. AABB is calculated on
the fly? If the second one is true, it is probably a lot slower than it
could be because the Box is calculated each time the rtree wants to
access it and (at least for now). The fastest way is to store some small
objects containing a Box, e.g. std::pair<Box, ID> where ID could be an
index of Polygon or an iterator, etc.

Regards,
Adam

-------------- next part --------------
HTML attachment scrubbed and removed

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

Message: 3
Date: Tue, 20 May 2014 16:20:17 +0200
From: Samuel Debionne <samuel.debionne@ujf-grenoble.fr>
To: "Boost.Geometry library mailing list" <geometry@lists.boost.org>
Subject: [geometry] Why reverse_dispatch returns bool rather than
        mpl::bool_<T> ?
Message-ID: <537B64A1.8030600@ujf-grenoble.fr>
Content-Type: text/plain; charset=ISO-8859-1

Hello all,

It's all in title but the reason I'm asking is that non-type parameter
are not really friendly with mpl metafunction composition. For instance,
a Placeholder Expression requires that :

> All of X's template parameters, including the default ones, are types.

Concrete problem :

I would like to turn the detail::distance::default_strategy into a meta
function class :

mpl::quote5<detail::distance::default_strategy> would do the trick if
the Reverse template parameter was not a non type parameter bool.

Regards,
Samuel


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

Message: 4
Date: Tue, 20 May 2014 16:33:04 +0200
From: Adam Wulkiewicz <adam.wulkiewicz@gmail.com>
To: "Boost.Geometry library mailing list" <geometry@lists.boost.org>
Subject: Re: [geometry] Why reverse_dispatch returns bool rather than
        mpl::bool_<T> ?
Message-ID: <537B67A0.7070908@gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

Hi,

Samuel Debionne wrote:
> Hello all,
>
> It's all in title but the reason I'm asking is that non-type parameter
> are not really friendly with mpl metafunction composition.

reverse_dispatch<> is derived from integral_constant<bool, ...> so AFAIU
it can be passed directly to the mpl metafunction. Or am I wrong about this?

Regards,
Adam

> For instance,
> a Placeholder Expression requires that :
>
>> All of X's template parameters, including the default ones, are types.
> Concrete problem :
>
> I would like to turn the detail::distance::default_strategy into a meta
> function class :
>
> mpl::quote5<detail::distance::default_strategy> would do the trick if
> the Reverse template parameter was not a non type parameter bool.
>
> Regards,
> Samuel
> _______________________________________________
> Geometry mailing list
> Geometry@lists.boost.org
> http://lists.boost.org/mailman/listinfo.cgi/geometry
>




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

Message: 5
Date: Tue, 20 May 2014 16:43:05 +0200
From: Samuel Debionne <samuel.debionne@ujf-grenoble.fr>
To: geometry@lists.boost.org
Subject: Re: [geometry] Why reverse_dispatch returns bool rather than
        mpl::bool_<T> ?
Message-ID: <537B69F9.3050504@ujf-grenoble.fr>
Content-Type: text/plain; charset=ISO-8859-1

> reverse_dispatch<> is derived from integral_constant<bool, ...> so AFAIU
> it can be passed directly to the mpl metafunction. Or am I wrong about
> this?

Thanks Adam, I was just about to answer my question with an other (more
accurate) question :

Why is the template parameter Reverse of say dispatch::distance of
non-type bool rather than mpl::bool_ ?

template
<
    ...
    *bool* Reverse = reverse_dispatch<Geometry1, Geometry2>::type::value
>

Samuel



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

Subject: Digest Footer

_______________________________________________
Geometry mailing list
Geometry@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/geometry


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

End of Geometry Digest, Vol 29, Issue 20
****************************************