Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-09-15 14:09:46

Fernando Cacciola wrote:
>> This is a trade-off that I made intentionally.  The rationale for not
>> allowing references to member data of geometry objects is that a
>> geometry object may not have such a data member.  For example, a
>> polygon may store its first point as a point and then subsequent
>> points as offset pairs from the previous point, a rectangle may be
>> represented as its center plus width and height and a point may be
>> in polar coordinates convertible to cartesian in the traits
>> specialization.  My own manhattan polygon data type stores only one
>> coordinate per vertex and has no point to get a non-const reference
>> to. In this case I sacrificed performance for generality. 
>> 
> But you don't have to sacrifice anything: that's the whole point of
> generic programming.
> Just add the concepts that allow mutation of veritices (or at least
> assignment 
> of vertices which is not even the same) and let the right types model
> it. 
> Then distpatch your algorithms appropriatedly.
> 
> What you said above is like justifying O(n) lookup in a vector just
> because a generlized container might not have random access.

That is an optimization that I didn't implement.  I agree it is implementable, but it does complicate the design somewhat.  In general people who have legacy OO polygon types don't provide mutable access to their internal data members anyway because that violates OO design principles.  It is an optimization that many people would not be able to take advantage of because they polygon types prevent efficient manipulation of member data outside member and friend functions.  It is also safe to assume that a polygon being mapped to my polygon concept may be a 3rd party data structure that the user doesn't have the ability to modify to declare the mutable accessor functions to be friend.  Obviously I don't agree with such design choices made by the implementation of legacy polygon classes, but it was these sorts of legacy data types I had in mind when I designed the interface.  The user can easily implement their own mutating version of these algorithms themselves by using the cooresponding point concept function in a loop.  There are quite a few optimizations the user can make if they choose, such as caching the bounding boxes of polygons and polygon sets and doing bounding box prechecks before boolean intersection operations and containment checks.  I don't and can't implement every optimization the user might want/need.  I can provide them a solid foundation for implementing them, however.

>> I was trying to make providing the traits easier.  Having a trait
>> for winding is an optimization.  I was trying to make it easy for
>> users to specify that trait by returning that the winding of their
>> polygon is not known at compile time.

> I undertand the existence of the "unknown_winding". That's not the
> problem. 
> It is the lack of this in the rest of the API.
> Ther is no need for two windings enumerations IMO.

One enum has two values, the other has three.  I use the one with three only in the polygon traits and I use the class that encapsulates the one with two value everywhere else.  I definintely don't want unknown winding to be a potential value of the winding direction data type I use everywhere because I would need to throw an excpetion in most instances if it should ever take that value.  I designed the system the way it is so that the enums would be type safe.
 
>>  I expect the return of negative values from area() would be more
>> surprising to the user than the fact that I created a special enum
>> for use by the winding trait. 
>> 
> Yet even if it rally were more surprising for some users, the point
> is that you can get rid of the sign but you cannot put it back once
> it is lost. 
> 
> i.e., users can always do abs(area) but they can never figure out
> what the sign was before it got lost in the implementation without
> computing the winding or such. 
> 
> So, signed area is more general and should be the one provided by the
> library. 

The only instance in which that would be beneficial is when the user wants to know both the area and winding direction of a given polygon and can do so with one instead of two calls the the point_sequence_area() algorithm.  I'm just not convinced that will happen very often, or how important an optimization it is.  Remember, there is a lot of optimization work I could do all over the place.  When considering an optimization I have to weigh it against the value of other potential optimizations and the value of implementing new features.  Typically once a feature is implemented and meets internal requirements (where performance is a critical concern mind you) I don't get the luxury of going back and making optimizations because new features tend to be more important than optimizations on existing features.  For algorithms that have O(n) complexity I generally don't consider the constant factor to be that important because these algorithms just never show up in the profiling of any real applications I've worked with, even if it is a little slow it is still pretty darn fast compared to the real work applications are doing.  I tend to give optimizations to the more complex algorithms that take longer to implement more priority than the simple algorithms that anyone can easily implement and usually already have by the time they realize they need my library for some of the harder stuff.  I like implementing optimizations, it makes me feel good to see benchmark numbers improving.  I'm happy to do that kind of work even after the library is accepted and I'd be happy to accept patches that add or enable optimizations.  There is a lifetime of work required to make polygon as fast as humanly possible, just as Stepanov didn't implement all of the optimizations that eventually made their way into std::sort and the stl red black tree I don't expect I can do all the optimizations to Boost.Polygon by myself and I'd like to see community participation. 

Thanks,
Luke