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

From: Martin Lutken (mlu_at_[hidden])
Date: 2008-01-21 04:25:17

The reason I have 2D, 3D, 4D vector and matrices is to support as fast as 
possible 2D/3D calcutations for use in computer games graphis and physiscs 
simulations where every cycle counts. I Don't think that any game-engine will 
ever use generic N-vector, N-matrix types like those in UBlas....

-Martin L

On Tuesday 15 January 2008 22:46, Barend Gehrels wrote:
> 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
>
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost