Re: [boost] Preview 3 of the Geometry Library

Subject: Re: [boost] Preview 3 of the Geometry Library
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-10-15 12:52:19

>About the default constructors debate: like Mathias I'd be inclined to
>have constructors that guarantee the integrity of any existing object
>and make checks useless, that's the choice I make in most cases. Luke,
>could you give some actual examples of cases where you found really
>annoying your legacy polygon class?

Ah, yes, I remember now.  It wasn't that it didn't have a default
constructor that was the real problem.  I removed the requirement from
my library that polygon be default constructible, but that didn't even
begin the solve the problems the legacy polygon caused me.  The problem
with the legacy polygon was that it had no constructor that would allow
me to create a non-rectangular polygon without it running a series of
checks on the input sequence of points that was horribly slow.  There
was a way to get data into it directly through a friend declared helper
class that encapsulated a list of points.  Once the data was in that
class I could call a make polygon member function of the helper class
which dynamically allocated the polygon and returned a bare pointer.
The effect was that it was impossible to construct the legacy polygon
efficiently without dynamically allocating it as well.  This made it
impossible to use the legacy polygon as an element of a std container
efficiently.  Upon reflection, I could use the constructor that took a
rectangle, dynamically allocate a polygon, assign it to the first
polygon and delete the dynamically allocated polygon.  Really annoying,
but not because it didn't have a default constructor.

Sorry for the confusion.

Back to the issue of default vs. non-default constructible polygons, I
believe that while the boost geometry library may choose to define a
polygon data type that may not be default constructible, it cannot make
that choice for legacy polygon types.  We have to assume that the
library's generic interfaces will work with polygons that are default
constructible and that the library's algorithms need to be implemented
in a way that is robust to all kinds of things that might normally be
considered an invariant of a well designed polygon class.  For instance,
it is a common practice to make the first and last point in the sequence
of points that represents a polygon be equal to eachother to show that
it is a closed figure and not a line string.  We have to assume that it
may or may not be the case and handle either if we are going to have a
generic concept of polygon that works with legacy data structures.
Similarly, it is often assumed that a certain winding convention is used
with a point sequence that represents a polygon.  The algorithms must
either be informed of the winding direction or compute it.

Other common invariants of a polygon class include that there be no zero
length edges or collinear edges described by the points in the point
sequence.  These also cannot be relied upon if we provide a generic
interface to unknown polygon type.  The library should not be dividing
by zero in these cases.

I don't, frankly, believe that there is a meaningful runtime overhead
incurred by performing the checks necessary to ensure that algorithms
are invariant to these cases.

Similar to polygon, rectangle (axis aligned rectangle, mind you) classes
also have invariants they like to provide.  Specifically, a rectangle
defined by a pair of points usually guarantees that one point is less
than the other in some geometric sorting order of points.  A generic
interface that accepts arbitrary rectangles can't really depend on the
class being defined this way, so I made the interface enforce my own
invariant.  My generic interface gets and sets the horizontal and
vertical intervals of an unknown rectangle type.  The interval itself
enforces the invariant that its low end is less than or equal to its
high end.  I assume that user defined rectangles may be default
constructible, and furthermore, that default constructed rectangles may
contain garbage data.  I, therefore, don't have a concept of an "empty"
rectangle.

Luke