Boost logo

Boost :

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

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