Is there any interest in a template geometry library?
Hi, Is there any interest in a template geometry library? The library we are developing is basic 2D geometry library. In this library, data structures are small and simple (but polygons can still have holes). Nevertheless, the library provides a lot of useful algorithms such as point-in-polygon, line intersections and polygon clipping. We at Geodan are developing our library since 1995, and recently restructured, simplified and enhanced the geometry core. Now that it is clean and well designed, and still with years of experience, we aim to publish it in Boost under the Boost Software License. To give some impressions, points are like this: template <typename T> class point { (...) inline const T& x() const (...) inline const T& y() const (...) }; and lines are completely empty, like this: template <typename P> class linestring : public std::vector<P> { }; (Besides that you can also specify another container). 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); and like this: template <typename S1, typename S2, typename MP> intersection_result intersection_segment(const S1& segment1, const S2& segment2, MP& multipoint); but also generic wrappers like a "within" algorithm which is defined for all relevant geometry types template <typename P1, typename P2> inline bool within(const P& p, const polygon<P2>& poly) Because the library is completely templatized, you can use your own geometry types, and/or container types (provided that they follow the basic interface). The library follows std:: and boost:: standards and conventions, as well as the OGC (The Consortium on Standards in Geographical Information Systems) conventions. I know there have been discussions before on geometry libraries and on CGAL, e.g. http://lists.boost.org/Archives/boost/2007/03/117582.php. We are using boost in our library since about 2000. If there is interest I will complete the documentation and examples according to Boost standards, and prepare a submission. Barend Gehrels ------------------------------------- Barend Gehrels ------------------------------------- Geodan Holding b.v. President Kennedylaan 1 1079 MB Amsterdam, the Netherlands ------------------------------------- E-mail: barend.gehrels@geodan.nl Website: www.geodan.nl -------------------------------------
I will greatly appreciate this type of library in Boost. Marc
-----Message d'origine----- De : boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] De la part de Beman Dawes Envoyé : mardi 15 janvier 2008 02:26 À : boost@lists.boost.org Objet : Re: [boost] Is there any interest in a template geometry library?
Barend Gehrels wrote:
Hi,
Is there any interest in a template geometry library?
Yes, at least from me:-)
--Beman _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Folks, Thanks for your answers. This reply answers them.
How about is your experience now? How long to publish the library? I want to have a sight on the library as soon as possible. There are more answers possible. I'm busy with the samples and documentation. I can do a preview post next week or so.
The library, in OGC sense, is not complete. However, we already use it since 1995 like this and do not miss the things which are not there. But if the library is a candidate for Boost we might consider add some or even all missing features. However, that will take some time and will influence the timeframe of course. For example: the algorithm "distance", prescribed by OGC, is implemented for point-point and for point-line, of course, but not yet for point-polygon, multipoint-polygon, etc. There are 6x6 combinations for the 6 OGC geometries (point,line,polygon,multi-point,multi-line,multi-polygon). So 6x6 cases for all algorithms on two geometries: distance, disjoint, touches, crosses, within, contains, overlaps, intersection, union and difference. This delivers 6x6x10=360 methods, however, some have some overlap or are easy (contains(a,b) = within(b,a) ) [Malte]
a few weeks ago, the authors of the "geometric template library" asked the same question I had seen the GTL but not this posting. GTL is another library than this one. There is not much overlap. In Boost documentation a section "other libraries" is often there and I will include the differences with GTL there.
[Niitsuma]
Basic Image AlgorithmS C++ Library (BIAS)
This is interesting, but this is also another library. It is huge and I would need more time to compare, but I think there is not much overlap too here. Is BIAS a boost candidate? There are more libraries: TGL (another template library, which has some more overlap, but still has a different approach), CGAL I already mentioned, GDAL, GEOS, GFC and some inside larger libraries as Mapnik, and some more specific as the polygon clipping library. I will mention them in the "other libraries" section. [Marc]
I will greatly appreciate this type of library in Boost. That is nice to hear and I agree, it should be there.
[Malte]
I'm particularly interested in clipping generic 2D polygons Clipping 2D polygons against rectangles is in the library, using the Weiler Atherton algorithm. This could be extended to other polygons, the algorithm supports that.
Generic polygon triangulation would be a plus Is not included at this moment.
Do you have any timeframe for the publication of your library? As above, I try to do a preview next week, and depending on the interest and process I think May 08 should be feasable.
Barend Gehrels Beman Dawes wrote:
Barend Gehrels wrote:
Hi,
Is there any interest in a template geometry library?
Yes, at least from me:-)
--Beman _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I made something two years ago, but did not have the time to do it all on my own. But You are welcome to take a look. It has all the basic types v2, v3, v4, m22, m33, m44, g44 http://cpaf.sourceforge.net/cpaf/cpaf_libs/math/math0_dir_description.html It is of any use go ahed. It's well documented and commented. I moved the source code here: https://cpaf.svn.sourceforge.net/svnroot/cpaf/trunk/cpaf/cpaf_libs/math/ -Martin Lütken
Barend Gehrels wrote:
Is there any interest in a template geometry library?
a few weeks ago, the authors of the "geometric template library" asked the same question (search for "GTL", http://tinyurl.com/2vftbb ). Since I guess that the supposedly outstanding speed of the GTL is not required by most who signaled interest, I assume that many would happily use your more generic library. FWIW, I'm particularly interested in clipping generic 2D polygons. I have to process GIS data for our landscape visualization research project, so the OGC conventions are already followed in most of our existing code. Generic polygon triangulation would be a plus, but I still don't know whether we'll really need it. Do you have any timeframe for the publication of your library? I have to find one by May 08, so I'd really appreciate if you could upload an initial version to the Boost sandbox in Q1/08. Malte
2008/1/15, Malte Clasen <news@copro.org>:
Barend Gehrels wrote:
Is there any interest in a template geometry library?
Basic Image AlgorithmS C++ Library (BIAS) http://www.mip.informatik.uni-kiel.de/tiki-index.php?page=BIAS have various geometric functions
Hi Barend,
Hi,
Is there any interest in a template geometry library?
Depends on the details ;)
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? 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?
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? What if the segments are collinear (hence their intersection is another segment)? How does it handle robustness issues? Best -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
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
Hi Barend,
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.
OK. I'm looking forward to seeing the code then.
How does it handle robustness issues?
Since you haven't answered this question I pressume that it doesn't handle robustness issues at all.
Or the question wasn't clear enough so let me reprhase it: What if I'm using 'double' as the coordinate type and I test containment of a point which happens to be a tiny epsilon away from a vertex? That is, is the library sensitive to roundoff? If so, this can be a problem considering that techniques to handle this exists and are implemented for instance in CGAL. AFAICT, there is the presumption that roundoff problems are imposible or impractical to handle so a library should just ignore them. That's not correct. In C++, they can be easily handled for a usable subset of the typical geometric computations (the so called predicates). See: http://www.cgal.org/philosophy.html
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.
Can a user determine the "validity" of a 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,
In scope, certainly, I wouldn't. But I expect any geometric computing library, regardless of its extension, to implement the fundamental techniques of the field. In particular, those aimed to isolate users from numerical issues.
compared to CGAL this library relatively basic, small and simple
If the library *unnecesarily* fails to produce correct results because of numerical issues then it's not 'simple' but 'simplistic'. Please don't get me wrong, I keep turning down libraries for this very reason over and over not becasue I'm biased toward CGAL but because the proper techniques have been around for years, so I see little justification in ignoring them, pushing the burden on end users, unnecesarily. The following recent discussion illustrates the importance of properly handling robustness issues in geometric computing http://tinyurl.com/2os9co Best -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
Hi Fernando, Fernando Cacciola wrote:
Hi Barend,
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.
OK. I'm looking forward to seeing the code then.
How does it handle robustness issues?
Since you haven't answered this question I pressume that it doesn't handle robustness issues at all.
Or the question wasn't clear enough so let me reprhase it:
What if I'm using 'double' as the coordinate type and I test containment of a point which happens to be a tiny epsilon away from a vertex?
That is, is the library sensitive to roundoff? If so, this can be a problem considering that techniques to handle this exists and are implemented for instance in CGAL.
AFAICT, there is the presumption that roundoff problems are imposible or impractical to handle so a library should just ignore them. That's not correct. In C++, they can be easily handled for a usable subset of the typical geometric computations (the so called predicates).
See:
Thanks for the clarification. The library uses the epsilon for floating point comparisons. Your will see it next week, but it is like this: inline bool operator==(const point& other) const { if (std::numeric_limits<T>::is_exact) return m_x == other.m_x && m_y == other.m_y; else return abs(m_x - other.m_x) < std::numeric_limits<T>::epsilon() && abs(m_y - other.m_y) < std::numeric_limits<T>::epsilon(); } If this approach is not enough, you can please help us to make it more robust because I agree, the library should handle these issues and not the user because that is not possible.
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.
Can a user determine the "validity" of a polygon?
OGC defines the method isSimple for this, there will be an algorithm is_simple.
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,
In scope, certainly, I wouldn't.
But I expect any geometric computing library, regardless of its extension, to implement the fundamental techniques of the field. In particular, those aimed to isolate users from numerical issues.
compared to CGAL this library relatively basic, small and simple
If the library *unnecesarily* fails to produce correct results because of numerical issues then it's not 'simple' but 'simplistic'.
OK, tell me next week if it is bright and simple or just simplistic, I'm curious.
Please don't get me wrong, I keep turning down libraries for this very reason over and over not becasue I'm biased toward CGAL but because the proper techniques have been around for years, so I see little justification in ignoring them, pushing the burden on end users, unnecesarily.
The following recent discussion illustrates the importance of properly handling robustness issues in geometric computing
Best
Best regards, Barend Gehrels, Geodan Holding B.V., Amsterdam, the Netherlands
Hi Barend,
See:
Thanks for the clarification. The library uses the epsilon for floating point comparisons. Your will see it next week, but it is like this: inline bool operator==(const point& other) const { if (std::numeric_limits<T>::is_exact) return m_x == other.m_x && m_y == other.m_y; else return abs(m_x - other.m_x) < std::numeric_limits<T>::epsilon() && abs(m_y - other.m_y) < std::numeric_limits<T>::epsilon(); }
If this approach is not enough
Indeed, is not enough.
you can please help us to make it more robust because I agree, the library should handle these issues and not the user because that is not possible.
Yes, I can help you. The very first thing you need to do is understand the problem and why that approach is insufficient. Have you read the sample discussion I posted before? that should get you started. http://tinyurl.com/2os9co
If the library *unnecesarily* fails to produce correct results because of numerical issues then it's not 'simple' but 'simplistic'.
OK, tell me next week if it is bright and simple or just simplistic, I'm curious.
You are using the so-called epislon-geometry approach, so I can tell you now: this is simplistic ;) Feel free to contact me directly if you want, though it might be interesting to discuss it on the list becasue this is not a problem specific to geometric computing but any computing sensitive to round off. Best -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
Hi Fernando, Fernando Cacciola wrote:
Hi Barend,
See:
Thanks for the clarification. The library uses the epsilon for floating point comparisons. Your will see it next week, but it is like this: inline bool operator==(const point& other) const { if (std::numeric_limits<T>::is_exact) return m_x == other.m_x && m_y == other.m_y; else return abs(m_x - other.m_x) < std::numeric_limits<T>::epsilon() && abs(m_y - other.m_y) < std::numeric_limits<T>::epsilon(); }
If this approach is not enough
Indeed, is not enough.
you can please help us to make it more robust because I agree, the library should handle these issues and not the user because that is not possible.
Yes, I can help you. The very first thing you need to do is understand the problem and why that approach is insufficient.
Have you read the sample discussion I posted before? that should get you started.
OK, thanks for your offer. Let me first finish the preview, it will take me too much time if I dive into this at this moment. I glanced through the discussion and to the philosophy page of CGAL, thanks.
If the library *unnecesarily* fails to produce correct results because of numerical issues then it's not 'simple' but 'simplistic'.
OK, tell me next week if it is bright and simple or just simplistic, I'm curious.
You are using the so-called epislon-geometry approach, so I can tell you now: this is simplistic ;)
Feel free to contact me directly if you want, though it might be interesting to discuss it on the list becasue this is not a problem specific to geometric computing but any computing sensitive to round off.
Thanks again, I surely will come back to this. Barend Gehrels. ------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl
Hi Barend,
OK, thanks for your offer. Let me first finish the preview, it will take me too much time if I dive into this at this moment. I glanced through the discussion and to the philosophy page of CGAL, thanks.
No problem. Just make sure to top-post a message so it doesn't get lost in this thread. Best Fernando
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
On Monday 21 January 2008 04:25, Martin Lutken wrote:
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....
I don't see any reason having a generic interface has to impose any runtime overhead. In the worst case, you could make the dimension a template parameter and provide partial specializations for whichever dimensions you have specially optimized code for. -- Frank
Barend Gehrels wrote:
Is there any interest in a template geometry library?
There certainly is. My particular interest is in efficient containers for points (and perhaps lines) with iterators over 2D ranges; have you done anything like that? Some random thoughts: Of course you're aware of the GTL proposal from a group at Intel last year. Here is my recollection of a couple of aspects of that discussion: - It turned out that their implementation uses a cast from a base class to a derived class, which works because the derived class has the same layout as the base class in all known compilers. This is a pragmatic choice, but it's not the sort of thing that's going to be popular with Boost people as the list discussions revealed. Unfortunately, because their library is complete and in use, they're too far down the road to change something as fundamental as that. When I read "We at Geodan are developing our library since 1995", I was immediately worried that your library would also turn out to have some unpopular feature at its core, now impossible to change. So letting us see the code ASAP is definitely a good idea. - A feature of GTL is that it can accommodate arbitrary point types by means of suitable adapters. I had mixed feelings about this. On one hand, this makes it possible to apply their algorithms to legacy data structures. On the other hand, I think that it would add an extra layer of complexity for new users who have no legacy to worry about (and library learning-curve steepness is something that I give a lot of weight to). Compare this to the standard library: using maps I often find myself writing "first" and "second" when I'd prefer to be writing "key" and "value" or "customer_number" and "address". If std::map could be adapted to work with arbitrary structs, rather than std::pair, that would be a good thing. So maybe we do need this extra layer. Except that it might make coding the libraries more complex, and my space-filling-curve point-set was at the limits of my C++ ability already! Indecision. Considering GTL, this library, GIL, and even CGAL, how much commonality is there? Are there shared concepts between all of these libraries? Can we extract some common concepts or patterns from the different libraries? Perhaps something that's also worth asking is whether Boost is the right place for such a library. Getting releases out has not been a smooth process over the last couple of years, and I can't imagine that adding more libraries makes it any easier. Maybe Boost ought to focus more on things that are close to the standard library, and let other code find a home elsewhere. Regards, Phil.
Phil,
Phil Endecott wrote:
Barend Gehrels wrote:
Is there any interest in a template geometry library?
There certainly is. My particular interest is in efficient containers for points (and perhaps lines) with iterators over 2D ranges; have you done anything like that?
There are three kinds of iterators can be used in our library: - you can use the standard std::for_each to iterate over the points of for example a linestring or a multi_point, or a part of a them (using begin() end() or so) because it's all std:: container implementation here - besides that the library supports a for_each_point which iterates over all points of a linestring, polygon, and all multi geometries - furthermore the library supports a for_each_segment which iterates over all segments of the relevant geometries I don't know if this answers your question?
Some random thoughts:
Of course you're aware of the GTL proposal from a group at Intel last year. Here is my recollection of a couple of aspects of that discussion:
- It turned out that their implementation uses a cast from a base class to a derived class, which works because the derived class has the same layout as the base class in all known compilers. This is a pragmatic choice, but it's not the sort of thing that's going to be popular with Boost people as the list discussions revealed. Unfortunately, because their library is complete and in use, they're too far down the road to change something as fundamental as that. When I read "We at Geodan are developing our library since 1995", I was immediately worried that your library would also turn out to have some unpopular feature at its core, now impossible to change. So letting us see the code ASAP is definitely a good idea.
I understand. Our complete library is from 1995 and is large. The geometry is only a part and that part had to be rewritten; that's done end 2007 and still in progress. It's redesigned from scratch, in that sense it is brand new. But some of the algorithms are copied and adapted from the 1995 one, in that sense the good parts are taken over. The new geometry part is regularly reapplied to (included in) the complete library (which is not completely rewritten and is not a boost candidate) but if adaptions are necessary, that is no problem. Furthermore there are no casts, actually there is no real inheritance and there are no virtual methods; furthermore there are no calls to new or delete and hardly any exceptions thrown. Code will be there next week.
- A feature of GTL is that it can accommodate arbitrary point types by means of suitable adapters. I had mixed feelings about this. On one hand, this makes it possible to apply their algorithms to legacy data structures. On the other hand, I think that it would add an extra layer of complexity for new users who have no legacy to worry about (and library learning-curve steepness is something that I give a lot of weight to). Compare this to the standard library: using maps I often find myself writing "first" and "second" when I'd prefer to be writing "key" and "value" or "customer_number" and "address". If std::map could be adapted to work with arbitrary structs, rather than std::pair, that would be a good thing. So maybe we do need this extra layer. Except that it might make coding the libraries more complex, and my space-filling-curve point-set was at the limits of my C++ ability already! Indecision.
I don't know the GTL details. However, in our case the geometries doesn't contain any data but x and y. If a user wants more, he can derive from our point type to include for example SRID or color or anything. Or he can implement his own point type. So I think it approaches your "arbitrary structs".
Considering GTL, this library, GIL, and even CGAL, how much commonality is there? Are there shared concepts between all of these libraries? Can we extract some common concepts or patterns from the different libraries?
Will answer this briefly in the documentation, probably not completely. The answers on these questions are too extensive to give them here at this moment. However, it is interesting.
Perhaps something that's also worth asking is whether Boost is the right place for such a library. Getting releases out has not been a smooth process over the last couple of years, and I can't imagine that adding more libraries makes it any easier. Maybe Boost ought to focus more on things that are close to the standard library, and let other code find a home elsewhere.
That's not for me to decide, however, personally I miss in boost things as point-in-polygon and distance, I think a geometry library is useful in boost. Best regards, Barend Gehrels
Barend Gehrels wrote:
Phil Endecott wrote: My particular interest is in efficient containers for points (and perhaps lines) with iterators over 2D ranges; have you done anything like that?
There are three kinds of iterators can be used in our library: - you can use the standard std::for_each to iterate over the points of for example a linestring or a multi_point, or a part of a them (using begin() end() or so) because it's all std:: container implementation here - besides that the library supports a for_each_point which iterates over all points of a linestring, polygon, and all multi geometries - furthermore the library supports a for_each_segment which iterates over all segments of the relevant geometries I don't know if this answers your question?
Say I have N points, randomly distributed. I want to iterate over the M points within some region (e.g. a rectangle), where M is much smaller than N. I need to be able to do this in much better than O(N) time, e.g. O(log N + M) time. Or I have N lines and I want to find the M of them that cross a rectangular region (harder!). I get the impression that you don't have this sort of thing.
- A feature of GTL is that it can accommodate arbitrary point types by means of suitable adapters.
I don't know the GTL details. However, in our case the geometries doesn't contain any data but x and y. If a user wants more, he can derive from our point type to include for example SRID or color or anything. Or he can implement his own point type. So I think it approaches your "arbitrary structs".
Well not if I have lat and long in my legacy code instead of x and y, for example. I'm not certain how useful this is, but the GTL proponents were very enthusiastic about it. Regards, Phil.
Phil, Phil Endecott wrote:
Barend Gehrels wrote:
Phil Endecott wrote: My particular interest is in efficient containers for points (and perhaps lines) with iterators over 2D ranges; have you done anything like that?
There are three kinds of iterators can be used in our library: - you can use the standard std::for_each to iterate over the points of for example a linestring or a multi_point, or a part of a them (using begin() end() or so) because it's all std:: container implementation here - besides that the library supports a for_each_point which iterates over all points of a linestring, polygon, and all multi geometries - furthermore the library supports a for_each_segment which iterates over all segments of the relevant geometries I don't know if this answers your question?
Say I have N points, randomly distributed. I want to iterate over the M points within some region (e.g. a rectangle), where M is much smaller than N. I need to be able to do this in much better than O(N) time, e.g. O(log N + M) time. Or I have N lines and I want to find the M of them that cross a rectangular region (harder!). I get the impression that you don't have this sort of thing.
No, it is not there, sorry. You can use std::sort etc for this but you can probably do that with any library. The library at this moment doesn't contain spatial indexing, however we considered this and we have at Geodan implementations. Will discuss this again. However at this moment it is not there. The final documentation should contain things about performance and how to use boxes etc for that, however I don't know if that is feasable for next week.
- A feature of GTL is that it can accommodate arbitrary point types by means of suitable adapters.
I don't know the GTL details. However, in our case the geometries doesn't contain any data but x and y. If a user wants more, he can derive from our point type to include for example SRID or color or anything. Or he can implement his own point type. So I think it approaches your "arbitrary structs".
Well not if I have lat and long in my legacy code instead of x and y, for example. I'm not certain how useful this is, but the GTL proponents were very enthusiastic about it.
Yes you can. You can define a point class like this, deriving or including your lat long class: class lola { public : double x() const { return my_latlong.long; } double y() const { return my_latlong.lat; } // rest of implementation, it is short but some algorithms will not compile if there are no methods to change things or compare things etc. private : MY_LEGACY my_latlong; }; If you define it like this, you can use it in the algorithms the library provides and you can make linestrings, polygons, etc from it. Best regards, Barend -- ------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl
From: Barend Gehrels
Phil Endecott wrote:
Barend Gehrels wrote:
Or he can implement his own point type. So I think it approaches your "arbitrary structs".
Well not if I have lat and long in my legacy code instead of x and y,
for example. I'm not certain how useful this is, but the GTL proponents were very enthusiastic about it.
Yes you can. You can define a point class like this [snip ...]
The problem surely is that lat+long are coordinates in a non-euclidean geometry. Pythagorus's theorum is not true, two straight line segments can have TWO points of intersection - I just don't see how it can /begin/ to work. -- Martin Bonner
Martin Bonner wrote:
From: Barend Gehrels
Phil Endecott wrote:
Barend Gehrels wrote:
Or he can implement his own point type. So I think it approaches your "arbitrary structs".
Well not if I have lat and long in my legacy code instead of x and y,
for example. I'm not certain how useful this is, but the GTL proponents were very enthusiastic about it.
Yes you can. You can define a point class like this [snip ...]
The problem surely is that lat+long are coordinates in a non-euclidean geometry. Pythagorus's theorum is not true, two straight line segments can have TWO points of intersection - I just don't see how it can /begin/ to work.
Martin, My sample was more to indicate that you can use your own points. But you're very right, most calculations are nonsense if you use latlong coordinates and make no specializations. If you make the right specializations, you'll get correct answers for latlong. It is a generic framework. If you specialize the algorithm for point-to-point distance and implement for example Vincenty there, that specialization is used for lat long points (of course). If you then calculate the length of a linestring you will get that length in meters, kilometers, or miles, depending how you implement it. Because the length algorithm uses distance, which uses square_distance_point_to_point, which takes the right version automatically (by C++). template <> inline double square_distance_point_to_point(const lola& p1, const lola& p2) { // vincenty implementation } Same for intersections. However, if you use latlong everywhere you have to specialize most or all algorithms.We normally first project the points. You can even specialize for two different points - calculate the distance between latlong and something else, for example, if you make that specialization. It is a generic framework. Best regards, Barend ------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl
Phil: You might also want to check my MS student's implementation (feel free to finish/polish/improve on it!) http://photon.poly.edu/~hbr/publi/ilya-thesis/index.html He's implemented (static and dynamic) kd-trees, in 2D but the paper (http://photon.poly.edu/~hbr/publi/inplace-ch3d.html) gives all the details needed for higher-dimensional and related algorithms. -- Hervé Brönnimann hervebronnimann@mac.com On Jan 15, 2008, at 5:08 PM, Phil Endecott wrote:
There certainly is. My particular interest is in efficient containers for points (and perhaps lines) with iterators over 2D ranges; have you done anything like that?
Interesting. To all geometry-interested people: The preview of our Geometry Library was scheduled and announced for this week but will be next Tuesday, as we're finishing preliminary documentation and samples. Barend Hervé Brönnimann wrote:
Phil: You might also want to check my MS student's implementation (feel free to finish/polish/improve on it!)
http://photon.poly.edu/~hbr/publi/ilya-thesis/index.html
He's implemented (static and dynamic) kd-trees, in 2D but the paper (http://photon.poly.edu/~hbr/publi/inplace-ch3d.html) gives all the details needed for higher-dimensional and related algorithms. -- Hervé Brönnimann hervebronnimann@mac.com
On Jan 15, 2008, at 5:08 PM, Phil Endecott wrote:
There certainly is. My particular interest is in efficient containers for points (and perhaps lines) with iterators over 2D ranges; have you done anything like that?
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- ------------------------------------- Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl
participants (11)
-
Barend Gehrels -
Beman Dawes -
Fernando Cacciola -
Frank Mori Hess -
Hervé Brönnimann -
Malte Clasen -
Marc Viala Perso -
Martin Bonner -
Martin Lutken -
Niitsuma Hirotaka -
Phil Endecott