[GRASS5] g51 spatial index, level 2 update and v.clean

[Radim Blazek]

Hi,

1) RTree: I commited to grass rtree library written A. Guttman and D. Green
and updated related vector library so that true spatial index for nodes,lines
areas and islands is built and stored in file.

2) Level 2 update (L2U): Work on L2U was started, not yet fully completed 
(rewrite uses delete + write) but seems to work. This is important
for v.digit (which based on L2U routines should be simplified) and modules 
which need topology or spatial index during vector modification (like v.clean)

3) v.clean: I played a bit with new functions Vect_segment_intersection() and 
Vect_line_intersection() (started with code from v.spag/linecros.c)
and wrote new module v.clean (current tools: intersect lines, remove 
duplicates). 
And to my big surprise, it seems to work. I am doing following tests:
a) generate random polygons
   http://mpa.itc.it/radim/g51/v.clean/clean.test.png 
b) clean the mess by
   v.clean input=clean.test output=clean.test1 tool=break,rmdupl 
   => http://mpa.itc.it/radim/g51/v.clean/clean.test1.png
c) check the topology by
   v.topo.check input=clean.test1 output=clean.test2 
   which: - removes all boundaries with area on both sides
          - check if just 1 area is in result
          - check if difference between sum original areas and new one is
            small enough (0.000001 %)
   => http://mpa.itc.it/radim/g51/v.clean/clean.test2.png 
d) write areas to new file as polygons and repeate b) and c) on that file
   (it tests better identical lines)

Is it sufficient test?

Test is automated by v.clean.test script (just start grass51 and run 
v.clean.test). Testers are welcome. I would also appreciate if people having 
some dirty vectors in grass50, for which intersection utility in grass50 
fails, could try v.convert and v.clean in grass51 and tell me results. 


Everything is in CVS and new binary version for linux is in:
http://grass.itc.it/grass51/binary/linux/


Radim