Subscribe to this thread
Home - General / All posts - Voronoi precision in Lat/Long vs Projection
JS _IED2 post(s)
#15-Jan-21 09:15

I am a relatively new user working in Manifold 8.

I have a layer of 5295 points in Bénin, in projection UTM 31N, around which I would like to trace Voronoi areas and then generate an output layer projected in Lat/Long.

When I generate my Voronoi areas in UTM 31N, I obtain 5,295 areas as expected. When I change the projection of the layer to Lat/Long and then generate the areas, I obtain 5291 areas.

I have four points that are each very close to another point (<0.1 meters, without being geom duplicates), and I suspect that the difference in the number of areas drawn in the two projections is a question of loss of precision when my X,Ys are translated into degrees by the projection change, and then (hypothesis on my part!) back into X,Y by the Voronoi algorithm, which makes the points "appear" to be perfect superpositions for the Voronoi areas.

Is that correct? Could someone provide a robust explanation for the difference and/or a good rule of thumb for working with Voronoi (e.g. "always work in X,Y because Voronoi works in X,Y" or "always work in the projection of the source data") please?

Thank you very much in advance!


6,436 post(s)
#15-Jan-21 14:29

Just a guess, but it's more likely that two points closer than whatever tolerance is calculated using the "auto" tolerance are at the same location in Lat/Lon but not in the UTM projection.

Benin is pretty close to the equator, so let's say a degree is 111 kilometers. 0.1 meter is therefore about 0.0000009 degree.

If you are using the Voronoi transform template, you can press the Edit Query button and change the query. You can change the 0 value (meaning, use auto tolerance) in the GeomVoronoiPar function call to some value (in degrees) that is smaller than the separation between the two points. There's probably also some interplay with the query logic that specifies a border, to prevent too great inflation of the outermost Voronoi areas.

But as you can see when you go to choose a sensible tolerance to manually specify in degrees, it's a poor idea to do anything involving measurement in Latitude / Longitude, since the length of a degree depends not only on orientation but also on the distance from the Equator.

The rule of thumb is to do things involving measurement in projected systems using linear units that preserve scale. You can always reproject the resulting Voronoi cells into Lat / Lon if that's what you want them in.

JS _IED2 post(s)
#15-Jan-21 16:26

Thank you Dimitri!


9,480 post(s)
#18-Jan-21 15:45

The advice to project lat/lon data to a metric system, then compute Voronoi areas in that metric system will work. But there's a way to avoid collapsing points, eg, within 0.1 meters, in lat/lon as well - change the tolerance value used for the Voronoi transform (make it smaller).

For Manifold 8: open your lat/lon component, invoke View - Properties, press the '...' button next to the Precision report, change the default value of 0.000001 degree (~0.1 meter at equator) to, say, 0.0000001 degree (~0.01 meter, one more zero), click OK twice, then repeat the transform.

Manifold User Community Use Agreement Copyright (C) 2007-2019 Manifold Software Limited. All rights reserved.