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) |
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).
-
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.
-
size_sort (pa, pb)
-
Comparator function to sort patterns by their size (number of cells).
Parameters:
- pa
first pattern.
- pb
second pattern.
Returns:
boolean true if pa's size is greater than pb's.
-
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
pattern (domain) 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)
-
Finds the largest contiguous rectangular subpattern within the pattern.
Parameters:
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.
Repeatedly removes boundary cells (while preserving connectivity) until no
further safe removals can be made.
Parameters:
- ip
pattern to thin.
- nbh
(optional) neighbourhood for connectivity (default: neighbourhood.moore()).
Returns:
a new, thinned pattern.
Usage:
local thin_p = p:thin()
-
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)
-
Finds a center-weighted packing offset to place pattern a as close as possible to the center of domain b.
Parameters:
- a
pattern to pack.
- b
domain pattern.
Returns:
a coordinate shift if a valid position is found; nil otherwise.
Usage:
local central_offset = pattern.find_central_packing_position(p, domain)
-
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)
-
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.
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)