Geometry Boost List: Re: [geometry] Geometry Digest, Vol 29, Issue 20

Subject: Re: [geometry] Geometry Digest, Vol 29, Issue 20
From: Aaron Josephs (aaron_at_[hidden])
Date: 2014-05-20 12:27:07

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_at_[hidden]> wrote:

> Send Geometry mailing list submissions to
>         geometry_at_[hidden]
>
> 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_at_[hidden]
>
> You can reach the person managing the list at
>         geometry-owner_at_[hidden]
>
> 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_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: Re: [geometry] Buffer/Offsetting Polygon with holes
> Message-ID: <537A6809.9010306_at_[hidden]>
> 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_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: Re: [geometry] PreparedPolygon performance (was: Geometry
>         Digest, Vol 29, Issue 15)
> Message-ID: <537A6FA8.7080301_at_[hidden]>
> 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_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: [geometry] Why reverse_dispatch returns bool rather than
>         mpl::bool_<T> ?
> Message-ID: <537B64A1.8030600_at_[hidden]>
> 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_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: Re: [geometry] Why reverse_dispatch returns bool rather than
>         mpl::bool_<T> ?
> Message-ID: <537B67A0.7070908_at_[hidden]>
> 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_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/geometry
> >
>
>
>
>
> ------------------------------
>
> Message: 5
> Date: Tue, 20 May 2014 16:43:05 +0200
> From: Samuel Debionne <samuel.debionne_at_[hidden]>
> To: geometry_at_[hidden]
> Subject: Re: [geometry] Why reverse_dispatch returns bool rather than
>         mpl::bool_<T> ?
> Message-ID: <537B69F9.3050504_at_[hidden]>
> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry
>
>
> ------------------------------
>
> End of Geometry Digest, Vol 29, Issue 20
> ****************************************
>