Boost logo

Boost :

From: Barend Gehrels (barend_at_[hidden])
Date: 2008-01-16 11:49:05


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; }
    // 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,

Boost list run by bdawes at, gregod at, cpdaniel at, john at