[GRASS-dev] Re: [GRASS GIS] #660: v.delaunay producing incorrect results

[GRASS GIS]

#660: v.delaunay producing incorrect results
-----------------------+----------------------------------------------------
  Reporter:  cmbarton  |       Owner:  grass-dev at lists.osgeo.org
      Type:  defect    |      Status:  closed                   
  Priority:  critical  |   Milestone:  6.4.0                    
 Component:  Vector    |     Version:  6.4.0 RCs                
Resolution:  fixed     |    Keywords:  delaunay                 
  Platform:  MacOSX    |         Cpu:  OSX/Intel                
-----------------------+----------------------------------------------------
Comment (by mmetz):

 Replying to [comment:39 hamish]:

 Thanks for looking at the code, two people see more than one alone.
 >
 > How does it perform when the number of input points > 10,000 (& up to
 ~3M)? which was where the old v.delaunay1 fell over?
 >
 I generated 10,000,000 random points and killed v.delaunay when building
 topology for the output vector, my system ran out of memory (8GB RAM). The
 delaunay triangulation went fast and did not use a lot of memory, but the
 topo file would be larger than 2GB which is only supported in grass7.

 Then I generated 5,000,000 random points, v.delaunay finsihed successfully
 in 11 min. The Delaunay triangulation took just a few seconds, impressive!
 That is the original algorithm of Martin Pavlovsky, slightly simplified by
 me. Again, the bottleneck was building topology, although I used lines not
 areas as output. Areas as output for 5 million points will only work in
 grass7.
 >
 > re. the patch, three minor comments after a cursory look.
 >
 >  2) TRUE=1, FALSE=0 is defined by gis.h, no need to repeat it.
 TRUE=1, FALSE=0 are used in geometry.c only which does not include gis.h,
 and it uses #ifndef TRUE...
 >  3) cmp_v() appears to test two FP values with ==. Should it use
 > {{{
 >  if( fabs(val1 - val2) < GRASS_EPSILON )
 > }}}
 > instead? Is it looking for itself or another point at the same place as
 it is?
 It's looking for another point at the same place. There is a lot of fp
 comparison in grass, should something like (x1 < x2) also be replaced with
 (fabs(x2 - x1) > GRASS_EPSILON)? With respect to the v.delaunay2 code, it
 would be safest and most consistent to use cmp() from main.c instead of
 cmp_v(), that also avoids code duplication. BTW, cmp_v() corresponds to
 compare() in the old code which caused qsort to fail on Windows and Mac
 for at least one, maybe three reasons (correct usage in v.voronoi).

 Markus M

-- 
Ticket URL: <https://trac.osgeo.org/grass/ticket/660#comment:40>
GRASS GIS <http://grass.osgeo.org>