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 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. 


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