Boost logo

Boost :

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2007-10-04 13:40:21


> GTL is a geometric library that implements basic rectilinear, fixed
> point 1D, 2D and 3D types.

I think most readers here don't know what "rectilinear" means.
Most likely, they will simply ignore the qualifier even though is central to
the nature of this library.
I also think most readers don't what "isotropic API", "directional types",
etc means.

In the presentation below you assume the reader is familiar with this type
of geometry, its core concepts and operations.
But I'm sure most people here don't, even worse, know it *differently* and
will misunderstand the library..

So, what are the core concepts of this type of geometry?

> * parametrized fixed-precision cartesian coordinates

What is parametrized exactly?

> * massive capacity

What does this mean?

> * isotropic API

And this?

I could extrapolate what you mean by "isotropic API" from the examples
below, but then I'm curious why you call it isotropic?

>> Implemented Rectilinear Types
>> =========================================
>> 1D Types: Interval

Is this a geometric primitive or a numerical primitive, or none?

(see Boost.Interval)

>> 2D Types: Point, Segment, Rectangle, Polygon, PolygonSet
>> 3D Types: Point3D, Segment3D, LayeredRectangle, RectangularPrism
> Polygons
> ========

"Polygons" here mean the layout of primitive rectangles right?

> This is by far the most algorithmically advanced type and
> functionality
> that we have.

> 1. full set of boolean operations on polygon sets (or, and, subtract,
> xor, etc)

Here is an important question:

What algorithm do you use?
Isn't it dependent on the central fact that polygons are the overlay of
rectangles? Doesn't the algorithm decompose a poygon in rectangular regions?

If yes, then is important to state that this library probably won't scale
nicely to general polygons.

> 2. runtime (all n*log(n) or better) - it is at par or better than
> other implementations that we're aware of

How do you handle the robustness of clipping? Is it based on the fixed-point
arithmetic alone or there is something else?

> 5. providing polygon set type that's complete

complete means that operations are regularized? (that is that you never
returned an "invalid" polygon having a region with no interior, like an

> std::vector<gtl::Rectangle> v;
> c.get(v); // populate v with the vertical rectangles that make up c
>> Isotropy
>> ========
>> A variety of directional types in 1D, 2D, 3D with states like: LOW,

What is a directional type and what those constants mean?

>> A set of operations on these types like: forward(), backward(),
>> toward(), left(), turn(), perpendicular(), etc.

Which do what?

>> All API functions are isotropic, i.e. they take arguments of
>> directions/orientations.
> None of the function names contain words
>> like X, Y, Up, deltaX, horizontal, etc. With isotropy, you can do
>> elegant things like:
>> // example 2
>> gtl::Rectangle a, b;
>> // bloat rectangle of a toward rectangle b by b's half delta in that
>> orientation
>> // do nothing if no trivial direction from a to b exists
>> a.bloatInDirection(a.toward(b),;
>> Writing this example in a non-isotropic fashion requires much more
>> lines of code, lots of if statements, four to eight different
>> scenarios, etc. Much more code, much less readable, not flexible at
>> all.
My un-informed (so far) opinion is that this interface looks a bit bloated
and that it can probably be factored out better.

Have you considered separatring vectors from points? (and categorizing
vectors as normals, directions, etc)


Fernando Cacciola

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