Roundness

Click on the Compute roundness file button creates a file with the roundness measures, from the code in Features/Roundness.js. Try to run the stabilization of Max stable + Identity on some tiling, and you will understand why we are talking about some "roundness".

Definition

The formal definition of roundness is given is this arXiv article. Given a configuration, the set of tiles is partitioned into:

• outerTiles for Tile Object t having t.sand = t.limit-1 grains and connected to the border by a path of tiles also having .sand = .limit-1,
• innerTiles for all other Tile Objects.

Then:

• the outerRadius is the biggest radius of a circle centered on (0,0) and having all outerTiles in its exterior (inscribed),
• the innerRadius is the smallest radius of a circle centered on (0,0) and having all innerTiles in its interior (circumscribed).

The roundness of the configuration is the difference innerRadius - outerRadius.

Implementation

The event listener calls asynchronously (await) the main function makeRoundnessFile on the current Tiling (currentTiling), which returns a file containing the roundness measures, formatted as one line of the form innerRadius/outerRadius/roundness, per step (we plan to create graphics using our beloved tikz), from Max stable + Identity to Max stable (included).

Technical considerations

Since tiles are polygons, the radius of a circumscribed circle (which is convex, that's the trick) can simply be computed as a Math.max on the distances of each tile bounds to coordinate (0,0), themselves computed with distance(xA,yA,xB,yB) from Utils/Geometry.js. However the inscribed circle may be tangent to some tile edge! To this purpose we have implemented distancePointSegment(x,y,xA,yA,xB,yB) in Utils/Geometry.js

In/circum-scribed circles: circles_radii(tiling)

Computes the radius of the inscribed and circumscribed circles of the entire tiling (all tiles). The former is an upper bound on the outer radius, and the latter is an upper bound on the inner radius.

The annoying part of this is to recover which edges of border tiles are on the border of the tiling, in order to compute the inscribed circle (see Technical considerations). Once borderEdges contains the pairs of pairs of coordinates corresponding to tile edges on the border of the tiling, its just:

  let borderEdgeDistances = borderEdges.map(e => distancePointSegment(0,0,e[0][0],e[0][1],e[1][0],e[1][1]));
  let inscribed = Math.min(...borderEdgeDistances);

  let borderDistances = borderEdges.flat(1).map(b => distance(0,0,b[0],b[1]));
  let circumscribed = Math.max(...borderDistances);

Main: makeRoundnessFile(tiling)

First set up Max stable + Identity.

Get the value of checkbox roundShow in show_roundness, whether to animate the roundness or not.
After computing the roundness (call to tiling.get_roundness()) and then tiling.iterate():

• add three.LineLoop to app.scene,
• wait for delay,
• update tiling.colorTiles().

It precomputes some global variables (see below), initialize the others, and then the main loop:

• iterate the tiling (tiling.iterate()) until stabilization, measuring the roundness at each step by calling tiling.get_roundness().

Prints some logs, and compile roundness measure in a String roundness_file_text in order to return the intended roundness_file.

The main technicalities are in tiling.get_roundness(), which relies on some global variables to speed up the computation.

Global variables

Computed once by makeRoundnessFile:

• borderTiles, tiles touching the border (ids only, which are integers),
• smallestDistancedict, smallest distance of each tile to (0,0) (this also has to do with tile edges, see Technical considerations),
• biggestDistancedict, biggest distance of each tile to (0,0),
• inscribedCircleRadius, radius of inscribed circle for the whole tiling (call to circles_raddi),
• circumscribedCircleRadius, radius of circumscribed circle for the whole tiling (call to circles_raddi).

Updated at each step by tiling.get_roundness():

• phase = 1;, get_roundness is separated into three subsequent phases according to this,
• outerTiles, the Array of all outerTiles (ids only, which are integers),
• frontierTiles, the Array of outerTiles having a neighbor in innerTiles.

Method doing the job: Tiling.get_roundness()

The method get_roundness() is added to the class Tiling. It relies on global variables (see above), and returns [outerRadius,innerRadius] for the current configuration.

The procedure is separated into three phases (phase transitions are printed in the log), according to the value of phase:

• Phase 1: erratic behavior,
• Phase 2: inner radius smaller than inscribed circle radius,
• Phase 3: border tiles are all outer tiles.

Remark that we can intuitively expect a direct transition from phase 1 to phase 3 when the condition of phase 2 is met (because tiles are polygons, but r_error may mess it up?)

Also Remark that no phase regression is expected, otherwise an outer tiles (from frontierTiles) receives some grain and triggers the toppling of all outerTiles. Phase regressions are nevertheless handled.

Tile Objects and their attribute values are recovered from this.tiles[id] (where id are integers).

phase == 1 (erratic behavior)

In this case the sandpile behavior is still erratic, so outerTiles and frontierTiles are simply recomputed from scratch.

• A FIFO Array of tiles tileStack is used to discover by BFS the set of outerTiles.
• frontierTiles are found by scanning the sand content of outerTiles' neighbors.
• set innerTiles_touches_border = (borderTiles.filter(id => !outerTiles.includes(id)).length == 0);.

phase == 2 (inner radius smaller than inscribed circle radius)

Phase transition is simply checked as

if(innerRadius <= inscribedCircleRadius+r_error){

where r_error is the rounding error set to 0.001.

During this phase the roundness is computed as in phase 1.

phase == 3 (border tiles are all outer tiles)

Phase transition is checked as

if(frontierTiles.filter(id => this.tiles[id].sand != this.tiles[id].limit-1).length == 0){

The circle now shrinks.

If it does not, meaning that some tile from frontierTiles of the last iteration is not anymore an outerTiles (checked with frontierTiles.filter(id => this.tiles[id].sand != this.tiles[id].limit-1).length > 0), then we recompute from scratch by calling phase 2 (phase transition is not logged, its just a hack). This is unexpected, as it would trigger the toppling of all outerTiles, and regression to phase 2 then 1.

• Discover new outerTiles with a FIFO+BFS as in phase 1 and 2, starting from frontierTiles.
• frontierTiles are found as in phase 1, from frontierTiles and new outerTiles only to fasten the process.
• Check regression to phase 2 or 1, even if this should never happen when we are here: regression may happen during the hack above (calling phase 2).

Common closing

• outerRadius is basically computed as Math.min of frontierTiles.map(id => smallestDistancedict.get(id)), with some special treatments when outerTiles is empty or contains all tiles (in this later case frontierTiles is empty and Math.min would return -Inifnity...).
• innerRadius is computed from a subset of innerTiles called innerTiles_sub, and made from borderTiles plus neighbors of frontierTiles. Then it is Math.max of innerTiles_sub.map(id => biggestDistancedict.get(id)), with a special treatment when innerTiles is empty.
• Phase transitions are checked.

Faster Roundness

In order to improve the speed, makeRoundnessFileFast(tiling) is a faster version of roundness, computing only phases 2 and 3:

• iterate phase 1 until phase 2 is reached, checked faster thanks to a pre-check:
  • inscribedTiles is a subset of tiles (only id) required to be outerTiles in order to have innerRadius <= inscribedCircleRadius,
  • pre-check that they may all be outerTiles with

  if(inscribedTiles.filter(id => tiling.tiles[id].sand != tiling.tiles[id].limit-1).length == 0){

  • if pre-check passed, call .get_roundness() to update phase by side-effect.
• check that phase 3 is immediately reached, otherwise fail (log and return;). Because our main optimizations are based on the fast that the circle slowly shrinks, and that this can be discovered locally from frontierTiles.
• then record roundness, expecting no regression of frontierTiles, i.e. frontierTiles from the previous iteration are still outerTiles of the current iteration (otherwise a warning message is logged and the behavior is not guaranteed).

The first line of the output file contains the starting step of phase 2.

Optimizations

Some experiments (see lines with //TIME, now fully in comments) led to the conclusion that updating outerTiles initially took more than 90% of makeRoundnessFileFast execution time. We therefore made the following optimizations on the BFS search for new outerTiles based on tileStack:

• main: use outerTiles_sub maintained as the subset of outerTiles being frontierTiles or neighbors of frontierTiles (the main slowdown was caused by some use of outerTiles.includes(id) for each element of tileStack, but outerTiles was growing until containing all tiling's tiles),
• start the tileStack only with the neighbors of frontierTiles which are not outerTiles (not in outerTiles_sub), this uses our assumption about no regression of frontierTiles,
• add no already known outerTiles (outerTiles_sub) to tileStack,
• remove duplicates in initializations of tileStack and outerTiles_sub.

It is now 4 to 5 times faster than initially ✌️

Show Xscribed radii

The slider button calls radii() to display (in Control bar) and show (in canvas) the inscribed and circumscribed radii of the current tiling.

Show current roundness

The slider button calls roundness() to display (in Control bar) and show (in canvas) the outer and inner radii of the current configuration.

Export frontier to TIKZ

Calls export_frontierTikz() to export the frontier (edges between inner and outer tiles) of the current configuration to tikz, with outer and inner radii.