4
$\begingroup$

Consider a set of points generated via Lloyd's relaxation algorithm

rel = Function[{pts}, 
   Block[{cells}, 
    cells = MeshPrimitives[VoronoiMesh[pts, {{-1, 1}, {-1, 1}}], 
      "Faces"];
    RegionCentroid /@ 
     cells[[SparseArray[Outer[#2@#1 &, pts, RegionMember /@ cells, 1],
           Automatic, False]["NonzeroPositions"][[All, 2]]]]]];
n = 30;
pts = RandomReal[{-1, 1}, {n, 2}];
vor = VoronoiMesh[Nest[rel, pts, 20]]

enter image description here

Then, if I wanted a more "realistic" mesh and exclude the boundary cells, I could get something like this

vori = MeshCellIndex[vor, {2, "Interior"}];
Graphics[{Gray, EdgeForm[{Thick, White}], 
  Table[MeshPrimitives[vor, 2][[vori[[j, 2]]]], {j, Length[vori]}]}]

enter image description here

Now, the problem with this approach is that I can't get the exact number of interior cells that I want (same as this approach). It will always depend on which cells touch the boundary (or "Frontier", as it's sometimes used) and which don't. Now, an alternative way is to consider a periodic mesh, and in that case we get

ptsi = Nest[rel, pts, 20];
pts2 = Flatten[
   Table[TranslationTransform[{2 i, 2 j}][ptsi], {i, -1, 1}, {j, -1, 
     1}], 2];
vorp = VoronoiMesh[pts2, {{-3, 3}, {-3, 3}}];
vcells = Catenate[NearestMeshCells[{vorp, 2}, #] & /@ ptsi];
pvor = MeshRegion[MeshCoordinates[vorp], MeshCells[vorp, vcells]]

enter image description here

This seems to do the trick (despite some occasional problems with rel), but it still has the problem that it is only considering periodic meshes.

My goal: Given a number n, generate a roughly square mesh of similar "realistic-looking" cells, in the sense of the examples above. For instance, I think it would be enough to simply fix the mean and variance of the cells area and perimeter, such that the tissue has a "uniform" look, and no "spiky" cells appear. I'm sorry for the over-usage of " ", but I'm ok with slightly different mathematical descriptions, as long as I get a mesh with a similar look to the ones presented above.

On top of that, if the mesh moves (as seen here, for example), I want the cells to be able to move accordingly (so that suddenly a cell doesn't become a frontier cell and disappears, which could happen in the first approach). Naturally I could draw the cells, but I want to specifically use VoronoiMesh and avoid periodic meshes.

Any ideas?

$\endgroup$
10
  • 1
    $\begingroup$ Can you clarify again what is meant by "realistic"? $\endgroup$ Jul 8 '20 at 12:32
  • 1
    $\begingroup$ @TumbiSapichu Great question, I've edited the "My goal" section, so that hopefully give you an idea of what I want. $\endgroup$
    – sam wolfe
    Jul 8 '20 at 14:12
  • 1
    $\begingroup$ @samwolfe I've thought a bit about the "regular cells" problem recently, and although I still have not tried an answer, here's an idea. I think it's not possible to build cells with a known average area/perimeter without first building the Voronoi mesh (I might be wrong here). But, what you could do is generate random points as you do, then calculate their areas/perimeters, then use use Lloyd's process and check the area/perimeter at every time step, and stop when it is around the desired average. This could be done also applying Loyd's to only some cells (the "irregular ones"), for instance. $\endgroup$ Jul 8 '20 at 14:19
  • 1
    $\begingroup$ I see. It's tricky, and I don't see if it will work (but you should try!). Alternatively, you can "fix" cells at the boundary (just like a picture frame), and only generate random points inside the frame, then apply all these processes (Lloyd's and whatnot) to the inner cells only (but the Voronoi tesselation to all points, including the frame), for enough steps that the inner cells become regular without converging to an hexagonal lattice. Another approach that seems relevant to you (or at least the ideas in it) is here. $\endgroup$ Jul 8 '20 at 14:31
  • 1
    $\begingroup$ @TumbiSapichu I've added my answer, please take a look and let me know if you have any comments. $\endgroup$
    – sam wolfe
    Jul 8 '20 at 16:13
3
$\begingroup$

Following the discussion in the comment section with @TumbiSapichu, I've found a possible solution to this problem. As mentioned, instead of translating the seeds, we could simply add more points, enough so that, upon drawing a rectangle centred in this new mesh, you simply pick the first n cells which seeds intersect the rectangle, with increasing size, until the n threshold is met. The following code does what I want, where n = 36 is simply selected so that we get an approximate $6\times 6$ lattice

n = 36;
rel = Function[{pts}, 
   Block[{cells}, 
    cells = MeshPrimitives[VoronoiMesh[pts, {{-1, 1}, {-1, 1}}], 
      "Faces"];
    RegionCentroid /@ 
     cells[[SparseArray[Outer[#2@#1 &, pts, RegionMember /@ cells, 1],
           Automatic, False]["NonzeroPositions"][[All, 2]]]]]];
pts = RandomReal[{-1, 1}, {1 + 2 n, 2}];
ptsr = Nest[rel, pts, 20];
vor = VoronoiMesh[ptsr];
rr = 0.1;
ac = 0;
While[ac < n,
  rt = Rectangle[{-rr, -rr}, {rr, rr}];
  ml = Select[MeshPrimitives[vor, 2], 
    RegionDimension[RegionIntersection[#, rt]] =!= -Infinity &];
  ac = Length[ml];
  rr = rr + .05
  ];
Graphics[{Gray, EdgeForm[{Thick, White}], ml}]

enter image description here

In fact, there is no limitation as to the shape of rt. Considering more cells and taking rt to be, for example, the disk

rt = Disk[{0, 0}, rr];

We get, for n = 400,

enter image description here

Notice that the radius increments become more sensible for higher value of n and therefore should be adjusted accordingly to avoid counting too many cells.

Just as an interesting observation, the disk case can be replicated using the following code

ml2 = Table[
   MeshPrimitives[vor, 
     2][[NearestMeshCells[vor, {0, 0}, n][[j, 2]]]], {j, n}];
Graphics[{Gray, EdgeForm[{Thick, White}], ml2}]

where NearestMeshCells is based on euclidean distance, maybe it's possible to tweak it in such a way that incorporates the rectangle case as well (Manhattan distance, maybe?).

Anyway, this seems to work fine for relatively small n. As suggested by @TumbiSapichu in the comments, fixing a cell frame and letting only interior cells move and update via Lloyd's relaxation algorithm could prove another, and perhaps more efficient, way of doing this. Let me know if you have any comments or improvements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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