[GRASS-dev] improved Break polygons

[Markus Metz]

Breaking polygons was in my tests the worst cleaning procedure in 
v.in.ogr with regard to memory consumption. Vect_break_polygons() is 
changed in trunk and should now use about 50% - 70% less memory, at the 
same time it is considerably faster. The function uses now a balanced 
binary search tree instead of an RTree to store potential break points, 
this reduces memory requirements from 6 x sizeof(double) per point to 2 
x sizeof(double) per point. Further on, a binary search tree does not 
create internal nodes like an RTree, saving some more memory. Search 
speed on points is faster because bounding box calculations are no 
longer needed.

The longer-term idea is to have the spatial index for point structures 
(nodes, points, centroids) also in a binary search tree instead of an 
RTree to save memory and get some speed gain (related to Radim's TODO). 
Spatial searches can also be done on a binary search tree, as 
demonstrated by the new Vect_break_polygons().  Vect_select_* functions 
would need some modifications "under the hood", but the API can stay as 
it is, AFAIKT. This is not coming soon, first I would like to wait for 
any errors with the new Vect_break_polygons, then it will take some time 
to implement such big changes. BTW, the proposed changes would not break 
backwards compatibility to grass6, because the spatial index is built on 
the fly (nice to try out new features:-)).

Markus M