Re: [boost] preview of a template geometry library

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2008-01-30 00:24:26

Dear Bernd:  I started with a few quick notes (I really didn't do  
much more than glance at the documentation), which grew into a  
somewhat more extensive review - sorry, I've been thinking about  
geometric software library for a while now :)

I have many concerns/questions/suggestions with your library:

* If you treat a polygon as a sequence of points, you should really  
provide generic algorithms with iterators, with two algorithms for  
differentiating between closed and open polygonal lines.  There is no  
distinction and/or specialization of algorithm for (general)  
polygons, and special classes: monotone, convex, orthogonal, or  
orthogonally convex polygons, for which better algorithm often exist  
(simpler geometric primitive computation, better algorithmic  
efficiency, elimination of special cases, etc.)

* generally, for checking, testing, and for further processing, I  
found it a good idea to return a witness/certificate with your  
answers.  For instance, for the point in polygon test, if you use ray- 
shooting (upward), you could also return some information that  
identifies the edge immediately above the point (if inside).  For  
intersection detection (returning a bool if intersection), returning  
a point inside both polygons.  For distance computation, returning  
the two closest points between the closest features.  Most times, you  
already have this information without any overhead, making it  
optional allows the user to toss it away if they don't need it.  If  
there is an overhead in providing the witness, I would always provide  
two algorithms.

* definition of polygon:  is a polygon a boundary or a topological  
disk?  eg. do two nested polygons intersect?  Is there an  
intersection algorithm for polygonal *regions* or for polygonal  
*boundaries* only?  Seems that every algorithm on polygon would have  
two versions.

* naming:  within_point_in_polygon is not a good name.  I understand  
the desire to have all of them start with "within_" but  
is_point_within_polygon would read like English, at least.  As  Theo  
mentioned, having 2D somewhere in the name would also avoid deflated  
expectations from users.

* is point necessarily defined by two coordinates? (eg. how about  
intersection points - do they require computation or can I store two  
lines?) Is a box necessarily axis-aligned? Is a circle always defined  
by center and radius?  (e.g., how about a circle defined by three  
points?  do I have to invoke sqrt() thrice to compute center and  
radius or can I keep three points as definition?)

In general, you make broad assumptions as to your objects  
representations, which may not be very useful for users in different  
but very common settings (e.g. in meshing a 2D polygonal region,  
doing map overlays, motion planning in 2D).

* genericity: I find it very limiting that you're tying your concepts  
of points to 2d Cartesian coordinates.  This confuses the concept of  
geometry with that of representation.  I'm of course biased but I  
think CGAL got it right by defining kernels and predicates, and  
implementing algorithms solely based on kernels.  Your approach on  
the other hand does not clearly say what the *concept* of point is,  
compared to your implementation.  Defining concept by an archetype is  
not a good way to do it.

The addition of traits as a baggage grouping all fundamental types is  
a good idea, as does CGAL, but I think "traits" should be renamed  
"geometry", be the central concept, and define both types (points,  
lines, segments, etc.) and primitives (intersection of lines,  
constructing a line joining two points, etc.) and take it from  
there.  Grading geometries with several concepts (one with points  
only, one with lines, one with convexity - implying segments,  
polygons, etc.) would help to define minimal requirements for each  
algorithm.

In short, templatizing your existing geometry falls short (at least  
for me) in making it "generic".

* concerning the scope, 2d is somewhat easy especially with epsilon  
geometry.  This sounds like a naive approach.  In addition, this only  
speaks about a single geometry traits class, i.e., yours.  But since  
it is not quite clear what one has to provide to have one's one  
alternate geometric traits class, I don't know without looking at the  
implementation how much work it would be Please talk to Fernando who  
has offered to discuss with you the details of exact predicate.  Or  
read my former student Sylvain Pion's PhD thesis (now manager in the  
CGAL project). Or read Fortune and vanVyk's and/or Shewchuk's  
excellent landmark articles for 2D and 3D exact predicates using  
integral or floating point computation.

* more algorithms and more implementations:  you can find working  
code for many intersection / detection / distance computation in many  
books.  Perhaps the most relevant for your purposes is the excellent  
"Geometric Tools for Computer Graphics"  by Philip Schneider & David  
Eberly
(http://www.amazon.com/dp/1558605940? 
tag=softsurfergeomet&link_code=as3&creativeASIN=1558605940&creative=3734 
89&camp=211189)

In all truth and honesty, I for one would not vote in favor of your  
library for Boost,  and I suspect that many potential users would  
find it unnecessarily restrictive.  For the algorithms and primitives  
you supply, I do not see enough care in the design of your library  
besides the specific setting/implementation you intend it for.  This  
is what makes a boost geometry library a difficult proposition, imho,  
since there are many users of geometry out there, and all seem to  
require different performance -vs- exactness tradeoffs, genericity,  
coordinate models, algorithms, or all of the above.

Not that I've had success with it either (I had some hopes my student  
in his GSoC project would come up with generic representations of 2D  
subdivisions, but he was sick for the second half of the project, had  
to graduate, the usual excuses, not to mention my own excuses...  
well, he dropped the project midway).  At this point, I'm not sure I  
believe that there can be a geometry library in Boost, perhaps  
several libraries for their own respective domains (CGAL, graphics/ 
OpenGL, GDAL, GTL, OpenMesh, etc.) is the highest level of factoring.
--
Hervé Brönnimann
hervebronnimann_at_[hidden]
On Jan 29, 2008, at 4:34 PM, Barend Gehrels wrote:
> Hi,
>
> Herewith the URL to the preview of Geodan's Geometry Library,  
> including
> documentation and some examples.
>
> There are still implementation issues and algorithmic details to be
> figured out or to be implemented. This is a preview and not yet a real
> submission. However I think that the community will get a feeling  
> how it
> works and/or should work.
>
> The URL with documentation is here:
> http://geometrylibrary.geodan.nl/geometry.html and sources can be
> downloaded from that webpage.
>
> Best regards, Barend Gehrels
>
>
> -------------------------------------
> Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands,  
> www.geodan.nl
>
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/ 
> listinfo.cgi/boost