Substitution API

General

What?

TilingPresets/SubsitutionAPI.js can help users implement tilings obtained by substitution.
That's a vast world!

Examples can be found in TilingPresets/PenroseP2Substitution.js and TilingPresets/PenroseP3Substitution.js, which use this API to generate respectively Penrose P2 (kite-dart) and Penrose P3 (rhomb) tilings obtained by substitution.

The overall procedure is expected to take time O(n) with n the number of tiles in the generated tiling (assuming time O(1) for Map access), apart from (optional) step 6 and (optional) lazy hack of step 3 (both take time O(n log n)).

Tile `id`

Tile ids are Array of things (e.g. String) with:

element [0] is the tile type,
element [1] is unique in the base tiling,
each subsequent element identifies children of a parent tile.

The API will use id.push(...).
These identifiers must be unique.

How to use this API?

(go) Create base tiles (global variables)
(go) Implement the tile to tile(s) substitution (called as a flatMap)
(go) Provide information about duplicated tiles (via DupInfo)
(go) Implement neighbors update in child tiles (discovered locally)
(go) Clean duplicated tiles (automatic)
(go) (optional) Provide a neighbors index to bounds indices correspondence (for neighbors discovered globally)
(go) Create base tiling and call substitute (requires steps 1-6)

Maybe you want to read step 7 first? This is where your Tiling.mytiling function is implemented.

Note that side effect means a function modifies directly the Objects it receives as argument.

0. Toolbox

id2key(id) converts some Tile.id to something usable as a key in maps (aka dictionaries, JS type Map).
We will denote idkey the key version of a tile id.

1. Base `Tile` Objects

User creates base Tile Objects Each base tile is a global variable, used at step 7 to create base tilings. Each one must have:

a unique id identifying the tile type, e.g. ['kite'] or ['dart'],
bounds (sounds reasonable that a pair of them is (0,0)),
neighbors may be left empty [],
or set all neighbors as undefined [undefined,undefined,...,undefined]
(remember this when creating your base tiling at step 7),
lim.

It may be useful for the substitution implementation (step 2) to have some typeX2typeY method, converting (by side effect) some tile of typeX to typeY at the same position with the same orientation, e.g. Tile.prototype.kite2dart = function(){ update id[0] and move bounds }. Geometric point transformations provided by Utils/Geometry.js may be useful:

scalePoint(xA, yA, xB, yB, f) scales A towards B by factor f (homothecy), returns [new_xA,new_yA],
shiftPoint(xA, yA, xB, yB) shifts A by vector B, returns [new_xA,new_yA],
rotatePoint(xA, yA, xB, yB, a) rotates A around B by angle a (in radian), returns [new_xA,new_yA]
(caution: a positive = counterclockwise, a negative = clockwise).

2. Tile substitution

User creates function mysubstitution(tile){...} implementing the tile to tiles substitution.

input:

a parent Tile to be substituted

output:

(Array of) children Tile replacing the input tile

It will be called at each iteration as a flatMap to the current Array of Tile.

It is very important that a unique element is pushed at the end of each child tile's id, identifying this child of the parent tile. User will also use these identifiers of children in steps 3 and 4.

The following methods may be useful:

Tile.myclone() to clone the parent tile
Tile.typeX2typeY() to convert between tile types (keeping position and orientation)
Tile.scale(...)
Tile.rotate(...)
Tile.shift(...)

Depending on how you initialize neighbors and code neighbors computation:

Tile.resetNeighbors() resets all existing neighbors Array elements to undefined

Newtiles are supposed to be scaled (down) by 1/ratio with ratio the value passed to substitute at step 7.

