I'm failing at reading the documentation. Is there a way to specify the distance function used by VoronoiMesh? As a stripped down example say I have a rank-1 lattice such as:

n = 256; v1 = {1, 71};

points = Table[Mod[i v1, n], {i, 0, n - 1}];
mesh = VoronoiMesh[points, {{0, n - 1}, {0, n - 1}}];
Show[mesh, Graphics[{Orange, Point[points]}]]

Rank1 example

but instead of standard Euclidean distance I instead want Euclidean distance on the flat torus, so in this example all the cells would be the same shape.

  • 1
    $\begingroup$ I don't know of a way to change the distance function in VoronoiMesh, but the "properties and relations" section of the docs shows an example where the conditions for each cell are generated explicitly and the mesh is reproduced with RegionPlot. That's not typically very fast, but it may work for you. What functional expression would "Euclidean distance on the flat torus" have? $\endgroup$
    – MarcoB
    Mar 19, 2019 at 14:34
  • $\begingroup$ Possible duplicate: Voronoi tessellations on meshed surfaces $\endgroup$
    – Szabolcs
    Mar 19, 2019 at 14:38
  • 1
    $\begingroup$ Adding a general non-Euclidean metric to the space would, I think, make the problem much harder computationally; it wouldn't necessarily be the case that a "straight line" (geodesic) bisecting the path of minimum distance between two points would be equidistant from both. $\endgroup$ Mar 19, 2019 at 14:40
  • 3
    $\begingroup$ Also, for your problem, a quick and dirty way to solve the problem would be to "pad" the set of points with duplicate points on all four sides, find the Voronoi mesh of that, and then trim the resulting cells back to the original domain. $\endgroup$ Mar 19, 2019 at 14:42
  • $\begingroup$ @ MarcoB: simply the top/bottom edges are the same and likewise right/left (so the square tiles the plane). Assume by brain's working correctly a hacky distance would be: "d[{x0_, y0_}, {x1_, y1_}, n_] := Sqrt[Mod[w[x1 - x0, n], n]^2 + Mod[w[y1 - y0, n], n]^2]" with helper function: w[d_, n_] := With[{a = Abs[d]}, If[a <= n/2, a, n - a]] $\endgroup$ Mar 19, 2019 at 21:17

1 Answer 1


If you're only concerned about visualization and not computation, you could always create a relation and pass it to a plotting function. If the number of points is low enough and your distance function isn't too unwieldy, you should get ok results.

VoronoiBoundaryPlot[pts_, bds_, df_:EuclideanDistance] :=
  Block[{nf, isoLine, x1, x2, y1, y2, mr, δ = .005, good, keep},
    nf = Nearest[pts -> {"Index", "Element"}, DistanceFunction -> df];
    isoLine[q_] := df[#1, q] - df[#2, q]& @@ Sort[nf[q, {2, ∞}]][[All, 2]];
    {{x1, x2}, {y1, y2}} = bds;

    mr = DiscretizeGraphics[ContourPlot[isoLine[{x, y}] == 0, {x, x1, x2},{y, y1, y2}, PlotPoints -> 80, Evaluated -> False]];
    good = Pick[Range[MeshCellCount[mr, 0]], UnitStep[Abs[isoLine /@ MeshCoordinates[mr]] - δ], 0];
    keep = Cases[Tally[mr["ConnectivityMatrix"[0, 1]][[good]]["NonzeroPositions"][[All, 2]]], {_,2}][[All, 1]];

      GraphicsComplex[MeshCoordinates[mr], {Red, MeshCells[mr, {1, keep}]}],

A small example:

pts = RandomReal[{0, 1}, {20, 2}];
dfs = {BrayCurtisDistance, ChessboardDistance, EuclideanDistance, ManhattanDistance};
bds = {{-.1, 1.1}, {-.1, 1.1}};

Table[Show[VoronoiBoundaryPlot[pts, bds, df], PlotLabel -> df], {df, dfs}]

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.