Module forma.pattern
A class containing a set (or pattern) of cells.
The pattern class is the central class of forma, representing a set of
points or cells. It can be initialized empty or using a prototype (an N×M
matrix of 1's and 0's). Helper methods for initialization are provided in the
primitives module. Once created, a pattern is modified only via the insert
method—other manipulations return new patterns.
Pattern manipulators include methods like translate, enlarge, rotate,
hreflect, and vreflect. Other operations, such as computing the exterior_hull
or interior_hull, help determine the boundaries of a pattern.
Coordinates are maintained reliably in the range [-65536, 65536], which can be
adjusted via the MAX_COORDINATE constant.
Functions can be invoked either procedurally:
pattern.method(input_pattern, ... )
or as methods:
input_pattern:method(... )
Usage:
-- Procedural style:
local p1 = pattern.new()
pattern.insert(p1, 1, 1)
-- Method chaining:
local p2 = pattern.new():insert(1, 1)
-- Prototype style:
local p3 = pattern.new({{1,1,1}, {1,0,1}, {1,1,1}})
-- Retrieve a random cell and the medoid cell:
local random_cell = p1:rcell()
local medoid_cell = p1:medoid()
-- Compute the exterior hull using the Moore neighbourhood:
local outer_hull = p1:exterior_hull(neighbourhood.moore())
-- or equivalently:
outer_hull = pattern.exterior_hull(p1, neighbourhood.moore())
| union (...) |
Returns the union of a set of patterns. |
| intersect (...) |
Returns the intersection of multiple patterns (cells common to all). |
| xor (a, b) |
Returns the symmetric difference (XOR) of two patterns. |
| __tostring (ip) |
Renders the pattern as a string. |
| __add (a, b) |
Adds two patterns using the '+' operator (i.e. |
| __sub (a, b) |
Subtracts one pattern from another using the '-' operator. |
| __mul (a, b) |
Computes the intersection of two patterns using the '*' operator. |
| __pow (a, b) |
Computes the symmetric difference (XOR) of two patterns using the '^' operator. |
| __eq (a, b) |
Tests whether two patterns are identical. |
| translate (ip, sx, sy) |
Returns a new pattern translated by a vector (sx, sy). |
| normalise (ip) |
Normalizes the pattern by translating it so that its minimum coordinate is (0,0). |
| enlarge (ip, f) |
Returns an enlarged version of the pattern. |
| rotate (ip) |
Returns a new pattern rotated 90° clockwise about the origin. |
| vreflect (ip) |
Returns a new pattern that is a vertical reflection of the original. |
| hreflect (ip) |
Returns a new pattern that is a horizontal reflection of the original. |
| connected_components (ip, nbh) |
Returns a multipattern of the connected components within the pattern. |
| interior_holes (ip, nbh) |
Returns a multipattern of the interior holes of the pattern. |
| bsp (ip, th_volume, alpha) |
Partitions the pattern using binary space partitioning (BSP). |
| neighbourhood_categories (ip, nbh) |
Categorizes cells in the pattern based on neighbourhood configurations. |
| perlin (ip, freq, depth, thresholds, rng) |
Applies Perlin noise sampling to the pattern. |
| voronoi (seeds, domain, measure) |
Generates Voronoi tessellation segments for a domain based on seed points. |
| voronoi_relax (seeds, domain, measure, max_ite) |
Performs centroidal Voronoi tessellation (Lloyd's algorithm) on a set of seeds. |
Here are the basic functions for creating and manipulating patterns.
-
new (prototype)
-
Pattern constructor.
Returns a new pattern. If a prototype is provided (an N×M table of 1's and 0's),
the corresponding active cells are inserted.
Parameters:
- prototype
(optional) an N×M table of ones and zeros.
Returns:
a new pattern according to the prototype.
-
clone (ip)
-
Creates a copy of an existing pattern.
Parameters:
- ip
input pattern to clone.
Returns:
a new pattern that is a duplicate of ip.
-
insert (ip, x, y)
-
Inserts a new cell into the pattern.
Returns the modified pattern to allow for method chaining.
Parameters:
- ip
pattern to modify.
- x
x-coordinate (integer) of the new cell.
- y
y-coordinate (integer) of the new cell.
Returns:
the updated pattern (for cascading calls).
-
remove (ip, x, y)
-
Removes a cell from the pattern.
Returns the modified pattern to allow for method chaining.
The bounding box is lazily recomputed when next accessed if the removed
cell was on the boundary.
Parameters:
- ip
pattern to modify.
- x
x-coordinate (integer) of the cell to remove.
- y
y-coordinate (integer) of the cell to remove.
Returns:
the updated pattern (for cascading calls).
-
has_cell (ip, x, y)
-
Checks if a cell at (x, y) is active in the pattern.
Parameters:
- ip
pattern to check.
- x
x-coordinate (integer).
- y
y-coordinate (integer).
Returns:
boolean true if the cell is active, false otherwise.
-
filter (ip, fn)
-
Filters the pattern using a boolean callback, returning a subpattern.
Parameters:
- ip
the original pattern.
- fn
a function(cell) -> boolean that determines if a cell is kept.
Returns:
a new pattern containing only the cells that pass the filter.
-
size (ip)
-
Returns the number of active cells in the pattern.
Parameters:
Returns:
integer count of active cells.
-
recalculate_bounding_box (ip)
-
Recalculates the bounding box of the pattern.
This is a slow O(N) operation. It is called automatically (lazily) when
the bounding box is accessed after a remove operation on a boundary cell.
Manual calls are only needed after directly modifying pattern internals.
Parameters:
-
size_sort (pa, pb)
-
Comparator function to sort patterns by their size (descending).
Parameters:
- pa
first pattern.
- pb
second pattern.
Returns:
boolean true if pa's size is greater than pb's.
-
inverse_size_sort (pa, pb)
-
Comparator function to sort patterns by their size (ascending).
Parameters:
- pa
first pattern.
- pb
second pattern.
Returns:
boolean true if pa's size is less than pb's.
-
bounding_box_density (ip)
-
Computes how densely the bounding box is filled.
Returns zero for an empty pattern.
Parameters:
Returns:
float the fraction of the bounding box that is occupied
-
bounding_box_asymmetry (ip)
-
Computes the asymmetry of the pattern's bounding box.
Returns zero in the case of an empty pattern.
Parameters:
Returns:
float the ratio of the bounding box's longest to shortest edge
-
count_neighbors (p, nbh, arg1, arg2)
-
Counts active neighbors around a specified cell within the pattern.
Can be invoked with either a cell object or with x and y coordinates.
Parameters:
- p
a pattern.
- nbh
a neighbourhood (e.g., neighbourhood.moore()).
- arg1
either a cell (with x and y fields) or the x-coordinate (integer).
- arg2
(optional) the y-coordinate (integer) if arg1 is not a cell.
Returns:
integer count of active neighbouring cells.
-
cell_list (ip)
-
Returns a list (table) of active cells in the pattern.
Parameters:
- ip
pattern to list cells from.
Returns:
table of cell objects.
-
edit_distance (a, b)
-
Computes the edit distance between two patterns (the total number of differing cells).
Parameters:
- a
first pattern.
- b
second pattern.
Returns:
integer representing the edit distance.
-
union (...)
-
Returns the union of a set of patterns.
Parameters:
- ...
a table of patterns or a list of pattern arguments.
Returns:
a new pattern that is the union of the provided patterns.
-
intersect (...)
-
Returns the intersection of multiple patterns (cells common to all).
Parameters:
- ...
two or more patterns to intersect.
Returns:
a new pattern of cells that exist in every input pattern.
-
xor (a, b)
-
Returns the symmetric difference (XOR) of two patterns.
Cells are included if they exist in either pattern but not in both.
Parameters:
- a
first pattern.
- b
second pattern.
Returns:
a new pattern representing the symmetric difference.
-
cells (ip)
-
Iterator over active cells in the pattern.
Parameters:
- ip
pattern to iterate over.
Returns:
iterator that returns each active cell as a cell object.
Usage:
for cell in p:cells() do
print(cell.x, cell.y)
end
-
cell_coordinates (ip)
-
Iterator over active cell coordinates (x, y) in the pattern.
Parameters:
- ip
pattern to iterate over.
Returns:
iterator that returns the x and y coordinates of each active cell.
Usage:
for x, y in p:cell_coordinates() do
print(x, y)
end
-
shuffled_cells (ip, rng)
-
Returns an iterator over active cells in randomized order.
Parameters:
- ip
pattern to iterate over.
- rng
(optional) random number generator (e.g., math.random).
Returns:
iterator that yields each active cell (cell object) in a random order.
Usage:
for cell in pattern.shuffled_cells(p) do
print(cell.x, cell.y)
end
-
shuffled_coordinates (ip, rng)
-
Returns an iterator over active cell coordinates in randomized order.
Parameters:
- ip
pattern to iterate over.
- rng
(optional) random number generator (e.g., math.random).
Returns:
iterator that yields x and y coordinates in random order.
Usage:
for x, y in pattern.shuffled_coordinates(p) do
print(x, y)
end
-
__tostring (ip)
-
Renders the pattern as a string.
Active cells are shown with pattern.onchar and inactive cells with pattern.offchar.
Parameters:
Returns:
string representation of the pattern.
Usage:
print(p)
-
__add (a, b)
-
Adds two patterns using the '+' operator (i.e. returns their union).
Parameters:
- a
first pattern.
- b
second pattern.
Returns:
a new pattern representing the union of a and b.
Usage:
local combined = p1 + p2
-
__sub (a, b)
-
Subtracts one pattern from another using the '-' operator.
Returns a new pattern with cells in a that are not in b.
Parameters:
- a
base pattern.
- b
pattern to subtract from a.
Returns:
a new pattern with the difference.
Usage:
local diff = p1 - p2
-
__mul (a, b)
-
Computes the intersection of two patterns using the '*' operator.
Parameters:
- a
first pattern.
- b
second pattern.
Returns:
a new pattern containing only the cells common to both.
Usage:
local common = p1 * p2
-
__pow (a, b)
-
Computes the symmetric difference (XOR) of two patterns using the '^' operator.
Parameters:
- a
first pattern.
- b
second pattern.
Returns:
a new pattern with cells present in either a or b, but not both.
Usage:
local xor_pattern = p1 ^ p2
-
__eq (a, b)
-
Tests whether two patterns are identical.
Parameters:
- a
first pattern.
- b
second pattern.
Returns:
boolean true if the patterns are equal, false otherwise.
Usage:
if p1 == p2 then
end
-
centroid (ip)
-
Computes the centroid (arithmetic mean) of all cells in the pattern.
The result is rounded to the nearest integer coordinate.
Parameters:
Returns:
a cell representing the centroid (which may not be active).
Usage:
local center = p:centroid()
-
medoid (ip, measure)
-
Computes the medoid cell of the pattern.
The medoid minimizes the total distance to all other cells (using Euclidean distance by default).
Parameters:
- ip
pattern to process.
- measure
(optional) distance function (default: Euclidean).
Returns:
the medoid cell of the pattern.
Usage:
local medoid = p:medoid()
-
rcell (ip, rng)
-
Returns a random cell from the pattern.
Parameters:
- ip
pattern to sample from.
- rng
(optional) random number generator (e.g., math.random).
Returns:
a random cell from the pattern.
Usage:
local random_cell = p:rcell()
-
translate (ip, sx, sy)
-
Returns a new pattern translated by a vector (sx, sy).
Parameters:
- ip
pattern to translate.
- sx
translation along the x-axis (integer).
- sy
translation along the y-axis (integer).
Returns:
a new pattern shifted by (sx, sy).
Usage:
local p_translated = p:translate(2, 3)
-
normalise (ip)
-
Normalizes the pattern by translating it so that its minimum coordinate is (0,0).
Parameters:
Returns:
a new normalized pattern.
Usage:
local p_norm = p:normalise()
-
enlarge (ip, f)
-
Returns an enlarged version of the pattern.
Each active cell is replaced by an f×f block.
Parameters:
- ip
pattern to enlarge.
- f
enlargement factor (number).
Returns:
a new enlarged pattern.
Usage:
local p_big = p:enlarge(2)
-
rotate (ip)
-
Returns a new pattern rotated 90° clockwise about the origin.
Parameters:
Returns:
a rotated pattern.
Usage:
local p_rotated = p:rotate()
-
vreflect (ip)
-
Returns a new pattern that is a vertical reflection of the original.
Parameters:
- ip
pattern to reflect vertically.
Returns:
a vertically reflected pattern.
Usage:
local p_vreflected = p:vreflect()
-
hreflect (ip)
-
Returns a new pattern that is a horizontal reflection of the original.
Parameters:
- ip
pattern to reflect horizontally.
Returns:
a horizontally reflected pattern.
Usage:
local p_hreflected = p:hreflect()
-
sample (ip, ncells, rng)
-
Returns a random subpattern containing a fixed number of cells.
Parameters:
- ip
pattern (domain) to sample from.
- ncells
number of cells to sample (integer).
- rng
(optional) random number generator (e.g., math.random).
Returns:
a new pattern with ncells randomly selected cells.
Usage:
local sample = p:sample(10)
-
sample_poisson (ip, distance, radius, rng)
-
Returns a Poisson-disc sampled subpattern.
Ensures that no two sampled cells are closer than the given radius.
Parameters:
- ip
pattern (domain) to sample from.
- distance
distance function (e.g., cell.euclidean).
- radius
minimum separation (number).
- rng
(optional) random number generator (e.g., math.random).
Returns:
a new pattern sampled with Poisson-disc criteria.
Usage:
local poisson_sample = p:sample_poisson(cell.euclidean, 5)
-
sample_mitchell (ip, distance, n, k, rng)
-
Returns an approximate Poisson-disc sample using Mitchell's best candidate algorithm.
Parameters:
- ip
the input pattern to sample from.
- distance
distance function (e.g., cell.euclidean).
- n
number of samples (integer).
- k
number of candidate attempts per iteration (integer).
- rng
(optional) random number generator (e.g., math.random).
Returns:
a new pattern with n samples chosen via the algorithm.
Usage:
local mitchell_sample = p:sample_mitchell(cell.euclidean, 10, 5)
-
floodfill (ip, icell, nbh)
-
Returns the contiguous subpattern (connected component) starting from a given cell.
Parameters:
- ip
pattern upon which the flood fill is to be performed.
- icell
a cell specifying the origin of the flood fill.
- nbh
(optional) neighbourhood to use (default: neighbourhood.moore()).
Returns:
a new pattern containing the connected component.
Usage:
local component = p:floodfill(cell.new(2, 3))
-
max_rectangle (ip, alpha)
-
Finds the largest contiguous rectangular subpattern within the pattern.
Parameters:
- ip
pattern to analyze.
- alpha
'squareness' parameter. 0 for max rectangle, 1 for max square.
Returns:
a subpattern representing the maximal rectangle.
Usage:
local rect = p:max_rectangle()
-
convex_hull (ip)
-
Computes the convex hull of the pattern.
The hull points are connected using line rasterization.
Parameters:
Returns:
a new pattern representing the convex hull.
Usage:
local hull = p:convex_hull()
-
thin (ip, nbh)
-
Returns a thinned (skeletonized) version of the pattern.
Iteratively removes border cells whose Moore neighbours remain a single
connected component under
nbh.
Parameters:
Returns:
a new, thinned pattern.
Usage:
local thin_p = p:thin()
local thin_4 = p:thin(neighbourhood.von_neumann())
-
erode (ip, nbh)
-
Returns the erosion of the pattern.
A cell is retained only if all of its neighbours (as defined by nbh) are active.
Parameters:
- ip
pattern to erode.
- nbh
neighbourhood (default: neighbourhood.moore()).
Returns:
a new, eroded pattern.
Usage:
local eroded = p:erode(neighbourhood.moore())
-
dilate (ip, nbh)
-
Returns the dilation of the pattern.
Each active cell contributes its neighbours (as defined by nbh) to the result.
Parameters:
- ip
pattern to dilate.
- nbh
neighbourhood (default: neighbourhood.moore()).
Returns:
a new, dilated pattern.
Usage:
local dilated = p:dilate(neighbourhood.moore())
-
gradient (ip, nbh)
-
Returns the morphological gradient of the pattern.
Computes the difference between the dilation and erosion.
Parameters:
- ip
pattern to process.
- nbh
neighbourhood for dilation/erosion (default: neighbourhood.moore()).
Returns:
a new pattern representing the gradient.
Usage:
local grad = p:gradient(neighbourhood.moore())
-
opening (ip, nbh)
-
Returns the morphological opening of the pattern.
Performs erosion followed by dilation to remove small artifacts.
Parameters:
- ip
pattern to process.
- nbh
neighbourhood (default: neighbourhood.moore()).
Returns:
a new, opened pattern.
Usage:
local opened = p:opening(neighbourhood.moore())
-
closing (ip, nbh)
-
Returns the morphological closing of the pattern.
Performs dilation followed by erosion to fill small holes.
Parameters:
- ip
pattern to process.
- nbh
neighbourhood (default: neighbourhood.moore()).
Returns:
a new, closed pattern.
Usage:
local closed = p:closing(neighbourhood.moore())
-
interior_hull (ip, nbh)
-
Returns a pattern of cells that form the interior hull.
These are cells that neighbor inactive cells while still belonging to the pattern.
Parameters:
- ip
pattern to process.
- nbh
neighbourhood (default: neighbourhood.moore()).
Returns:
a new pattern representing the interior hull.
Usage:
local interior = p:interior_hull(neighbourhood.moore())
-
exterior_hull (ip, nbh)
-
Returns a pattern of cells that form the exterior hull.
This consists of inactive neighbours of the pattern, useful for enlarging or
determining non-overlapping borders.
Parameters:
- ip
pattern to process.
- nbh
neighbourhood (default: neighbourhood.moore()).
Returns:
a new pattern representing the exterior hull.
Usage:
local exterior = p:exterior_hull(neighbourhood.moore())
-
find_packing_position (a, b, rng)
-
Finds a packing offset where pattern a fits entirely within domain b.
Returns a coordinate shift that, when applied to a, makes it tile inside b.
Parameters:
- a
pattern to pack.
- b
domain pattern in which to pack a.
- rng
(optional) random number generator (e.g., math.random).
Returns:
a cell (as a coordinate shift) if a valid position is found; nil otherwise.
Usage:
local offset = pattern.find_packing_position(p, domain)
-
find_central_packing_position (a, b, c)
-
Finds a center-weighted packing offset to place pattern a within pattern
b as close as possible to the cell c. If no
c is provided, then the centroid
of pattern b is used.
Parameters:
- a
pattern to pack.
- b
domain pattern.
- c
(optional) cell to act as a center for packing.
Returns:
a coordinate shift if a valid position is found; nil otherwise.
Usage:
local central_offset = pattern.find_central_packing_position(p, domain, c)
-
connected_components (ip, nbh)
-
Returns a multipattern of the connected components within the pattern.
Uses flood-fill to extract contiguous subpatterns.
Parameters:
- ip
pattern to analyze.
- nbh
neighbourhood (default: neighbourhood.moore()).
Returns:
a multipattern containing each connected component as a subpattern.
Usage:
local components = p:connected_components(neighbourhood.moore())
-
interior_holes (ip, nbh)
-
Returns a multipattern of the interior holes of the pattern.
Interior holes are inactive regions completely surrounded by active cells.
Parameters:
- ip
pattern to analyze.
- nbh
neighbourhood (default: neighbourhood.von_neumann()).
Returns:
a multipattern of interior hole subpatterns.
Usage:
local holes = p:interior_holes(neighbourhood.von_neumann())
-
bsp (ip, th_volume, alpha)
-
Partitions the pattern using binary space partitioning (BSP).
Recursively subdivides contiguous rectangular areas until each partition's volume is below th_volume.
Parameters:
- ip
pattern to partition.
- th_volume
threshold volume (number) for final partitions.
- alpha
(optional) parameter for squareness of BSP.
Returns:
a multipattern of BSP subpatterns.
Usage:
local partitions = p:bsp(50)
-
neighbourhood_categories (ip, nbh)
-
Categorizes cells in the pattern based on neighbourhood configurations.
Returns a multipattern with one subpattern per neighbourhood category.
Parameters:
- ip
pattern whose cells are to be categorized.
- nbh
neighbourhood used for categorization.
Returns:
a multipattern with each category represented as a subpattern.
Usage:
local categories = p:neighbourhood_categories(neighbourhood.moore())
-
perlin (ip, freq, depth, thresholds, rng)
-
Applies Perlin noise sampling to the pattern.
Generates a multipattern by thresholding Perlin noise values at multiple levels.
Parameters:
- ip
pattern (domain) to sample from.
- freq
frequency for Perlin noise (number).
- depth
sampling depth (integer).
- thresholds
table of threshold values (each between 0 and 1).
- rng
(optional) random number generator (e.g., math.random).
Returns:
a multipattern with one component per threshold level.
Usage:
local noise_samples = p:perlin(0.1, 4, {0.3, 0.5, 0.7})
-
voronoi (seeds, domain, measure)
-
Generates Voronoi tessellation segments for a domain based on seed points.
Parameters:
- seeds
pattern containing seed cells.
- domain
pattern defining the tessellation domain.
- measure
distance function (e.g., cell.euclidean).
Returns:
a multipattern of Voronoi segments.
Usage:
local segments = pattern.voronoi(seeds, domain, cell.euclidean)
-
voronoi_relax (seeds, domain, measure, max_ite)
-
Performs centroidal Voronoi tessellation (Lloyd's algorithm) on a set of seeds.
Iteratively relaxes seed positions until convergence or a maximum number of iterations.
Parameters:
- seeds
initial seed pattern.
- domain
tessellation domain pattern.
- measure
distance function (e.g., cell.euclidean).
- max_ite
(optional) maximum iterations (default: 30).
Returns:
a multipattern of Voronoi segments, a pattern of relaxed seed positions, and a boolean convergence flag.
Usage:
local segments, relaxed_seeds, converged = pattern.voronoi_relax(seeds, domain, cell.euclidean)
-
get_max_coordinate ()
-
Returns the maximum allowed coordinate for spatial hashing.
Returns:
maximum coordinate value (number).
Usage:
local max_coord = pattern.get_max_coordinate()
-
test_coordinate_map (x, y)
-
Tests the conversion between (x, y) coordinates and the spatial hash key.
Parameters:
- x
test x-coordinate (number).
- y
test y-coordinate (number).
Returns:
boolean true if the conversion is correct, false otherwise.
Usage:
local valid = pattern.test_coordinate_map(10, 20)
-
print (ip, char, domain, printer)
-
Prints the pattern within an optional domain, line-by-line.
Parameters: