Subject: Re: [boost] GGL Review
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-11-16 14:35:14
Jonathan Franklin wrote:
> On Mon, Nov 16, 2009 at 11:16 AM, Stefan Strasser
> <strasser_at_[hidden]> wrote:
>> I think the question of this review is not whether some algorithms
>> in GGL have limitations, as long as they are documented, but if the
>> concepts and algorithm/strategy interface is sufficient to allow the
>> implementation of specialized algorithms. is this the case?
> The concepts, interfaces, and algorithms provided by a library are
> indeed of paramount importance during a review. However, the
> implementation is also extremely important. Any serious algorithmic
> bugs identified in the implementation should probably be fixed prior
> to release (e.g. acceptance is contingent on fixing them).
> My argument is that numerical stability issues due to floating point
> limitations are not algorithmic bugs, but rather "properties" of the
> chosen algorithm(s). </flame_bait>
> I greatly like the ability to generically pick the representation of
> my choice, w/ the ability to use a more "robust" algorithm when
> needed. Any bugs that would prevent the more robust algorithm from
> being as robust as it claims should be fixed.
>> luke seems to be willing to integrate his
>> Boost.Robust2DIntegerPolygon into GGL, but he also seems to have
>> some concerns if he'll be able to do that using GGL's polygon
>> representation. those should be addressed before GGL is accepted.
> I was under the impression that Luc was basing his reservations on
> robustness issues due to floating point limitations. Perhaps I
> misread, or missed a point or two.
Barend requires that the polygon provide a type with stl container interfaces that holds its holes. This prevents it from adapting the majority of polygon data types (including my own) that don't provide direct acceess to private members. My request was that he make the interface for his polygon concept more generic.
If you bother to look at my submission you will find that the interfaces for the geometry concepts are fully generic, and the fixed point requirement for polygon intersection is a property of the algorithm I chose, and documented. I can easily call eg. Barend's algorithm when the coordinate is floating point without the need to change my interfaces at all, so I think it is inaccurate to describe my library as "not generic". The concepts I define are fully generic and equivilent to what Barend has proposed. I don't handle different coordinate systems, but that is a difference in scope between my library and GGL and not a design flaw.
I'd also like to point out that fixed point is not a VSLI specific requirement, nor is robustness. Some GIS applications use fixed point coordinates and closed source solutions for polygon clipping that are robust and fast are used in VLSI all the time.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk