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

Subject: Re: [boost] [Review] GGL review starts today, November 5th
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-11-12 13:46:50

Barend Gehrels wrote:
> Hi Luke,
> 
> Herewith the answers on (most of) your questions (the rest wil come
> soon now).
> 
> 
> First, I added two additional pages of documentation, to not make this
> answering mail too long.
> - one about intersections (overlay): http://tinyurl.com/ggl-sets

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?  My own implementation is a 1D spatial index on all edges, so there is considerable algorithmic advantage derived from both red-blue and monotonic section optimizations. 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.  I was hoping to upgrade my algorithm to the optimal algorithm rather than apply optimizations to the sup-optimal algorithm, but that looks increasingly unlikely now.

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'll defer discussion of your answers to the self intersection questions until the precision questions are answered since these issues are inter-related.

> - one with custom polygon: http://tinyurl.com/ggl-c06

Thank you, that is what I wanted to see.

>> 14. Why do you need interior_type for the polygon concept traits? 
>> What requirements does the interior_type need to satisfy?  Is it
>> expected to be an stl container?  
>> 
> 
> - 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.

Regards,
Luke