Hi, I've been attempting to run the voronoi/thiessen polygons function on a set of points and it seems to cause the program to freeze up.

On a side note: I have tested the function using a set of randomly generated points and it seems to work perfectly - so I'm assuming there is a problem with the coordinates for my set of points? Thank you in advance.



My code:

Dim pstations As New MapWindow.Data.FeatureSet
Dim pstations2 As New MapWindow.Data.FeatureSet

For i = 0 To numshapes - 1
Dim pt As New MapWindow.Geometries.Point(xcoords(i), ycoords(i))
pstations.AddFeature(pt)
Next

pstations.SaveAs(p_stations_path, True)

pstations2 = MapWindow.Analysis.Voronoi.VoronoiPolygons(pstations, True, MwStatusStrip1)
pstations2.SaveAs(tdbFileList.p_stations2_path, True)




Here are the coordinates for the set of points I am using:
440382.01186 , 5410897.24789
465800.95153 , 5388977.74950
477080.24752 , 5406705.20457
485252.55936 , 5395940.59067
485521.91321 , 5421193.81249
450467.96913 , 5431518.85557
521340.24370 , 5430299.30681
499043.54310 , 5403268.98553
519345.85619 , 5396912.77530
519771.40523 , 5459616.68399
509890.94559 , 5439402.77199
545606.16257 , 5417408.67386
516238.02312 , 5391001.41633
553156.96192 , 5390220.06759
437882.96963 , 5427066.11869
449580.40967 , 5426359.22860
470565.99503 , 5430166.93972
477042.03682 , 5413763.88736
482032.68784 , 5427028.65574
490591.39528 , 5418827.33644
448942.05419 , 5414081.86469
458204.26847 , 5416372.99776
472074.32450 , 5409929.21524
469349.31406 , 5403929.97999
486475.14008 , 5406453.31370
501053.65283 , 5409061.18299
507868.19853 , 5405488.07516
495563.63789 , 5427246.82834
505129.56369 , 5427525.97037
513270.83668 , 5420937.54826
516255.93724 , 5409452.59374
517909.13120 , 5402021.80809
515362.66790 , 5400991.48795
489720.20197 , 5443738.36848
489303.96006 , 5435558.11323
498229.78093 , 5443607.40548
513514.89216 , 5428718.86051
519856.07043 , 5428204.82742
517282.78774 , 5439411.55836
524011.49584 , 5434401.77200
519984.58208 , 5415089.22607
535235.23463 , 5405195.32557
529473.76835 , 5392279.18755
519904.64265 , 5376342.39105



Edited 1 time(s). Last edit at 02/12/2010 09:22AM by sschung.

You know who might be a good person to get involved in the conversation? Benjamin Dittes, the original author of the algorithm. I spent some time getting to know the algorithm and fixed some problems it was having when I first implemented it, but he may have released some updates/improvements lately. I could always try to take it apart again myself, but I'd like to see if he still has any interest in getting involved. I'll let you know what he says.

Shade1974 (Ted)

Thank you Shade1974, I appreciate the quick response. Any help on this will be greatly appreciated!

hmm, I have tried to run the same code but divided each of the coordinates of the points by 1000 and it seems to run perfectly fine. Perhaps the function has trouble using coordinates that are really high numbers?

You are probably correct. I think Ben was looking at how the function ran at different scales and probably fixed this some time ago. In the meantime, you could either re-project the points or else you could just use the scaling method before and then again after you run the tool. This is the e-mail he sent me yesterday.

Hi Ted,

no problem, I've been planning to re-publish the updated code anyways. I'm
travelling right now, but starting next week I'll look into the problem and
make a new release on code-project.

Till then,

Ben

Shade1974 (Ted)

Hi Ted,

I've temporarily got around the issue by dividing all the coordinates of the points by 1000, running the thiessen polygon function and then multiplying the result polygons by 1000 to move them back to their original coordinates.

I have now run into another issue. When I try to clip the thiessen polygons shapefile using another polygon shapefile it displays an error "System.NullReferenceException: Object reference not set to an instance of an object." Any ideas on how to fix this? (I don't seem to run into this error when I run the clipping routine on other shapefiles)

Thanks in advance.

Fascinating! These are usually cases where I simply forgot a null check. For instance, it's entirely possible that there are polygons that are being created that are empty or something. I will take a look and see if I can replicate this exception.

Shade1974

Can you give me maybe the two shapefiles you were clipping? I tried with some thiesen polygons from cities clipped by the state of texas and it worked perfectly. So it must be something that is more specific to your two datasets. (I think you can upload the datasets more easily onto the codeplex issue site).

[mapwindow.codeplex.com]

If they are too large, you can also email me at d+u+n+s+h+a+r+o+@+i+s+u+.+e+d+u minus the plusses which may or may not thwart spam crawlers.

Shade1974 (Ted)

Hi Ted,

I've emailed you the shapefiles. Thanks for the help!

I just tried the Voronoi Polygons feature in Dot Spatial and got the same problem that sschung reported in February. The function works (at least for some tests) when I divide the coordinates by 100000, but hangs with the full coordinates. Has anyone heard about an update to the algorithm?

Paul