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

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-01-16 11:31:32

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.