Boost logo

Boost :

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

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,
Then I rewrite the same algorithm for convex polygons. So non-convex
simple polygons should invoke the old algorithm, and convex ones the new
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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at