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-09 12:41:06

Hartmut Kaiser wrote:
> The formal review of the Generic Geometry Library (GGL) starts today,
> November 5, 2009 and will finish November 15, 2009.
> GGL is being developed by Barend Gehrels, Bruno Lalande and Mateusz
> Loskot, with substantial input from this Boost mailing list.

This library looks like a very good example of generic interfaces for geometry objects and several well known and useful geometry algorithms. 

This is not a review.

I found it difficult to answer my questions about the library based on the documentation.  I am having difficulty coming up with a complete list of features for the library.  It seems there is more implemented than documented.  Specifically, I'd like to know more about the ggl::algorithms::overlay namespace, which appears to contain algorithms of interest to me, but is not documented.

I'll ask my questions on the list to help me identify which header files I should look at to understand the interfaces and implementation of interesting algorithms in the GGL.

1. Does the library support other Boolean operations between pairs of polgyons than intersection?
        Union
        XOR
        AND NOT
2. If so, does the library support the union of more than two overlapping polygon simultaneously (three or more mutually overlapping polygons)?
3. Does the library support map overlay operations of two layers?  Of more than two layers simultaneously?
4. If the non-self-intersecting invariant is violated at the input of the polygon pair intersection algorithm what does the algorithm do?
5. Is there a way to check self-intersecting invariant before attempting an intersection operation?
6. Is there a way to fix a polygon that is self-intersecting to be non-self intersecting?
7. When intersection points are snapped to the floating point grid at the output of the polygon pair intersection algorithm edges may move laterally some small distance which may introduce self intersection artifacts.  How is this handled by the polygon intersection algorithm?
8. What is the algorithmic complexity of the polygon intersection algorithm?
9. Could you please provide the community with a description of the polygon intersection algorithm?
10. Is the polygon intersect bounding box algorithm linear time?
11. When a polygon is intersected against a bounding box the same problem can happen that self intersections are introduced in the output polygon(s) when intersection points are snapped to the floating point grid.  These artifacts cannot be addressed by a linear time algorithm.  Are the output polygons of the polygon intersects bounding box algorithm implemented by this library potentially self intersecting?
12. Is the distance algorithm implemented for linestring pairs?  For polygon pairs?  If so, what algorithmic complexity does it have, and can you describe the algorithm for the community?
13. Why is there no custom polygon example in the documentation?
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?
15. What happens if you instantiate the polygon pair intersection algorithm with integer coordinates?
16. What is required for a data type to satisfy the requirements of a coordinate type?
17. Can you tell us more about the support and usage of high precision numerical datatypes?

With enough time and effort reading the code and exercising it I can answer all of these questions for myself, but a little help from the library author would be greatly appreciated.  If the answers to some of my questions can be found in the documentation please let me know where.

It is unfortunate that Fernando's buisness success leaves him so little time recently--hopefully he will be able to conduct a review.  I think that as a CGAL author and user of both GPC and CGAL in his consulting work his review of the polygon intersection algorithm in GGL would be insightful.

Thanks,
Luke