Re: [boost] A design for geometric objects

Subject: Re: [boost] A design for geometric objects
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2008-11-14 09:46:40

Simonson, Lucanus J wrote:

> polygon_90_concept is the base most type of polygon.  It's corners are restricted to multiples of 90 degrees and its edges are axis-parallel.  It is the base most type because it is the most restricted.

Well, there is something wrong here.
The base type should be the less restricted one, not the most restricted 
one.

In my hierarchy, the base type is "Object" (in lack of a better name) 
which is a potentially infinite set of points. That's as less restricted 
as it gets, I'm sure.
Then Curve inherits from it, it is a "connected" set of points.
Then Polygon inherits from it (indirectly, there are a few useful things 
in between), then more restricted polygons, etc.

> polygon_90_with_holes_concept inherits from polygon_90_concept and extends the idea of an axis-parallel polygon with the ability to contain axis-parallel polygonal holes.

A polygon_90_with_holes is not a polygon_90. The inverse, however, is true.

Indeed, if you consider a polygon with holes as a polygon, you forget 
some information and the polygon with holes is not well represented anymore.
In the other direction, a polygon being considered as a polygon with 
holes is not a problem, it just happens to have a number of holes with 
is zero.

> polygon_45_concept inherits from polygon_90_concept, and extents the idea of an axis parallel polygon by allowing its edges to also be 45 degree sloping.

Same, if the angles are multiples of 45 they're not necessarily 
multiples of 90.
So a polygon with angles multiples of 45 is not a polygon with angles 
multiples of 90.

However, a polygon with angles multiples of 90 is a polygon with angles 
multiples of 45, so polygon_90 should inherit from polygon_45.

Your design fails to comply with the basics of subtyping: the Liskov 
Substitutability Principle.
As a result, you cannot write generic code, you are forced to specialize 
everything, even when it is not useful.

I would even say that it is broken beyond repair, since it cannot 
possibly support polymorphism.
The invariant of a base can (will) be broken by any type/concept that 
derives from it, rendering the whole hierarchy not only useless but also 
dangerous.

> Furthermore, we want to dynamically downcast the conceptual type of geometric data types.  If a polygon happens to be a rectangle, or convex, we can apply a much more efficient algorithm than in the general case.  In my library I might check if object that is tagged as polygon_concept might represent an axis-parallel or 45-degree polygon like so:
> 
> template <typename output_container_type, typename polygon_data_type>
> void polygon_concept::get_trapezoids(output_container_type& output, const polygon_data_type& polygon) {
> 	CONCEPT_ID id = concept_downcast(polygon);
> 	if(id == POLYGON_90_CONCEPT) {
> 		polygon_90_concept::get_trapezoids(output, polygon); return;
> 	} else if(id == POLYGON_45_CONCEPT) {
> 		polygon_45_concept::get_trapezoids(output, polygon); return;
> 	}
> 	//implementation of arbitrary angle slicing of polygon into trapezoids
> }
> 
> It's not perfect.  One of the major challenges is that the volume of code in the API is huge, and has an inertia that once implemented it is very labor intensive to change even a minor aspect of the design because the impact is global.  The revised library is 23 thousand lines of code--that's a mountain that I don't move lightly.

Well it doesn't even seem to be using the fact that the types are related.
Where is the static polymorphism in it?

Also, since you're taking the output as an argument, that necessarily 
means your objects are mutable. Which means doing the hierarchy the 
other way around can't work either, since the base can break the 
invariant of the derived.

You may want to read that article on Wikipedia:
http://en.wikipedia.org/wiki/Circle-ellipse_problem

Basically, inheriting an Ellipse from a Circle is always wrong, and 
inheriting a Circle from an Ellipse is wrong if the Ellipse view of the 
Circle is mutable.

> One annoyance is that I can't dispatch based upon a runtime value without enumerating possible values.  The only way to factor that out I can think of is with a macro, and I'm reluctant to use macros merely to save myself typing.  I don't want to move all dispatch to runtime for obvious reasons of lack of ability to inline leading to degraded performance.
> 
> The code also becomes very repetitive, especially where I have to duplicate functions.  As you said, making the library complete is an extreme challenge because the number of functions required scales super-linearly to the number of conceptual object types in the system.  Inheritance and static polymorphism of conceptual types helps some.  If only an arbitrary angle implementation of an algorithm is available, it can be implemented in the base polygon_90_concept and chosen by static polymorphism of the tags for all polygon data types that inherit from polygon_90_concept.
> 
> Clearly a similar design could be implemented based on SFINAE overloading instead of tag dispatching, but I have gotten the idea into my head that SPINAE overloading of template functions has a higher compile time cost than tag dispatching based overloading.  It seems unnecessary and wasteful to check and recheck that an object models a concept every time it is used.  It is also unclear to me how I would implement dynamic subtyping behavior based on runtime checks that downcast the conceptual type if I used SFINAE overloading unless I duplicated every SFINAE overloaded API with a non-SFINAE protected API that I could call in such cases.  That could be tedious.

No compile-time solution can possibly be as wasteful as a runtime linear 
branching (that even requires you to state all cases) as you gave in 
your example.