I am trying to subdivide a finite portion of the plane into a set of at least 20 or so random interlocking shapes, with the shape boundaries having a fractal dimension around that of borders between countries that aren't simply straight lines (which I crudely estimate to be $1.15\pm0.1$, based upon visual inspection of Wikipedia's list of fractals by Hausdorff dimension). Preferably, the plane would have toroidal boundary conditions, although generating another single country-like shape to serve as the overall boundary would also be acceptable.

Running Kruskal's algorithm for maze generation on a torus (and keeping only the boundary) gives about the right fractal dimension, but that only creates one shape that tiles the plane by translation. Running several instances of the DFS algorithm at once (again, keeping only the boundaries between the various sub-mazes) generates highly unrealistic narrow portions. (Additionally, in both cases, the result is made of tiny discrete units, which may or may not be a problem). Using a Delauney triangulation is an excellent method to make a graph representing a system of countries, but its corresponding Voronoi diagram makes for perfectly straight borders.

Kruskal maze generation:

Kruskal maze generation

16-fold DFS maze generation:

16-fold DFS maze generation

100-point toroidal Delauney triangulation and corresponding Voronoi diagram:

With[{r = RandomReal[{-1, 1}, {100, 2}]}, 
 With[{s = 
    Flatten[Table[# + {i, j} & /@ r, {i, -2, 2, 2}, {j, -2, 2, 2}], 
     2]}, Show[
   VoronoiMesh[s, PlotRange -> 1, ImageSize -> 1024, 
    MeshCellStyle -> {{1, All} -> Directive[Dashed, Black]}], 
   DelaunayMesh[s, PlotRange -> 1, ImageSize -> 1024, 
    PlotTheme -> "Lines", 
    MeshCellStyle -> {{1, All} -> Directive[Thick, Blue], {0, All} -> 
       Directive[PointSize[Large], Red]}]]]]

Delauney triangulation and corresponding Voronoi diagram

While it is likely implied by solving the main question, do also let me know if there is a simpler procedure for generating a single country-like shape. (I've tried a polar plot of fractional Brownian motion, but the anomalies look decidedly non-random to the eye, as they all point directly towards or away from the pole. Using a 3D terrain generator (and slicing it at a certain z-value) works, but one has to generate the entire terrain, not just the boundary in question; this method also produces many excess islands (which might actually be beneficial, but that could interfere with the border-making process).)

Polar plot of fractional Brownian motion ($h=.85$):

With[{p = 
   BlockRandom[SeedRandom[1, Method -> "MersenneTwister"]; 
      FractionalBrownianMotionProcess[.85], {0, 2 Pi, Pi/180}][
 With[{q = 
    p[#] - p[2 Pi] #/(2 Pi) + 
      3/2 &}(*effectively turns this into a BrownianBridgeProcess*), 
  Show[PolarPlot[q[t], {t, 0, 2 Pi}, ImageSize -> 1024, 
    Axes -> False, PlotStyle -> None](*establishes plot range*), 
    Sqrt[x^2 + y^2] <= q[Mod[ArcTan[x, y], 2 Pi]], {x, -5, 5}, {y, -5,
      5}, PlotPoints -> 200](*allows for filling*)]]]

polar plot

1024*1024 terrain (again, $h=.85$; method originally found in ISBN 0-306-42851-2, although I translated it into Mathematica):

n = 10; H = .85; heightlist = {{0}}; For[k = 1, k <= n, k++, 
 heightlist = 
    ArrayPad[heightlist, {{0, 1}, {0, 1}}, "Periodic"], {2^k + 1, 
     2^k + 1}][[;; -2, ;; -2]]; 
 heightlist += 
  Table[Mod[i + j, 2], {i, 2^k}, {j, 2^k}] /. {1 -> Indeterminate}; 
 heightlist += 
  RandomVariate[NormalDistribution[0, 2^((-k + 1/2) H)], {2^k, 2^k}]; 
 heightlist = 
  CellularAutomaton[{{{_, a_, _}, {b_, Indeterminate, c_}, {_, 
       d_, _}} -> 
     Mean[{a, b, c, d}], {{_, Indeterminate, _}, {Indeterminate, e_, 
       Indeterminate}, {_, Indeterminate, _}} -> e}, heightlist]; 
 heightlist += 
   NormalDistribution[0, 2^(-k H)], {2^k, 2^k}]]; ArrayPlot[
 Sign[heightlist - 1], PixelConstrained -> 1, Frame -> False, 
 PlotRange -> {-1, 1}]


  • 1
    $\begingroup$ This question is a bit too broad, don't you think? And how is it related to Mathematica? $\endgroup$ Nov 10, 2017 at 7:42
  • 1
    $\begingroup$ You might want to think about breaking your question down into a few smaller questions. And posting what you've tried. $\endgroup$ Nov 10, 2017 at 10:53
  • $\begingroup$ @HenrikSchumacher It might be broad, but I often have trouble distilling my hodgepodge of thoughts down to a single idea (instead of multiple connected ideas). As for how the question is related to Mathematica, it's the programming language I use most frequently, at least partly because of all of the predefined functions that are available. However, as I do use other programs in tandem with Mathematica, I would be fine with a migration to StackOverflow (or another more appropriate place) if it is deemed necessary. $\endgroup$ Nov 11, 2017 at 0:05
  • $\begingroup$ @aardvark2012 I am thinking of splitting the question into the singular and interlocking cases, but I am holding off on doing so until the above question of migration is answered. (Or should I just split the question now and not worry about migration yet?) In any case, I will be gradually uploading and editing in images of what I've tried. $\endgroup$ Nov 11, 2017 at 0:14
  • 1
    $\begingroup$ @HenrikSchumacher: OK, I'll admit that I misunderstood the question, in that my original question would still be valid if you replaced Mathematica with any other programming language. Reposting on Stack Overflow. $\endgroup$ Dec 2, 2017 at 18:41


Your Answer

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

Browse other questions tagged or ask your own question.