[GRASS5] [bug #4292] (grass) Incorrect v.voronoi cells

this bug's URL: http://intevation.de/rt/webrt?serial_num=4292
-------------------------------------------------------------------------

Subject: Incorrect v.voronoi cells

Hi,

Formalities: grass 6, CVS, Ubuntu (debian)

v.voronoi does not produce correct output. It has two problems:

Input points arn't always given output polygons. (Polygons represent the cells
or region which will have the input point as its nearest neighbor).

Adjacent points on the edges arn't always divided into two polygons. This
could be a problem with dummy points on the edges.

Example:

Made an xy cooridinate system.

Set region to be [0-300] x [0-300]

v.in.ascii input=voronoi-test.csv output=voronoi_test_input fs=, skip=1

Maximum input row length: 18
Maximum number of columns: 4
Minimum number of columns: 4
column: 1 type: integer
column: 2 type: integer
column: 3 type: integer
column: 4 type: integer
Building topology ...
178 primitives registered
Building areas: 100%
0 areas built
0 isles built
Attaching islands:
Attaching centroids: 100%
Topology was built.
Number of nodes : 178
Number of primitives: 178
Number of points : 178
Number of lines : 0
Number of boundaries: 0
Number of centroids : 0
Number of areas : 0
Number of isles : 0

We've got 178 distinct nodes here, we should get 178 polygons.

v.voronoi input=voronoi_test_input output=voronoi_test_output
Layer 1
Done.
Building topology ...
589 primitives registered
Building areas: 100%
174 areas built
1 isles built
Attaching islands: 100%
Attaching centroids: 100%
Topology was built.
Number of nodes : 412
Number of primitives: 589
Number of points : 0
Number of lines : 0
Number of boundaries: 411
Number of centroids : 178
Number of areas : 174
Number of isles : 1
Number of incorrect boundaries : 15
Number of centroids outside area : 3
Number of duplicate centroids : 1

We only get 174 polygons. One of them is missing in the lower right corner of
the map where two points on the edge arn't being divided. Three are missing
from the left side of the top of the map; the lines are there but the areas
aren't. You can see these easily by displaying the map. The output above
suggests that they might be getting cut in some later building topology stage
because the centroids are misplaced.

Using regions close to the data and larger regions doesn't change the problems
in the output.

Download test case:
http://www.shockfamily.net/cedric/grass/voronoi-test.csv

(it has more than two collumns due to v.in.ascii bug 4291)

Thanks for the help,

--Cedric

-------------------------------------------- Managed by Request Tracker