[boost] [wykobi] Computational Geometry Plans??

From: John Femiani (JOHN.FEMIANI_at_[hidden])
Date: 2007-04-11 23:02:07

This is with respect to the discussion on a computational geometry
library (http://thread.gmane.org/gmane.comp.lib.boost.devel/145922).
That is before I discovered boost so I don't have an email to reply to. 

About 1 year ago, according to the dates on the boost vault, the wykobi
computational geometry library was posted in the vault.  The discussion
in the thread I cite above leaves me with the understanding that Arash
Patal's library was going to be submitted for review, and I understand
that that is still the case and He is trying to write a plan for the
development of the library, which currently resides in a GoogleCode
repository (http://code.google.com/p/wykobi/) 

I personally would like a boost-worthy and boost-licensed library for
computational geometry (CG), and it seems like after the prior thread
some ideas on a proper boost CG library were being tossed around.  I
want to post my comments on the wykobi version of a CG library here, and
hopefully revive interest and comments from boost folks on how this or
any library can be developed into a review-ready version as well. 

I like wykobi's functional style -- the library is not a complex and
hard to use collection of over-templatized classes. It seems to have
benefited from its Pascal-related history as FastGEO by evolving a
direct interface with a functional style.  It does not appear overly
bulky as I have seen one poster mention
(http://article.gmane.org/gmane.comp.lib.boost.devel/155129/match=wykobi
), in fact I wish the library had spatial indexing support such as
octtrees, quadtrees, or kdtrees (perhaps somebody wants to do a separate
spatial indexing or trees library). I also wish support for solid
geometry operations (intersection, union, etc.) for polygons was
supported.    

Wykobi seems to be a solid library, however I it needs work, and Arash
is currently drafting a plan for improving it for submission. I do not
know the details of Arash's plans, but here are the changes I personally
would like to see:  

1)  Neither this library nor the one or two others I had a chance to
check out and look over seem to have embraced concepts-based
programming. I really wish the various routines for ray-intersection,
area, triangulation, etc. targeted concepts rather than the slew
geometry classes.  For example the wykobi polygon class has _almost_ the
exact same interface as a vector of point. It would be much more
flexible if I knew whether I could just use a Boost.Range range data
type rather than the wykobi polygon class.  

2)  I would like to see more constructors; for example points should
have a constructor that takes a pair of coordinates. That seems simple,
but it makes it a lot easier to use. 

3)  The library seems to be decomposed into 3 parts; 2d, 3d, and nd
(n-dimensional).  Functionally I see the sense in this division, because
the complexity of the algorithms' implementation increases sharply as
the dimension gets higher.  I wonder, however, if that is a flexible way
to partition the library. From a syntactic point of view, point<float,
3> for a 3d point makes more sense that pointnd<float,3>, which is
similar but different then point3d<float>.  I suggest that the
primitives should all be developed consistently for n dimensions if
possible, and that the algorithms be generic enough to apply to tuples
and arrays.   Solid point and vector classes are important because I'm
sure a number of other boost libraries have re-implemented them in
limited form (indices, c_vector in uBlas, point_t in gil, etc.)

4) I know Arash is planning to remove the enumerations; which are a
relic of the libraries past.

5) I think that for fixed-size geometry the indexing operator ([])
should be toned down in favor of a template property accessor such as
get<0>(p), etc or get<wykobi::X>(p).  This gives a compile time error
when we attempt to access outside the range of the values the index --
at the cost of making it a harder to loop over the indices.  GIL for
example does this and provides static_for_each, static_transform,
static_generate, etc. algorithms. 

Thanx,

John C. Femiani