Is there any interest in a template geometry library?

View: New views
20 Messages — Rating Filter:   Alert me  
< Prev | 1 - 2 | Next >

Is there any interest in a template geometry library?

by Barend Gehrels :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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@...
Website: www.geodan.nl
-------------------------------------



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Parent Message unknown Re: Is there any interest in a template geometry library?

by 吴黄 :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message



------------------
吴黄
2008-01-15

-------------------------------------------------------------
发件人:Barend Gehrels
发送日期:2008-01-14 21:36:12
收件人:
抄送:
主题:[boost] Is there any interest in a template geometry library?

Hi,

Is there any interest in a template geometry library?

I am a Chinese graduate student majoring CAD/CG in Hefei University of Technology, and I'm very interest in the 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.

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.

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,

Why not to put the data and algorithms together for encapsulation? Because I think the parameter type which algorithm operates is very limited, not generic, just one or two.

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.

Where could i get the library and documentation from?

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@...
Website: www.geodan.nl
-------------------------------------



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Beman Dawes :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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

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

by Malte Clasen-2 :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Niitsuma Hirotaka :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

2008/1/15, Malte Clasen <news@...>:
> 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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Marc Viala Perso :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

I will greatly appreciate this type of library in Boost.

Marc

> -----Message d'origine-----
> De : boost-bounces@... [mailto:boost-bounces@...]
De la part

> de Beman Dawes
> Envoyé : mardi 15 janvier 2008 02:26
> À : boost@...
> 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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Barend Gehrels :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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
>
>
>
>  



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Re: Is there any interest in a template geometry library? I had started one - Info here!

by Martin Lütken-2 :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Fernando Cacciola-2 :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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 


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Barend Gehrels :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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

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

by Phil Endecott-48 :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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.




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Fernando Cacciola-2 :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Barend Gehrels :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Barend Gehrels :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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:
>
> http://www.cgal.org/philosophy.html
>  
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
>
> http://tinyurl.com/2os9co
>
>
> Best
>
>  
Best regards,
Barend Gehrels, Geodan Holding B.V., Amsterdam, the Netherlands



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Phil Endecott-48 :: Rate this Message:

Reply to Author | View Threaded | Show Only this Message

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.




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

by Barend Gehrels :: Rate this Message: