Re: [boost] preview of a template geometry library

From: Barend Gehrels (barend_at_[hidden])
Date: 2008-01-30 05:23:44

Dear Hervé,

Thanks for your extensive review on my preview...

Maybe I should have stated more clearly that I'm a geographer and built 
this library from a GIS perspective. We (at least in my company) 
normally do not distinguish between polygon types, for example.

Therefore, as in my other mail, we might change the namespace to 
"geospatial" or to "geospatial2d" to make this more clear.

For the rest I put my comments between yours.

Hervé Brönnimann wrote:
> 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.)
>   
I agree that some algorithms are better for, for example, convex 
polygons. However, we didn't make a distinction indeed. It is normally 
not done in GIS systems. The states of the US, for example, are polygons 
of which some might be convex. However, if you edit a convex polygon by 
adding one point it might result in a non convex one. We could add a 
flag "is_convex", however (until now) we didn't do that and see the 
polygon as one or more series of linear rings.
Polygons are or should always be closed, it is a "surface", having an 
area. An "open polygonal line" is a linestring in our case. Or maybe I 
do not understand you completely.
> * 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.
>   
Interesting, actually we did this thing in the intersection of segments 
and you are right, the information is often there. However, I think you 
should also provide generic alternatives, calling those witnessed 
functions, but without that information because to be honest, I have 
never needed the edge above the point in a point-in-polygon case.
> * 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.
>   
I think that it is not clear enough in the documentation then: a polygon 
is a polygonal closed region, a surface, an open polygonal boundary is a 
linestring. The intersection of two polygons deliver a multi_polygon. 
The intersection of two linestrings (being closed or open) delivers a 
multi_point or actually a (not defined) multi_geometry (points and maybe 
line segments in collinear cases)
> * 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.
>   
Good idea. We designed it like this: all algorithms start with the OGC 
name, so "within" in this case and "intersection" in another case. But 
your name is probably more clear indeed. However, the name 
"point_in_polygon" is also very common, and "within" is justed prefixed 
there. I also thought about putting all those algorithms in the 
namespace "within" but we have to find another name for the function 
"within" then.
> * 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?)
>   
The circle is there because of circle-selections (selecting points, 
lines or polygons falling completly within circles), we do not other 
things with it, sorry. Maybe we should have omitted in our library but 
because we had it and need it ourselves we kept it there. There are 
indeed no circles defined by three points or other circle algorithms in 
this library.
> 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.
>   
Good point, the "concept" documentation and implementation must be 
better. We didn't plan to rebuilt CGAL because it is already there. This 
is another library and more directed to GIS systems and therefore, as 
said above, we will probably rename the namespace to "geospatial::". It 
is more clear then.
> 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. 
OK
> 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)
>   
Thanks for the suggestions

> 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.
>   
I didn't expect vote intentions at this time but, however, I'm glad with 
it. Making the preview took more time than planned and if many people 
would vote negatively I would rather not submit (but let's first wait 
for other reactions.). I agree with you, I always look at the geometry 
from a GIS perspective but there are ways more to do it, and needs for 
other geometries or 3D or whatsoever. However, we will not implement  
those things as we don't need them and have not enough spare time / 
experience.

> 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.
>   
Maybe indeed more geometry libraries would be convenient because I think 
it is better to have two than none of them. I really miss things as 
point-in-polygon or area in boost, things which are very common and 
scattered over the internet but not yet in boost.

Thanks again for your comments.
Barend

> --
> 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
>>     
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>
>
>
>   

-- 
-------------------------------------
Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl