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

GDAL · June 22, 2009, 1:38pm

#660: v.dalaunay producing incorrect results
-----------------------+----------------------------------------------------
Reporter: cmbarton | Owner: grass-dev@lists.osgeo.org
Type: defect | Status: new
Priority: critical | Milestone: 6.5.0
Component: Vector | Version: svn-develbranch6
Keywords: delaunay | Platform: MacOSX
Cpu: OSX/Intel |
-----------------------+----------------------------------------------------
When I tried v.delaunay after compiling GRASS 6.5 from the SVN on Friday
(20 May), it gave very weird results. I'm attaching an example from using
it on archsites from Spearfish.

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

GDAL · June 23, 2009, 5:39am

#660: v.delaunay producing incorrect results
-----------------------+----------------------------------------------------
  Reporter: cmbarton | Owner: grass-dev@lists.osgeo.org
      Type: defect | Status: new
  Priority: critical | Milestone: 6.5.0
Component: Vector | Version: svn-develbranch6
Resolution: | Keywords: delaunay
  Platform: MacOSX | Cpu: OSX/Intel
-----------------------+----------------------------------------------------
Changes (by hamish):

* summary: v.dalaunay producing incorrect results => v.delaunay
producing incorrect results

Comment:

see these mailing list threads:

http://thread.gmane.org/gmane.comp.gis.grass.user/30001/
http://thread.gmane.org/gmane.comp.gis.grass.devel/33926

including this valgrind error:

{{{
...
WARNING: Vector map <DelaunayTriangles> already exists and will be
overwritten
==7844== Syscall param write(buf) points to uninitialised byte(s)
==7844== at 0x71C09F0: write (in /lib/libc-2.7.so)
==7844== by 0x716E909: _IO_file_write (in /lib/libc-2.7.so)
==7844== by 0x716E569: (within /lib/libc-2.7.so)
==7844== by 0x716E8A4: _IO_do_write (in /lib/libc-2.7.so)
==7844== by 0x7170256: _IO_switch_to_get_mode (in /lib/libc-2.7.so)
==7844== by 0x716ED8F: _IO_file_seekoff (in /lib/libc-2.7.so)
==7844== by 0x7164049: ftell (in /lib/libc-2.7.so)
==7844== by 0x5D455FD: dig_ftell (file.c:41)
==7844== by 0x5D4600F: dig__write_head (head.c:56)
==7844== by 0x4E5AC9C: V1_open_new_nat (open_nat.c:127)
==7844== by 0x4E5A155: Vect_open_new (open.c:565)
==7844== by 0x403B0D: main (main.c:106)
==7844== Address 0x4022009 is not stack'd, malloc'd or (recently) free'd
Building topology for vector map <DelaunayTriangles>...
Registering primitives...
...
}}}

works ok in Linux + latest grass 6.5svn, both 32 and 64bit.

Hamish

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

GDAL · July 6, 2009, 3:36pm

#660: v.delaunay producing incorrect results
-----------------------+----------------------------------------------------
  Reporter: cmbarton | Owner: grass-dev@lists.osgeo.org
      Type: defect | Status: new
  Priority: critical | Milestone: 6.5.0
Component: Vector | Version: svn-develbranch6
Resolution: | Keywords: delaunay
  Platform: MacOSX | Cpu: OSX/Intel
-----------------------+----------------------------------------------------
Comment (by hamish):

is this seen on 6.4.0rc as well?

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

GDAL · July 6, 2009, 5:27pm

#660: v.delaunay producing incorrect results
-----------------------+----------------------------------------------------
  Reporter: cmbarton | Owner: grass-dev@lists.osgeo.org
      Type: defect | Status: new
  Priority: critical | Milestone: 6.5.0
Component: Vector | Version: svn-develbranch6
Resolution: | Keywords: delaunay
  Platform: MacOSX | Cpu: OSX/Intel
-----------------------+----------------------------------------------------
Comment (by cmbarton):

Yes unfortunately.

I just updated 6.4 from the SVN and compiled in 32 bit. I get the same
kind of output seen in the PNG attached to this report. This is a blocker
for 6.4.0.

Michael

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

GDAL · July 6, 2009, 5:35pm

#660: v.delaunay producing incorrect results
-----------------------+----------------------------------------------------
  Reporter: cmbarton | Owner: grass-dev@lists.osgeo.org
      Type: defect | Status: new
  Priority: blocker | Milestone: 6.4.0
Component: Vector | Version: 6.4.0 RCs
Resolution: | Keywords: delaunay
  Platform: MacOSX | Cpu: OSX/Intel
