Polygon Sponsor

Polygon Library Design Overview

The Polygon library uses C++-Concepts inspired template programming to provide generic library functions overloaded on concept type.  There are currently thirteen concepts in the Polygon library type system.  A concept object in the Polygon library is just an empty struct similar to a tag that would be used for tag dispatching.   These concepts are shown in the refinement diagram below.

The arrows between diagram bubbles show concept refinement relationships.  This is similar, but not identical to, inheritance relationships between normal classes.  A refinement of a concept narrows down the definition of a more general concept.  For example, the rectangle concept is a refinement of a polygon concept because it restricts the polygon to a four sided, axis-parallel, rectilinear figure.  A refinement of a concept is always acceptable to an API that expects read only access to a given concept, but never acceptable to an API that expects to write to that concept.  There are three types of geometry in the polygon library, the general case, the case restricted to angles that are multiples of 45 degrees, and the Manhattan/rectilinear case where angles are restricted to multiples of 90 degrees.   The refinement diagram shows that 90 degree concepts are refinements of 45 degree concepts, which are themselves refinements of the general case.  This allows the compiler to choose between the three implementations of algorithms to select the best algorithm for the conceptual data types passed to an overload of a function including heterogeneous combinations of 90, 45 and general case geometry.  To provide the operator& that performs the intersection on any pair of objects from the ten conceptual types related to each other through refinement in the diagraph above fully one hundred distinct combinations of conceptual types are supported by the library, but only three overloads are required to implement the operator (one for 90, one for 45 and one for arbitrary angle version of the intersection operation) because refinement generalizes the implementation of the interface.  In this way a fully symmetric, complete and internally consistent API is implemented to provide meaningful and correct behaviors for all combinations of argument types in all APIs where those types make sense.  For example, it doesn't make sense to copy data from a polygon into a rectangle, so attempting to do so yields a syntax error, while copying a rectangle into a polygon does make sense.  The assign() function that is used to copy geometry data between concepts instantiates for the 49 combinations of concepts that make sense, but not for the 51 combinations that are illegal.  The syntax error you will see when attempting an illegal assign operation is simple and clear because use of SFINAE by the library to overload generic functions means no matching function is found by the compiler in cases where no overload is provided.

error: no matching function for call to 'assign(rectangle_data<int>&, polygon_data<int>&)'

Associated with each concept is a traits struct that generally must be specialized for a given data type to provide the concept mapping between the interfaces of the data type and the expected behaviors of an object of that type required by the library.  The library also provides its own data types for each concept that conform to the default traits definition.  These library provided data types are no more than dumb containers that provide access to their data and rely on the generic library functions to enforce invariants and provide useful behaviors specific to their type of geometry that would normally be member functions of the data type in an OO design.  The library data types conform to the default traits associated with their related geometry concept and are registered as models of that concept.  When a data type has been mapped to a concept through traits it needs to be registered as that conceptual type with the library by specializing the geometry_concept meta-function.  Once mapped and registered, a user data type can be used interchangeably with library data types in the generic free functions that are overloaded on concept.

Traits for mapping a data type to a concept are broken down into mutable and read only traits.  Read only traits are specialized internally to work with any types that are refinements of a concept.  The mutable traits are defined only for objects that exactly model the concept.  Both read only traits and mutable traits need to be defined for a type to model a concept, but a type can be used without defining the mutable traits as long as no API that needs to modify the object is used with that type.  For example, a triangle type could be registered as a polygon_concept and the read only traits but not the mutable traits defined for that triangle type.  This would allow the triangle type to be passed into any API that expects a const reference to an object that models polygon. 

An object that is a model of a given concept can usually be viewed as a model of any of its refinements if it is determined at runtime to conform to the restrictions of those concepts.  This concept casting is accomplished through the view_as<>() function.  For example if an object of conceptual type polygon 90 has four sides it must be a rectangle, and can be viewed as a rectangle with the following syntax:

view_as<rectangle_concept>(polygon_90_object)

The return value of view_as<>() can be passed into any interface that expects an object of the conceptual type specified in its template parameter.  The exception to this ability to concept cast geometric objects is that polygon set objects cannot be viewed as individual polygons or rectangles.