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