Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk