Re: [boost] preview of a template geometry library

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

Bernd:

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  
algorithms.

Hope those considerations give you food for thoughts,
--
Hervé Brönnimann
hervebronnimann_at_[hidden]