Re: [boost] Is there any interest in a template geometry library?

From: Barend Gehrels (barend_at_[hidden])
Date: 2008-01-15 16:46:43

Hi Martin, Fernando,

Thanks for your answers.

Martin, thanks for your suggestion about cpaf, I can imagine that the 
job was large. Your library is different and probably planned larger 
than the one we propose, and contains different things. We for example 
have no vector and matrix definitions nor implementations, if we need we 
would use for example boost/UBLAS. On the other hand we have polygons 
with holes and corresponding algorithms.

Fernando Cacciola wrote:

 >Hi Barend,
 >  
 >
 >>Hi,
 >>
 >>Is there any interest in a template geometry library?
 >>
 >Depends on the details ;)
 >  
 >
Details will follow next week, I'll post a sort of preview including 
sources, some examples and some documentation. I shortly answer your 
questions below.

 >>Data and algorithms are separated, so there are algorithms like:
 >>template <typename P, typename POL>
 >>bool point_in_polygon(const P& p, const POL& pol);
 >>
 >What algorithm is implemented for this function?
 >  
 >
Both crossing number and winding rule are implemented, besides that, you 
can implement your own if necessary (there is a "for_each_segment" 
algorithm which walks through segments, like std::for_each). The 
crosscounting is in the library since '95 and should be considered as 
thoroughly tested, however, we used it mainly for interactively 
selecting polygons in GIS applications. Winding rule algorithms are
generally available on the internet, in this library it is just 
implemented and comparisons (e.g. speed) have still to be done.

 >How does it handle robustness issues?
 >
 >What are the geometric requirements on the input polygon? (i.e. must be
 >simple? strictly simple?)
 >What if the point is exactly *over the boundary* of the polygon?
 >  
 >
Good questions, polygons are considered as in OGC, simple, their outer 
ring and inner rings (if any) should not be (self)intersecting. We 
consider the point-in-polygon as a case of the more generic "within"
relation between two geometries and that is defined as "TRUE if g1 is 
completely contained in g2.", for "Within(g1 Geometry, g2 Geometry)", 
see e.g. OGC's 99-049 http://www.opengeospatial.org/standards/sfs. I 
will come back on this.

 >>And like this:
 >>template <typename S1, typename S2, typename MP>
 >>intersection_result intersection_segment(const S1& segment1, const S2&
 >>segment2, MP& multipoint);
 >>
 >What is a multipoint?
 >  
 >
See 99-049 above or see for example 
http://dev.mysql.com/doc/refman/5.0/en/opengis-geometry-model.html. One 
of the reasons the multi versions are there is that, for example, 
clipping a polygon might result in a multi-polygon.

 >What if the segments are collinear (hence their intersection is another
 >segment)?
 >
 >How does it handle robustness issues?
 >  
 >
This is handled, the intersection_result gives information about how the 
segments intersect. If the intersection is another segment a multi-point 
containing two points are delivered, plus a  "is_collinear" result.

I've seen on your website that you co-develop CGAL. Don't expect 
something like CGAL here, compared to CGAL this library relatively 
basic, small and simple. However, I think it will fit in the boost
libraries and concepts and therefore we considered proposing it.

Best regards, Barend Gehrels
Geodan Holding B.V., Amsterdam, The Netherlands