Boost logo

Boost :

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2008-01-31 08:37:01


On Jan 30, 2008, at 5:23 AM, Barend Gehrels wrote:
> Dear Hervé,
> Thanks for your extensive review on my preview...
> Maybe I should have stated more clearly that I'm a geographer and
> built
> this library from a GIS perspective. We (at least in my company)
> normally do not distinguish between polygon types, for example.
> Therefore, as in my other mail, we might change the namespace to
> "geospatial" or to "geospatial2d" to make this more clear.

I agree that names of entities of your library (never heard of a
linestring outside GIS, for instance) is slanted towards geospatial.
However, many of the algorithms such as intersection, distance,
convex hulls, etc. are much more general than that. I wonder if you
could isolate the geometry part better without geospatial in mind,
and perhaps have your own geospatial layer on top (in or out of
boost). After all, it's it's truly generic, you shouldn't have
problems / performance loss using it in your context. But I think
it's not a good idea to craft a general-purpose geometry with names
that belong to a particular domain.

> For the rest I put my comments between yours.
> [snip]
> Maybe indeed more geometry libraries would be convenient because I
> think
> it is better to have two than none of them. I really miss things as
> point-in-polygon or area in boost, things which are very common and
> scattered over the internet but not yet in boost.

I agree that there definitely is a place for those oh-so-basic
algorithms. But to be truly generic and useful to the maximum number
of people, you should think about what there algorithms *require*.

For instance, for area, all that is needed is the area of a triangle,
and even (if it can be implemented more efficiently) the third point
can be the origin (or a reference point). If the user can supply
that primitive, there is no need to require coordinates, and indeed
your area algorithm will work with latlong points, or in any other
system of reference. (I've never thought how to compute the area of a
triangle on the sphere, and it can't be too simple, bu surely there
is a formula). The point (pun intended) is that you can decouple the
algorithm from the geometric computation, and separately provide the
computation for Euclidean, latlong, whatnot spaces. It makes the
library much more useful.

For convex hull, to take another example, all that is required is
some notion of extremum (e.g. in x- or y- direction) and the
orientation of three points. If you can compare points by some
coordinate or somehow order them in an order that's compatible with
the hull (i.e., makes any convex polygon monotone for that order),
you're in business. I do not need to know how (i.e., with what
specific formula) you compute the orientation or order the points.
Here we are talking about an oriented space. Its a requirement that
you did not have in the area computation (well, in fact you must have
had it underneath, otherwise there would be no notion of inside/
outside, but the software requirement is different).

This is not quite the direction that CGAL took, in fact it pushes
their position a bit further because they have a monolithic kernel
(as a concept, or set of requirements) that doesn't separate those
requirements due to orientability, or area/metric computations, from
e.g., the ability to define circular objects, to having specialized
computations like in-circle testing. Otherwise, they already have
the separation of representation (x,y in cartesion or lat,long in
spherical or x,y,w in homogeneous coordinates) from the geometric
predicates. And that I argue is a very desirable thing for a generic
(i.e., maximally reusable) library.

As for interaction with boost.gil, I am not familiar, and their
documentation does not really do a good job at expressing concepts.
But surely it's easy to write area_triangle(p,q,r) or
area_reference_triangle(p,q) and orientation_triangle(p,q,r) in a way
that require gil::Point2DConcept<Point>. Then you can reuse your

Hope those considerations give you food for thoughts,

Hervé Brönnimann

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