Typically, after a switch(tile.id[0]){ to handle the different parent tile types, we have something like:

case `kite`:
  // kite -> 2 kites, 2 darts
  var newtiles = []; // once, to store the child tiles
  // first child tile
  var newkite1 = tile.myclone();
  newkite1.id.push('kite1');
  newkite1.scale(tile.bounds[0],tile.bounds[1],1/phi);
  newkite1.rotate(tile.bounds[0],tile.bounds[1],3*Math.PI/5);
  newkite1.shift(tile.bounds[2]-tile.bounds[0],tile.bounds[3]-tile.bounds[1]);
  newtiles.push(newkite1);
  // second child tile
  ...
  return newtiles;
  break;

The substitution may create duplicated tiles, i.e. child tiles from two parent neighboring tiles, which (the child tiles) overlap completely. This is then handled at step 3.

3. Duplicated tiles

User provides information on duplicated tiles as mydupinfos an Array of DupInfo, and as mydupinfosoriented an Array of DupInfoOriented.

Indeed, it often happens that the substitution "déborde", and as a consequence neighboring parent tiles may create twice a same child tile. If your substitution is very nice and does not have this issue, then simply set mydupinfos=[]; and mydupinfosoriented=[];. Otherwise init to [] and then mydupinfos.push(new DupInfo(...)); or mydupinfosoriented.push(new DupInfoOriented(...)); for each potential duplicate case.

DupInfo is the data structure storing information about the potential duplicated children of a parent tile.
Its constructor new DupInfo(ptype,type,id,index,potype,oid) means the following:
if parent is ptype and parent.neighbors[index] is potype, then "id child of parent" is a duplicate of "oid child of parent.neighbors[index] (both are type).
E.g. duplicatedP2.push(new DupInfo('kite','dart','dart2',3,'kite','dart1')); means that if neighbor 3 of a parent kite is a also a kite, then the child dart2 of this parent is a duplicate of the child dart1 of this neighbor (children are both of type dart).

If the identification of the duplicated tile also depends on the matching side of the neighboring tile (i.e. on its orientation), then use data structure DupInfoOriented.
Its constructor new DupInfoOriented(ptype,type,id,index,potype,oid,oindex) means the following:
if parent is ptype and parent.neighbors[index] is potype, and if furthermore the former is neighbor 'oindex' of the latter, then "id child of parent" is a duplicate of "oid child of parent.neighbors[index] (both are type).
E.g. this is required for Ammann-Beenker substitution.
Note that user must (if it applies) handle by him·herself this orientation business at step 4.

A map of duplicated (child) tiles will be created for user to use at step 4:

idkey of duplicated -> id of original.

The method isDup(newdup, pid, id, type) may be useful at step 4, it checks if child id of pid is a duplicated tile, with:

newdup the map of duplicated child tiles
pid the parent of id (Array)
id the child identifier (last part)
type the child tile type

Step 5 will (automatically) handle the deletion of duplicated tiles and update Tile.neighbors when it contains duplicated tiles.

4. Compute neighbors

It is recommended to number neighbors of each tile from 0 to tile.bounds.length/2-1 following the order of tile.bounds, ie tile.neighbors[i] is along segment (tile.bounds[2*i],tile.bounds[2*i+1]) -- (tile.bounds[2*i+2],tile.bounds[2*i+3]) (with a modulo tile.bounds.length).

Lazy?
This part of the process may be a bit tedious/boring.
If user is lazy, then set myneighbors="I am lazy";.
Cost: O(n log n) as findNeighbors which will do all the job (see step 6), but with a bigger n (number of tiles times number of neighbors per tile).
Nevertheless, lazy user must provide duplicated tiles information (step 3), and must also provide a neighbors to bounds correspondence (step 6), in accordance one with the other regarding the neighbors ordering.
User do not need to set neighbors for tiles of the base tiling (leave them as []), because in lazy mode the call to substitute (step 7) will initialize it before calling findNeighbors (which will be called at each iteration so that duplicated tiles are removed).
See BirdsBeesSubstitution.js for an example.

User creates a function myneighbors to fill (by side effect) neighbors of the new tiles.
input:

Array of parent Tile
Map of parent Tile (idkey -> Tile) for convenient access
Array of child Tile (obtained from mysubstitution)
Map of child Tile (idkey -> Tile) for convenient access
Map of duplicated child tiles (idkey -> id of original)

no output, just return;.

Child tiles' neighbors elements are computed locally based on the parent's neighbors, therefore it may be natural to iterate over the Array of parent tiles. Non-local neighbors are (optionally) handled at step 6.

Recall: you may have used Tile.resetNeighbors() at step 2.

Remark: no need to fill neighbors of duplicated tiles (see isDup from step 3).

The cleaning of duplicated tiles at step 5 will update the neighbors elements which are id of duplicated tiles. It means that you may set as neighbor some tiles which turn out to be duplicated, the replacement for the original tile will be handled automatically from mydupinfos.

Tip: maps may be useful to get the neighbor of a neighbor, do not forget to use id2key(id) (see step 0) when calling .has and .get methods.

Some useful methods (made for this purpose):

setNeighbor(newtilesdict, pid, id, type, i, pnid, nid, ntype) modifies newtilesdict (map of child tiles) by setting child nid (of type ntype) of parent pnid as neighbor of index i of child id (of type type) of parent pid, with:
- pid the parent id (Array)
- id the child id (last part)
- type the child type
- i the neighbors index (integer)
- pnid the neighbors parent id (Array)
- nid the neighbors id (last part)
- ntype the neighbors type
setNeighborUndefined(newtilesdict, pid, id, type, i) same as above but set the neighbor as undefined, meaning that there is no neighboring tile on this side.

For example, neighbor 0 of the kite1 child of a parent kite is set as follows:

function neighborsP2(tiles,tilesdict,newtiles,newtilesdict,newdup){
  // iterate tiles and fill neighbors of newtiles
  for(let tile of tiles) {
    switch(tile.id[0]){
      case 'kite':
        //
        // new kite 1
        //
        // neighbor 0
        if(tile.neighbors[1] != undefined){
          switch(tile.neighbors[1][0]){
            case 'kite':
              setNeighbor(newtilesdict,tile.id,'kite1','kite',0,tile.neighbors[1],'kite2','kite');
              break;
            case 'dart':
              setNeighbor(newtilesdict,tile.id,'kite1','kite',0,tile.neighbors[1],'dart1','dart');
          }
        }
        else{
          setNeighborUndefined(newtilesdict,tile.id,'kite1','kite',0);
        }
        // neighbor 1
        ...

5. Clean duplicates (automatic)

clean removes duplicated tiles and updates neighbors, it will be called automatically by substitute at step 7 from the information provided at step 3.

6. (optional) Non-local neighbors

findNeighbors checks if non-neighboring tiles have neighboring children, in time O(n log n) with n the number of undefined elements in neighbors (hoping that JS Array.sort() implements quicksort).

It happens for example in Penrose tilings, that tiles far apart may have neighboring children, the purpose of this global neighbors finder

In order to use this option and trigger the call to findNeighbors, user must provide a neighbor index to bounds indices correspondence, as myneighbors2bounds: a Map associating to each tile type an Array of neighbors.length Arrays of four indices (these latter corresponding to bounds). Element i of the Array is an Array of four indices [i_1,i_2,i_3,i_4] meaning that the tile side (segment) corresponding toneighbors[i] is given by coordinates (bounds[i_1],bounds[i_2]) -- (bounds[i_3],bounds[i_4]). E.g. 'kite' -> [[0,1,2,3],[2,3,4,5],[4,5,6,7],[6,7,0,1]] is the default.

The default neighbor index to bounds indices correspondence is that tile.neighbors[i] corresponds to segment (tile.bounds[2*i],tile.bounds[2*i+1]) -- (tile.bounds[2*i+2],tile.bounds[2*i+3]) (with a modulo tile.bounds.length). If this is not the case in user's implementation, then user provides its own correspondence for each tile type, as a map described above. In any case it is expected that tile.bounds.length = 2*tile.neighbors.length.

To use the default correspondence, for example:

var neighbors2boundsP2 = new Map();
neighbors2boundsP2.set('kite',default_neighbors2bounds(4));
neighbors2boundsP2.set('dart',default_neighbors2bounds(4));

Remark: this procedure of undefined neighbors matching takes into account rounding errors in coordinates computation, up to a distance between two points (expected to be identical) less than p_error=0.001 (value when this wiki page is written).

7. Calling the substitute method

At this point the user (eventually!) writes its Tiling.mytiling function:

define a base tiling
call substitute
return a Tiling

Tiling.mytiling = function({iterations}={}){
  // 1.
  var tiles = [];
  ...
  tiles.push(mytile1);
  ...

Tip: use the base tiles from step 1 and myclone() method, do not forget to fill neighbors for tiles of the base tiling and set the boundary as undefined (except for lazy user).

  // 2.
  tiles = substitute(...);

substitute takes as input:

number of iterations (iterations)
Array of Tile (aka base tiling)
scaling ratio of the substitution
mysubstitution (see step 2)
mydupinfos (see step 3)
mydupinfosoriented (see step 3)
myneighbors (see step 4)
(optional) whether to call findNeighbors (see step 6), one of:
- false
- myneighbors2bounds
(optional) an initial sand content for each tile type (based on id[0]), one of:
- false
- an exhaustive Map tile type -> integer

Be careful that to use the second option without using the first, the first must be set to false. It's less error-prone to just set any option you don't want to use to false.

  // 3.
  return new Tiling(tiles);
}

What is substitute doing? See its fairly simple code at the bottom of SubstitutionAPI.js

Example definition of base tiling and call to substitute:

var decorateP2 = new Map();
decorateP2.set('kite',0);
decorateP2.set('dart',1);

Tiling.P2sunbysubst = function({iterations}={}){
  var tiles = [];
  // push base "sun" tiling
  for(var i=0; i<5; i++){
    // construct tiles
    var mykite = kite.myclone();
    mykite.id.push(i);
    mykite.rotate(0,0,i*2*Math.PI/5);
    // define neighbors with undefined on the boundary
    mykite.neighbors.push(['kite',(i-1+5)%5]); // 0
    mykite.neighbors.push(undefined); // 1
    mykite.neighbors.push(undefined); // 2
    mykite.neighbors.push(['kite',(i+1)%5]); // 3
    tiles.push(mykite);
  }
  // call the substitution
  tiles = substitute(
    iterations,
    tiles,
    phi,
    substitutionP2,
    duplicatedP2,
    duplicatedP2oriented,
    neighborsP2,
    neighbors2boundsP2,
    decorateP2
  );
  // construct tiling
  return new Tiling(tiles);
}

Do not forget to include your new tiling preset in JS-Sandpile.html.

Home

Usage

Code

Extra

Laser-cut & 3d print

Navigation Menu

Substitution API

General

What?

Tile `id`

How to use this API?

0. Toolbox

1. Base `Tile` Objects

2. Tile substitution

3. Duplicated tiles

4. Compute neighbors

5. Clean duplicates (automatic)

6. (optional) Non-local neighbors

7. Calling the substitute method

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Clone this wiki locally

Substitution API

General

What?

Tile id

How to use this API?

0. Toolbox

1. Base Tile Objects

2. Tile substitution

3. Duplicated tiles

4. Compute neighbors

5. Clean duplicates (automatic)

6. (optional) Non-local neighbors

7. Calling the substitute method

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Clone this wiki locally

Tile `id`

1. Base `Tile` Objects