Re: [boost] A design for geometric objects

Subject: Re: [boost] A design for geometric objects
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-11-13 13:15:29

Mathias wrote:
>Therefore I am wondering if there is any way to make the design simpler 
>and more elegant.
>Indeed, such a design seems hard to maintain, it doesn't scale so well, 
>and if I want to include something in there I probably have to modify 
>other concepts as well.

>A geometric object is really just a set of proprieties. Working with 
>meta-functions like is_quadrilateral, is_convex or is_simple seems like 
>less work and verbosity.
>But how can such a system provide subtyping and best matches?

>Any comments and ideas are welcome.

Thank you, Mathias, for raising these questions.  I have been playing with subtyping of tags that indicate the conceptual type of a geometry object.  In this way I can achieve static polymorphism of templated geometry data structures.

A good example of such an object hierarchy of tags is the polygon tags I have created for my library:

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.

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.

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.

polygon_45_with_holes_concept cannot inherit from both polygon_90_with_holes_concept and polygon_45_concept because the multiple inheritance semantic in C++ lacks utility.  I inherit it from polygon_45_concept and am forced to overload functions in the library to make it appear that polygon_90_with_holes_concept and polygon_45_with_holes_concept have static polymorphism.

similarly polygon_concept inherits from polygon_45_concept allowing arbitrary angle corners and edges and polygon_with_holes_concept inherits from polygon_concept and I have to again overload functions to achieve the appearance of static polymorphism in the library.

Now consider an algorithm such as one that slices a polygon into trapezoids.

template <typename output_container_type, typename polygon_data_type>
void get_trapezoids(output_container_type& output, const polygon_data_type& polygon);

We wand to select the most efficient algorithm for the type of polygon provided.  There should be several implementations that depend upon the conceptual type of the input polygon.  These are accessed through get_trapezoids dispatch functions.  I make them static members of the tag struct

struct polygon_concept {
        template <typename output_container_type, typename polygon_data_type>
        static void get_trapezoids(output_container_type& output, 
                                            const polygon_data_type& polygon);
};

and dispatch to them by looking up the conceptual type

template <typename coordinate_data_type>
struct geometry_concept<polygon_data<coordinate_data_type> > { 
        typedef polygon_concept type;
};

and then accessing its static member function that implements the algorithm.  This produces pleasing error msgs when such function is not provided:

error: no function get_trapezoids in struct rectangle_concept

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.

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.

Regards,
Luke