|
|
Geometry : |
Subject: Re: [geometry] Geometry Digest, Vol 29, Issue 15
From: Aaron Josephs (aaron_at_[hidden])
Date: 2014-05-19 13:00:19
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 benchmarks available somewhere?
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.
On Fri, May 16, 2014 at 5:48 AM, <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. Is the de9im class usable yet (Aaron Josephs)
> 2. Re: [index] rtree news (Barend Gehrels)
> 3. Re: TR: dissolve and correct (Barend Gehrels)
> 4. Re: [index] rtree news (Menelaos Karavelas)
> 5. Re: Is the de9im class usable yet (Adam Wulkiewicz)
> 6. Re: Is the de9im class usable yet (Bruno Lalande)
> 7. [test][length] cannot compile unit test for length in develop
> branch (Menelaos Karavelas)
> 8. Re: [test][length] cannot compile unit test for length in
> develop branch (Menelaos Karavelas)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Thu, 15 May 2014 13:36:10 -0400
> From: Aaron Josephs <aaron_at_[hidden]>
> To: geometry_at_[hidden]
> Subject: [geometry] Is the de9im class usable yet
> Message-ID:
> <CAHyt1g+apUC73=
> oqa6hRqoKJRiHQXPjnBXVs3NAr7XAPvQ4SVw_at_[hidden]>
> Content-Type: text/plain; charset="utf-8"
>
> I can't seem to figure out how to use the de9im class in boost geometry
> (posted SO question here
>
> http://stackoverflow.com/questions/23684869/is-the-boost-de-9-im-struct-usable
> ).
> Maybe I'm just missing something but is it even in a usable state yet, an
> example of a point within a polygon calculation would be greatly
> appreciated.
> -------------- next part --------------
> HTML attachment scrubbed and removed
>
> ------------------------------
>
> Message: 2
> Date: Thu, 15 May 2014 22:55:09 +0200
> From: Barend Gehrels <barend_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: Re: [geometry] [index] rtree news
> Message-ID: <537529AD.7070406_at_[hidden]>
> Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
>
> Hi Adam,
>
> Adam Wulkiewicz wrote On 15-5-2014 3:53:
> > Hi,
> >
> > I have some news regarding the rtree:
> >
> > 1. Segments are now supported by the rtree. They can be used as
> > Indexables and stored directly in the spatial index.
>
> Great news! This is really convenient. Thanks a lot.
>
> Is it possible to have this in the docs too (including an example?)
>
> Menelaos, does this mean that we should reconsider (probably after
> release) some implementations for distance?
>
> Regards, Barend
>
>
> -------------- next part --------------
> HTML attachment scrubbed and removed
>
> ------------------------------
>
> Message: 3
> Date: Thu, 15 May 2014 22:56:45 +0200
> From: Barend Gehrels <barend_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: Re: [geometry] TR: dissolve and correct
> Message-ID: <53752A0D.7020400_at_[hidden]>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> Hi Yohann,
>
> yohann.benedic_at_[hidden] wrote On 15-5-2014 11:50:
> > Hi everyone,
> >
> > Any comment on my message below?
>
>
> >
> > Yohann B?n?dic wrote
> >> Hi again,
> >>
> >> I am successfully compiling dissolve in the release branch thanks to
> Adam and Barend's support.
> >> Now comes the question about its recommended usage.
> >>
> >> Before I realized my polygon database contained self-intersecting
> polygons, I use to call the correct algorithm after each geometry::polygon
> was built to make sure it met boost::geometry standards (clockwise and
> duplicate ending points).
> >> What am I supposed to do now that some of my input polygons are
> self-intersecting : for them, clockwise or anticlockwise doesn't make
> sense, so I guess I should skip the call to correct, manually duplicate the
> endpoints and proceed directly with the dissolve algorithm.
> >> Should I then call correct on the result to fix Clockwise issue or is
> dissolve taking care of that for me?
>
>
> Sure, I was not forgotten yet, but indeed it takes a while. I will
> answer Saturday.
>
> Regards,
> Barend
>
>
>
> ------------------------------
>
> Message: 4
> Date: Fri, 16 May 2014 00:54:42 +0300
> From: Menelaos Karavelas <menelaos.karavelas_at_[hidden]>
> To: geometry_at_[hidden]
> Subject: Re: [geometry] [index] rtree news
> Message-ID: <537537A2.9080102_at_[hidden]>
> Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
>
> Hi Barend.
>
> On 15/05/2014 11:55 ??, Barend Gehrels wrote:
> > Hi Adam,
> >
> > Adam Wulkiewicz wrote On 15-5-2014 3:53:
> >> Hi,
> >>
> >> I have some news regarding the rtree:
> >>
> >> 1. Segments are now supported by the rtree. They can be used as
> >> Indexables and stored directly in the spatial index.
> >
> > Great news! This is really convenient. Thanks a lot.
> >
> > Is it possible to have this in the docs too (including an example?)
> >
> > Menelaos, does this mean that we should reconsider (probably after
> > release) some implementations for distance?
>
> Yes, we can.
> I am not saying that using segments in the R-Tree would be
> better/faster. I am only saying that now we have one more alternative
> way for implementing distances, and in that respect it should be
> investigated.
>
> - m.
>
> > Regards, Barend
> >
> >
> >
> >
> > _______________________________________________
> > Geometry mailing list
> > Geometry_at_[hidden]
> > http://lists.boost.org/mailman/listinfo.cgi/geometry
>
> -------------- next part --------------
> HTML attachment scrubbed and removed
>
> ------------------------------
>
> Message: 5
> Date: Fri, 16 May 2014 02:15:26 +0200
> From: Adam Wulkiewicz <adam.wulkiewicz_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: Re: [geometry] Is the de9im class usable yet
> Message-ID: <5375589E.2070304_at_[hidden]>
> Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
>
> Hi Aaron,
>
> Aaron Josephs wrote:
> > I can't seem to figure out how to use the de9im class in boost
> > geometry (posted SO question here
> >
> http://stackoverflow.com/questions/23684869/is-the-boost-de-9-im-struct-usable
> ).
> > Maybe I'm just missing something but is it even in a usable state yet,
> > an example of a point within a polygon calculation would be greatly
> > appreciated.
>
> It doesn't make sense to discuss on StackOverflow in the comments so I'd
> like to move the discussion here.
>
> You said:
> "Already using the rtree, I only ask this question because the JTS
> implementation of |within| using a prepared geometry is killing
> |boost::geometry::within|, and JTS is in java"
>
> 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 benchmarks available somewhere?
>
> Regards,
> Adam
> -------------- next part --------------
> HTML attachment scrubbed and removed
>
> ------------------------------
>
> Message: 6
> Date: Fri, 16 May 2014 08:45:04 +0100
> From: Bruno Lalande <bruno.lalande_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: Re: [geometry] Is the de9im class usable yet
> Message-ID:
> <CAB-MWKzGFbL12VoJCE=kL=
> qTO89xNFNsc26H0ZBi6Njp9wBVVQ_at_[hidden]>
> Content-Type: text/plain; charset="utf-8"
>
> >
> > 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 benchmarks available somewhere?
> >
>
> + the usual suspect when it comes to templated libraries and performance =>
> have you made sure to enable compiler optimizations.
>
> Regards
> Bruno
> -------------- next part --------------
> HTML attachment scrubbed and removed
>
> ------------------------------
>
> Message: 7
> Date: Fri, 16 May 2014 12:39:30 +0300
> From: Menelaos Karavelas <menelaos.karavelas_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: [geometry] [test][length] cannot compile unit test for length
> in develop branch
> Message-ID: <5375DCD2.9020304_at_[hidden]>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> Hello all.
>
> The subjects says it all, but just to add a few details. The problem
> appears with both g++ and clang++.
> The error messages I get seem to have to do with a "call" to
> point_type<Geometry>::type where Geometry is actually a variant.
>
> Does anybody else have a similar experience? Any ideas?
>
> Thanks.
>
> - m.
>
>
>
> ------------------------------
>
> Message: 8
> Date: Fri, 16 May 2014 12:48:30 +0300
> From: Menelaos Karavelas <menelaos.karavelas_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: Re: [geometry] [test][length] cannot compile unit test for
> length in develop branch
> Message-ID: <5375DEEE.3060500_at_[hidden]>
> Content-Type: text/plain; charset=UTF-8; format=flowed
>
> Some more info on this: the problem appears with the macro
> GEOMETRY_TEST_DEBUG is defined.
> If not defined, then the length test compiles.
>
> - m.
>
> On 16/05/2014 12:39 ??, Menelaos Karavelas wrote:
> > Hello all.
> >
> > The subjects says it all, but just to add a few details. The problem
> > appears with both g++ and clang++.
> > The error messages I get seem to have to do with a "call" to
> > point_type<Geometry>::type where Geometry is actually a variant.
> >
> > Does anybody else have a similar experience? Any ideas?
> >
> > Thanks.
> >
> > - m.
> >
>
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry
>
>
> ------------------------------
>
> End of Geometry Digest, Vol 29, Issue 15
> ****************************************
>
Geometry list run by mateusz at loskot.net