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