Module forma.subpattern
Sub-pattern finders.
Functions for the selection of sub-patterns of various forms from a parent pattern. The simplest of these is the random sampling of a fraction of cells from the parent.
Several of these finders return a table of all relevant sub-patterns. For example the segments method which returns a table of all contiguous (according to some neighbourhood) sub-patterns by using a floodfill.
In addition to the subpattern finders, a print_patterns utility is provided to render these tables of sub-patterns into text.
Sub-patterns
mask (ip, mask) | Masked subpattern. |
random (ip, ncells, rng) | Random subpattern. |
poisson_disc (ip, distance, radius, rng) | Poisson-disc random subpattern. |
mitchell_sample (ip, distance, n, k, rng) | Mitchell's best candidate sampling. |
perlin (ip, freq, depth, thresholds, rng) | Perlin noise sampling. |
floodfill (ip, ipt, nbh) | Returns the contiguous sub-pattern of ip that surrounts cell ipt |
maxrectangle (ip) | Find the maximal contiguous rectangular area within a pattern. |
Lists of sub-patterns
segments (ip, nbh) | Generate a table of contiguous 'segments' or sub-patterns. |
enclosed (ip, nbh) | Returns a table of 'enclosed' segments of a pattern. |
bsp (ip, th_volume) | Generate subpatterns by binary space partition. |
neighbourhood_categories (ip, nbh) | Determine subpatterns for all neighbourhood categories. |
voronoi (seeds, domain, measure) | Generate Voronoi tesselations of cells in a domain. |
voronoi_relax (seeds, domain, measure, max_ite) | Generate (approx) centroidal Voronoi tessellation. |
convex_hull_points (ip) | Compute the points lying on the convex hull of a pattern. |
convex_hull (ip) | Compute the convex hull of a pattern. |
Utilities
print_patterns (domain, segments, chars) | Print a table of forma.patterns. |
Sub-patterns
- mask (ip, mask)
-
Masked subpattern.
Generate a subpattern by applying a boolean mask to an input pattern.
Parameters:
- ip the pattern to be masked.
- mask a function that takes a cell and returns true if the cell passes the mask
Returns:
-
A pattern consisting only of those cells in
domain
which pass the mask argument. - random (ip, ncells, rng)
-
Random subpattern.
For a given domain, returns a pattern sampling randomly from it, generating a random
subset with a fixed fraction of the size of the domain.
Parameters:
- ip pattern for sampling a random pattern from
- ncells the number of desired cells in the sample
- rng (optional) a random number generator, following the signature of math.random.
Returns:
-
a pattern of
ncells
cells sampled randomly fromdomain
- poisson_disc (ip, distance, radius, rng)
-
Poisson-disc random subpattern.
Sample a domain according to the Poisson-disc procedure. For a given
distance measure
distance
, this generates samples that are never closer together than a specified radius. While much slower than subpattern.random, it provides a more uniform distribution of points in the domain (simmilar to that of subpattern.voronoi_relax).Parameters:
- ip domain pattern to sample from
- distance a measure of distance between two cells d(a,b) e.g cell.euclidean
- radius
the minimum separation in
distance
between two sample points. - rng (optional) a random number generator, following the signature of math.random.
Returns:
-
a Poisson-disc sample of
domain
- mitchell_sample (ip, distance, n, k, rng)
-
Mitchell's best candidate sampling.
Generates an approximate Poisson-disc sampling by Mitchell's algorithm.
Picks 'k' sample point attempts at every iteration, and picks the candidate
that maximises the distance to existing samples. Halts when
n
samples are picked.Parameters:
- ip domain pattern to sample from
- distance a measure of distance between two cells d(a,b) e.g cell.euclidean
- n the requested number of samples
- k the number of candidates samples at each iteration
- rng (optional) a random number generator, following the signature of math.random.
Returns:
-
an approximate Poisson-disc sample of
domain
- perlin (ip, freq, depth, thresholds, rng)
-
Perlin noise sampling.
Samples an input pattern by thresholding a Perlin-noise pattern in the
domain. This function takes an initial sampling frequency, and computes
perlin noise over the input pattern by taking the product of
depth
successively halved frequencies. A table of subpatterns are then returned, consisting of the perlin noise function thresholded at requested levels.Parameters:
- ip pattern upon which the thresholded noise sampling is to be performed.
- freq (float) frequency of desired perlin noise
- depth (int), sampling depth.
- thresholds table of sampling thresholds (between 0 and 1).
- rng (optional) a random number generator, following the signature of math.random.
Returns:
-
a table of
patterns
, one per threshold entry. - floodfill (ip, ipt, nbh)
-
Returns the contiguous sub-pattern of ip that surrounts cell ipt
Parameters:
- ip pattern upon which the flood fill is to be performed
- ipt a cell specifying the origin of the flood fill
- nbh defines which neighbourhood to scan in while flood-filling (default 8/moore)
Returns:
-
a forma.pattern consisting of the contiguous segment about cell
- maxrectangle (ip)
-
Find the maximal contiguous rectangular area within a pattern.
Parameters:
- ip the input pattern
Returns:
-
The subpattern of
ip
consisting of its largest contiguous rectangular area.
Lists of sub-patterns
- segments (ip, nbh)
-
Generate a table of contiguous 'segments' or sub-patterns.
This performs a series of flood-fill operations until all
pattern cells are accounted for in the sub-patterns
Parameters:
- ip pattern for which the segments are to be extracted
- nbh defines which neighbourhood to scan in while flood-filling (default 8/moore)
Returns:
-
A table of forma.patterns consisting of contiguous sub-patterns of ip.
- enclosed (ip, nbh)
-
Returns a table of 'enclosed' segments of a pattern.
Enclosed areas are the inactive areas of a pattern which are
completely surrounded by active areas
Parameters:
- ip pattern for which the enclosed areas should be computed
- nbh defines which directions to scan in while flood-filling (default 4/vn)
Returns:
-
A table of forma.patterns comprising the enclosed areas of ip.
- bsp (ip, th_volume)
-
Generate subpatterns by binary space partition.
This works by finding all the contiguous rectangular volumes in the input
pattern and running a binary space partition on all of them. The partitions
are then returned in a table.
The BSP is controlled by the
threshold volume
parameter. The algorithm will recursively subdivide every rectangular area evenly in two until the volume of the largest remaining area is less thanth_volume
.Parameters:
- ip the pattern for which the BSP will be run over
- th_volume the highest acceptable volume for each final partition
- neighbourhood_categories (ip, nbh)
-
Determine subpatterns for all neighbourhood categories.
Each neighbourhood has a number of possible combinations or
categories
of active cells. This function categorises each cell in an input pattern into one of the neighbourhood's categories.Parameters:
- ip the pattern in which cells are to be categorised
- nbh the forma.neighbourhood used for the categorisation
Returns:
-
A table of #nbh patterns, where each cell in ip is categorised.
- voronoi (seeds, domain, measure)
-
Generate Voronoi tesselations of cells in a domain.
Parameters:
- seeds the set of seed cells for the tesselation
- domain the domain of the tesselation
- measure the measure used to judge distance between cells
Returns:
-
A table of Voronoi segments.
- voronoi_relax (seeds, domain, measure, max_ite)
-
Generate (approx) centroidal Voronoi tessellation.
Given a set of prior seeds and a domain, this iterates the position of the
seeds until they are approximately located at the centre of their Voronoi
segments. Lloyd's algorithm is used.
Parameters:
- seeds the original seed points to be relaxed
- domain the domain to be tesselated
- measure the distance measure to be used between cells
- max_ite (optional) maximum number of iterations of relaxation (default 30)
Returns:
- A table of resuling Voronoi segments.
- A pattern consisting of the voronoi segment centres.
- A bool, true if the algorithm converged, false if not.
- convex_hull_points (ip)
-
Compute the points lying on the convex hull of a pattern.
This computes the points lying on a pattern's convex hull with Andrew's
monotone chain convex hull algorithm. Adapted from sixFinger's
implementation at
https://gist.github.com/sixFingers/ee5c1dce72206edc5a42b3246a52ce2e
Parameters:
- ip input pattern for generating the convex hull
Returns:
-
A pattern consisting of the points of
ip
lying on the convex hull. - A clockwise-ordered table of cells on the convex hull
- convex_hull (ip)
-
Compute the convex hull of a pattern.
This computes the points on a pattern's convex hull with
subpattern.convexhullpoints and connects the points with line rasters.
Parameters:
- ip input pattern for generating the convex hull
Returns:
-
A pattern consisting of the convex hull of
ip
Utilities
- print_patterns (domain, segments, chars)
-
Print a table of forma.patterns.
Prints a table of pattern segments to io.output. If provided, a table of
segment labels can be used, with one entry per segment.
Parameters:
- domain the basic pattern from which the segments were generated.
- segments the table of segments to be drawn.
- chars the characters to be printed for each segment (optional).