Geometry Boost List: Re: [geometry] PreparedPolygon performance (was: Geometry Digest, Vol 29, Issue 15)

Subject: Re: [geometry] PreparedPolygon performance (was: Geometry Digest, Vol 29, Issue 15)
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-05-19 16:55:04

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