-----------------------+----------------------------------------------------
Changes (by martinl):

  * priority: critical => blocker
  * version: svn-develbranch6 => 6.4.0 RCs
  * milestone: 6.5.0 => 6.4.0

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

GDAL · July 20, 2009, 1:41pm

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

On a random suggestion from Markus Neteler, I tested a build with no GCC
optimization. Same results. 32bit and 64bit.

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

GDAL · August 20, 2009, 11:00am

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

* priority: blocker => critical

Comment:

triage

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

GDAL · October 3, 2009, 5:58am

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

On Linux v.delaunay is looking fine to me, testing it on 64bit Ubuntu 9.4
running 6.4.0RC5.

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

GDAL · October 3, 2009, 6:47am

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

Still badly broken on my Mac in 6.4 compiled from svn 26 September. Has
there been any fix since that date?

Michael

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

GDAL · November 12, 2009, 10:13pm

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

v.delaunay is still broken. It creates a mess of overlapping triangles in
places and leaves complete blankes in other places.

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

GDAL · December 25, 2009, 12:23pm

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

Michael, could You, please, run affected module from 6.5 under valgrind
(or any other memory tracing tool)? It works just fine on Linux and I'm
unable to get meaningfull errors out of valgrind/mudflap.

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

GDAL · December 30, 2009, 4:51am

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

maris, just checking if you saw my valgrind attachments - trac didn't
email me like it does for comments.

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

GDAL · December 30, 2009, 7:57pm

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

kyngchaos - no need for leakcheck, as we are not hunting leaks Thanks
for output. Same as on my AMD64 Linux box, still here results are fine. No
other ideas from me (mudflap is somehow broken and thus requires some
tweaking before use and it doesn't show anything interesting on my Linux
box).

MarkusM - what's up with those warnings in vlib/diglib code?

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

GDAL · December 30, 2009, 9:23pm

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

I did some more tests and have posted the results to better show what is
happening. For comparison, I show a map of Spearfish archsites (blue
triangles in all images). In June 2005, v.delaunay worked correctly on my
computer. It also worked correctly 24 April 2008, so that narrows down
when it broke better.

For small datasets (4-5 points) it seems to work fine. See
dt_fewsites.png.

For medium sized datasets (all archsites) it runs but gives incorrect
results. See dt_allsites.png

For larger datasets (1000 points) it uses all available CPU resources and
takes a VERY long time to complete (or perhaps just locks up).

Michael

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

GDAL · December 30, 2009, 9:28pm

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

More information. When I ran v.delaunay on 1000 points, I finally killed
it, but it had created a coor file of 1.37 Gb. Yes that is Gb. Before I
realized how huge it was, I tried to run v.build on it. It was up to <
300,000 primitives before I killed that.

Something is seriously wrong here.

Michael

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

GDAL · December 31, 2009, 10:06am

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

Replying to [comment:12 marisn]:
>
> MarkusM - what's up with those warnings in vlib/diglib code?

I assume you refer to the valgrind output, at least I don't get any
warnings when running v.delaunay without valgrind. The only valgrind
errors that tell me something are right at the beginning, here

http://trac.osgeo.org/grass/attachment/ticket/660/delaunay-
valgrind1.txt#L17

and here

http://trac.osgeo.org/grass/attachment/ticket/660/delaunay-
valgrind1.txt#L27

The second one saying that Address 0x66d5f29 is 9 bytes inside a block of
size 4,096 alloc'd may cause problems, but I have not the faintest idea
where this is coming from, I don't get this one on Linux, only number 1.

If all other vector modules are working, the problem is IMHO more likely
somewhere in the module than in the vector libs. So, are other vector
modules working?

On my Linux system, v.delaunay is fast and produces correct results, also
with e.g. elev_lid792_bepts with 118,716 points.

Sorry, not much help from my side,

Markus M

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

GDAL · December 31, 2009, 11:42am

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

Please try attached patch in verbose mode.

Markus M

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

GDAL · December 31, 2009, 3:10pm

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

Same output on archsites for me.

v.voronoi appears to work, on archsites. I don't have a large point file
to test it - Michael?

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

GDAL · December 31, 2009, 7:07pm

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

I tried v.voronoi on 1000 elevation points in the SC demo data set. It
took only a couple seconds and worked fine.

Michael

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

GDAL · December 31, 2009, 7:56pm

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

I applied the patch in GRASS 6.4 (just updated from the SVN).
Unfortunately, it gives the same results as before.

Michael

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