[boost] A design for geometric objects

Subject: [boost] A design for geometric objects
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2008-11-12 23:41:08

The past discussions on geometric libraries focused on how to define 
points. What matters even more however is how geometric objects are 
designed.

There is a natural subtyping relationship between geometric objects. 
Deriving a square from a rectangle is usually frowned upon in OOP, 
because it can easily break the Liskov Substitution Principle if the 
objects are mutable.
Making them immutable, however, solves the issue altogether.

Morever, by using static subtyping, e.g. with concepts, we have multiple 
dispatch for free and don't pay any performance overhead, making such a 
design much better than with OOP.
Concepts being non-intrusive, a mutable object may well be implemented 
but the concept can be a read-only view.

Note that while I'm talking about concepts, I don't necessarily mean 
C++0x concepts, it could also be an alternative system.

I would like to be able to write generic algorithms for geometric 
objects. Say I write an algorithm for any simple polygon. That algorithm 
should work with any simple quadrilateral, simple triangle, a rectangle, 
etc.
Then I rewrite the same algorithm for convex polygons. So non-convex 
simple polygons should invoke the old algorithm, and convex ones the new 
one.
So a system to find best matches is required.

If we consider the subtyping graph for rectangle (which is not the most 
complex object, but certainly is complex enough to expose a complex 
graph), here is what we get:

Rectangle < Right-angled Trapezium < Trapezium < ConvexQuadrilateral
           < Parallelogram < Trapezium

ConvexQuadrilateral < SimpleQuadrilateral < Quadrilateral < Polygon
                     < ConvexPolygon < SimplePolygon

SimplePolygon < InsideSimplePolygonalLine
SimplePolygon < Polygon

Polygon < PolygonHole < Curve
Polygon < InsidePolygonalLine

InsideSimplePolygonalLine < InsideSimpleClosedCurve
InsideSimplePolygonalLine < InsidePolygonalLine < InsideClosedCurve

InsideSimpleClosedCurve < InsideClosedCurve < Curve
SimpleClosedCurve < ClosedCurve < Curve

InsideSimpleClosedCurve -> SimpleClosedCurve (composition thingy)
InsideClosedCurve -> ClosedCurve             (composition thingy)

Curve < Object

For clarification, a curve is here defined as the image of a continuous 
map from a real interval to the space. That is to say any set of points 
that is "connected".
A simple curve is a curve that doesn't cross itself (just like simple 
polygons), which means the the map is injective, and a closed curve is a 
curve where the application comes from a closed interval and where the 
image is the same on both boundaries. A closed simple curve is a closed 
curve that is injective but for the boundaries.
InsideClosedCurve defines the space with is "inside" a closed curve, 
which could also be defined by another map (known as a space-filling 
curve, but they are harder to manipulate, at least for polygons).
A Polygon is an InsideClosedCurve with the closed curve being line 
segments within a plan.
A PolygonHole is a Polygon which may have holes themselves defined by 
closed curves.
An Object is a possibly (likely, even) infinite set of points in space.

There is quite a complexity and redundancy here. It would be nice if it 
was possible to enhance that somehow.
And that graph probably isn't fully complete, for example "right-angled" 
should probably be made separate propriety from trapezium. Also there 
should probably be Polytope somewhere. And PolygonHole lacks 
specializations too.
The worse is the Inside thingies. I suppose having template concepts of 
some kind could help.

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.