Re: [boost] [Review] GGL review starts today, November 5th

Subject: Re: [boost] [Review] GGL review starts today, November 5th
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-11-12 17:23:00

Hi Luke,

Simonson, Lucanus J wrote:
>
> I still don't know what the find_intersections algorithm's complexity is or how it works.  What data structure does it currently use for indexing?  Based on the documentation I'm guessing you use a 1D spatial index for red blue overlap detection between monotonic sections.  Is that correct?  

As in the documentation: monotonic sections, and the algorithm is named 
"get_intersection_points". How it works: I worked quite a day on that 
page and I hope it is clear enough for the detail needed for a review. 
If not, I'm sorry to hear that but I don't know if I can still improve 
this before the review period ends.

> [...] Do you realize that pathological cases of large number of 45 degree edges with no intersection between them with result in O(n^2) work even with a good 2d spatial index based algorithm for finding overlaps because 2d spatial indexing works on bounding boxes. [...]
>   
A large number of edges will result in multiple monotonic sections, as 
described in the new doc-page, so also then it will not be quadratic, in 
most cases. You're referring (I think) to a very large number of 
diagonal parallel edges and indeed all those bounding boxes will 
overlap. And I understand most spatial indexes will not help here (did 
you scan all variants?). As this seems to be problematic for both our 
libraries we can discuss this further (but at this moment it is not so 
convenient for me).

Anyway, I think our figures are clear enough, there is no library found 
which even comes close, within several factors. So I would not worry too 
much about its current performance. If you find a real test-case where 
it is too slow, I'm interested, we're happy to (try to) improve it.

> Holes are obviously associated to their enclosing outer rings by your algorithm because that is the semantics of the output data structure.  My question is, how is it identified by your algorithm that a hole is enclosed by a polygon?  This is something that is prone to pathological performance in the cases where the number of holes is very large, so it is an important part of the algorithm.
>   
I agree, and it's currently sorted on descending area to get obvious 
possibilities. There are alternatives here such as bboxes, spatial 
indexes or multiple-point-in-polygon, there is room for research and 
possible improvement.

>>
>> - interior_type is there a polygon may have holes. If library users
>> use polygons without holes, they can take a ring (or, stated more
>> precisely: 
>> a type fulfilling the Ring Concept)
>> - interior_type is expected to be a Boost.Range (for a read-only
>> polygon) and to be STL container-conformant (for a mutable polygon).
>>     
>
> I'm not too keen on this requirement.  It turns out that my own polygon with holes has a private data member which is an stl container that contains the holes, but I don't expose that in the public interface.  I don't believe I could adapt my polygon_with_holes_data to your polygon concept without changing its implementation, however, I am certain that I could adapt your polygon data type to my polygon_with_holes_concept.  I doubt there are many legacy polygon types that can be successfully adapted to your mutable polygon concept.  This calls into question to the utility of the polygon concept.  I would rather see it done the same way as linestring where you can either use stl style pushback and clear or supply your own clear and append traits.
>   
Also here we're happy to provide it, it is not satisfying your needs, 
especially if this enhances interoperability we're certainly willing to 
adapt and finetune things. Actually I'm also glad to hear positive 
feedback about the way we designed it for linestring.

Thanks, Barend