Re: [boost] Preview 4 of the Generic Geometry Library (ggl)

Subject: Re: [boost] Preview 4 of the Generic Geometry Library (ggl)
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-02-19 15:28:32

>> The library is really generic now, concepts are everywhere, as 
>> requested by the list before. It  can take any std::vector or range, 
>> as requested by this list.
>
> That's certainly very good, isn't it?
> So you can do retroactive modeling and everything.
True. External  (legacy) classes (points, lines, polygons, boxes) can be 
registered by traits classes and handled as if they were points etc. 
Ranges are working very good indeed.
>
>> It is coordinate system agnostic and dimension agnostic, as requested 
>> by the list.
>
> I wonder how it works. I hope the algorithms can still be written 
> generically, and don't have to be written independently for every 
> coordinate system.
The algorithms are generic and forward to strategies (which are normally 
different per coordinate system) where possible. For example the 
distance algorithm uses different strategies for spherical / cartesian 
distance. The simplify algorithm (using distance internally) is generic, 
is not per system.

In many cases it is possible to write code dimension agnostic, for 
example for the Pythagorean theorem. In other cases it is better to 
specialize it for its number of dimensions. For example the separating 
axis algorithm to check the intersection of 2 oriented bounding boxes in 
3D. The theorem makes it possible to solve the problem with "only" 15 
cross products. Even if it's still available in 2D, it can probably be 
written in a much more direct way. So it's reasonable to have sometimes 
2D, a 3D and a nD versions for a complete and efficient 
dimension-agnostic implementation.

To be complete: not all algorithms are implemented for 3D

Behind the screens the agnosticy works with "coordinate system tags" 
traits classes, binding strategies to them. For some strategies (e.g. 
transform) strategies are specialized by the number of dimensions as 
well. You'll see a lot of strategy specializations in the code, those 
are always specialized per tag, and sometimes per dimension.

> I also hope you didn't force yourself to too much agnosticism just 
> because it was requested on the list.
> People request lots ;).
Actually this abstraction was also very useful for ourselves, we're 
often working with both x/y and latitude/longitude and the way the 
library handles them now is also convenient for us.
>
> There seems to be a few inconsistencies in the documentation, Ring 
> says it checks the linestring concept, for example.
Thanks, this one is fixed
>
> Also, what a geometry is should be in the documentation of its 
> concept, not of its model (the model is the implementation of a concept).
> Of course, the documentation isn't really concept-centric at the moment.
There is a page about concepts on "Related pages" but you are right, the 
documentation will therefore be enhanced.
> The documentation of geometries isn't very clear, by the way. For 
> example, what's an nsphere?
> Is it the set of points which are at an equal distance of another 
> point, the center? (what a(n n-)sphere really is)
> Is it the set of points which are at an equal or inferior distance of 
> the center? (typically known as a ball)
> I would recommend clearly defining every geometry to prevent 
> ambiguities, in terms of set of points maybe, rather than referring to 
> a name which may have various meanings.
> In the same sort of thing, a polygon is not just the set of points 
> which are on its border, it's all the points that are within, too.
> The name "ring" lets me think it's just the border.
Documentation will be enhanced. In general we've used OGC/Egenhofer 
definitions, e.g. described in 
http://www.spatial.maine.edu/~max/RJ3.html 
<http://www.spatial.maine.edu/%7Emax/RJ3.html> where indeed geometries 
are handled as point sets.

About the n-sphere, ball, there was a discussion before on the list on 
this. It is actually handled in the same document of Egenhofer, by the 
definitions you give. So "within" within a sphere makes no sense, within 
a disk it does, the point is taken. n-sphere, n-disk...

True, polygon is the set of points within, plus border, whilst its 
borders are linear rings, not having an interior themselves. Internally 
that is not always handled consequently like this formal definition, a 
polygon consists of rings so the areas of rings are calculated and 
added/subtracted, which is conceptually wrong (the result is right...). 
So you are right, it is a good point (one of your set of good points :-) )

> I also just noticed the performance section. It doesn't really tell 
> what the other libraries are. And since GGL is so much more efficient 
> (by an impressive margin, actually), I recommend adding other 
> libraries to the benchmark: why not CGAL? That one should be a much 
> tougher competitor.
There are some more measurements to be done and more details will be 
added. Therefore I'll keep them currently anonymous. In the end we'll 
publish the comparison sources and details, it first has to mature a bit 
and be described better.  So you guessed CGAL is not one of them... It 
will be included, as it provides much or all of the algorithms tested, 
it is interesting indeed.
>
> How is the new selected algorithm much different from distance? It 
> seems it's either distance or within that is used, depending on the 
> geometry.
> Is there a use for this algorithm? It just feels kind of weird to me.
It can be very useful, but it is indeed weird in the sense that it is 
more pragmatical oriented than most others. Two reasons for it:
1) abstraction
2) performance
Abstraction: because in a collection of same-type-geometries you might 
select by a point, especially visually, on the screen you click on a 
point, line or polygon. However you might click one pixel away from it. 
By having the generic "selected" it either takes the point or linestring 
near by, or the point in which it is clicked. The enclosing entity (e.g. 
a 'layer') does not have to care about which geometry type it selects.
Performance: it is not really distance calculation here, as soon as in 
one dimension it is too far away a point (or linestring) is discarded, 
no more mathematics necessary then.

> Is concept refinement implemented? Is a Ring also a ConstRing and a 
> ConstPolygon?
A Ring is a ConstRing, yes. A (Const)Ring is formally not a 
ConstPolygon, by the definition you gave above...

We try to limit the geometries such that they are as orthogonal as 
possible. Basic geometires are point, linestring and polygon which are 
really mutually different (ignoring the linestring with zero length or 
polygon with zero area). In that sense the box for example is not 
strictly necessary: it is a polygon without holes and with 5 points, the 
last closing one the same as the first one. A segment is also not 
strictly necessary, it is a linestring with only two points. However, 
segment and box can hardly be missed in implementations. Besides that 
they are also very useful for the user. So although theoretically and 
formally they are too much, pragmatically they make a lot of sense.
So conceptually Box might be seen a refinement of a Polygon. In practice 
all algorithms for a box (keep in mind that Box here means an axis 
aligned box) are different. We've also defined different, pragmatic, 
access algorithms for it such as getting the min/max corners. And we 
didn't implement the polygon operations on it such as the outer ring, 
inner rings, etc because it makes no sense. So no, the Box in our code 
is not a refinement for a Polygon. The box was just an example but in 
the end: refinements seem not applicable (besides Const/non Const)

Regards, Barend