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

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-09-15 12:09:39

Hi Luke,

> Fernando Cacciola wrote:
>> (*) The library needs to distinguish lvalue-ness from write-ness: it is one
>> thing to "reset" the X ccordinate of a point and one totally diferent is to
>> get a non-const reference (lvalue) to it.
>> 
>> This general lack of "mutation" as opposed to "assignment" causes for 
>> example gross inefficiency in the operations that modify the vertices of a 
>> polygon (such as convolve, scale, transform, etc):
>> 
>> The functions that implement that, generate a new container with the 
>> modified points and then resets the point sequence within the input/output
>> polygon. IMO this is nonesense (and a showstopper from a review POV). yet
>> is it really just the conequence of lacking "lvalue" access to the vertices
>> WITHIN a polygon.
> 
> 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.

>> (*) There is a lowercase "winding_direction" enum whith values like 
>> "clockwise_winding" and "counterclock_winding" (plus unknown), but then
>> there is the "direction_1d_enum" with values of "CLOCKWISE" and
>> "COUNTERCLOCKWISE" Not only that is confusing but it also boils down to
>> inefficient code because the "winding" function returns
>> CLOCKWISE|COUNTERCLOCKWISE yet the "polygon_traits<>::winding" code that is
>> the actual implementation returns winding_direction. Since the actual
>> numeric values mismatch there is an explicit conditional convertion:
>> 
>> return w == clockwise_winding = CLOCKWISE : COUNTERCLOCKWISE
>> 
>> (*) In fact, the problem above comes from the design of the fucntion 
>> winding(): if the actualt winding cannot be computed, it iself computes the
>> area instead and uses its sign to second guess the winding.
>> 
>> IMO, that alternative calculation should be done by the user if and when it
>>  makes sense.
>> 
>> (*) In fact again, the problem above comes from the design of the function
>> area(): there is a "point_sequence_area" that does the actual calculation
>> and returns a signed value. But then area() returns the ABS of that, so a
>> user would not be able to call area() as a robust way to compute the
>> winding of a polygon as, well, winding() internally does.
>> 
>> IMO this is a mistake: the area() method should return the signed value and
>> let the user do the abs() WHEN and IF makes sense.
> 
> 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.

>  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.

Best

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com