Improved Dunham

We provide a performance optimized implementation of the tiling algorithm by Douglas Dunham. It achieves a factor 10-20x speed up compared to the literal, unoptimized implementation, which is available as the legacy Dunham kernel.

Sources:

  • [Dun86] Dunham, Douglas. “Hyperbolic symmetry.” Symmetry. Pergamon, 1986. 139-153.

  • [Dun07] Dunham, Douglas. “An algorithm to generate repeating hyperbolic patterns.” the Proceedings of ISAMA (2007): 111-118.

  • [Dun09] Dunham, Douglas. “Repeating Hyperbolic Pattern Algorithms — Special Cases.” unpublished (2009)

  • [JvR12] von Raumer, Jakob. “Visualisierung hyperbolischer Kachelungen”, Bachelor thesis (2012), unpublished

The improved Dunham kernel is implemented as:

class hypertiling.kernel.DUN07X.DunhamX(p: int, q: int, n: int)

Performance optimized implementation of the tiling algorithm by Douglas Dunham, published in [Dun07] It achieves a factor 10-15x speed up compared to the literal, unoptimized implementation, which is available as kernel “Dunham” in DUN07.py

Note that this kernel internally uses Weierstrass (hyperboloid) arithmetic.

Kernel Details

The following function defines a method to calculate the fundamental polygon. It creates an array of complex numbers representing vertices in Weierstrass coordinates, and then converts them to a 3D array. The method returns the 3D array representing the fundamental polygon.

hypertiling.kernel.DUN07X.DunhamX._create_fundamental_polygon(self) → array

Calculates the fundamental polygon.

Returns:

A 3D array of shape [p + 1, 3]. The array represents [center, vertex1, …] in Weierstrass coordinates.

Return type:

np.array

This is the driver routine for the Dunham tiling algorithm. It iterates over each vertex of the polygon and, for each vertex, iterates over a certain number of polygons. For each polygon, it determines the exposure level, replicates the motif, and modifies the transformation. It is not part of the class but a separate helper function. Since this kernel is improved with performance in mind, a larger number of function arguments could not be avoided.

hypertiling.kernel.DUN07X.generate_dun(p: int, q: int, n: int, polygons: array, polygon_counter: int, transs: array, transs_props: array, trans_init: array, trans_init_orient: int, trans_init_pos: int, layer: int, exposure: int, min_exp: int, max_exp: int) → int

Calculates the tiling and stores the polygons in polygons. Returns the number of constructed polygons

Parameters:

  • p (int) – Number of edges

  • q (int) – Number of polygons at a vertex

  • n (int) – Number of layers to construct

  • polygons (np.array) – Shape [m, p + 1]. Polygons in the tiling in format [[center, vertex1, …], …]

  • polygon_counter (int) – Counter of how many polygons are already constructed

  • transs (np.array) – Shape [p, 3, 3]. Each subarray represents a transformation for edge trans

  • transs_props (np.array) – Shape [p, 2]. Each subarray represents [orient, pos] for edge trans

  • trans_init (np.array) – Shape [3, 3]. Transformation (current)

  • trans_init_orient (int) – Orientation of transformation (current) in {-1, 1}

  • trans_init_pos (int) – Position of transformation (current)

  • layer (int) – Current layer in construction

  • exposure (int) – Number of open edges

  • min_exp (int) – Minimal number of open edges

  • max_exp (int) – Maximal number of open edges

Returns:

Polygon counter after construction

Return type:

int

What is left is the function which initiates the construction:

hypertiling.kernel.DUN07X.DunhamX._generate(self)

Generate the tiling according to the Dunham algorithm

Helper functions

As for every kernel, there is a number of helpers:

hypertiling.kernel.DUN07X.DunhamX._compute_edge_reflections(self) → Tuple[array, array]

Calculate the fundamental transformations on the edges.

Returns:

A tuple containing two numpy arrays. The first array is of shape [p, 3, 3] representing transformations ([trans1, …]). The second array is of shape [p, 2] representing their properties ([[orient, pos], …]).

Return type:

tuple

hypertiling.kernel.DUN07X.comp_tran(p: int, transs_props: array, transs: array, trans: array, trans_orient: int, trans_pos: int, shift: int) → Tuple[array, int, int]

Calculate the new transformation for the edge.

Parameters:

  • p (int) – Number of edges.

  • transs_props (np.array) – Array of shape [p, 2] representing [[orient, pos], …] for edge trans.

  • transs (np.array) – Array of shape [p, 3, 3] representing [trans, …] for edge trans.

  • trans (np.array) – Current transformation of shape [3, 3].

  • trans_orient (int) – Orientation of transformation (current) in {-1, 1}.

  • trans_pos (int) – Position of transformation (current).

  • shift (int) – Fixed value -1.

Returns:

Transformation, orientation and position.

Return type:

Tuple[np.array, int, int]

hypertiling.kernel.DUN07X.add_trans(p: int, transs_props: array, transs: array, trans: array, trans_orient: int, trans_pos: int, shift: int) → Tuple[array, int, int]

Calculate the new transformation for the edge by adding a shift.

Parameters:

  • p (int) – Number of edges.

  • transs_props (np.array) – Array of shape [p, 2] representing [[orient, pos], …] for edge trans.

  • transs (np.array) – Array of shape [p, 3, 3] representing [trans, …] for edge trans.

  • trans (np.array) – Current transformation of shape [3, 3].

  • trans_orient (int) – Orientation of transformation (current) in {-1, 1}.

  • trans_pos (int) – Position of transformation (current).

  • shift (int) – Fixed value -1.

Returns:

Transformation, orientation and position.

Return type:

Tuple[np.array, int, int]

Getter

Finally, the DUN07X kernel satisfies the required getter methods:

hypertiling.kernel.DUN07X.DunhamX.get_polygon(self, index: int) → HyperPolygon

Returns the polygon at index as HyperPolygon object.

Parameters:

index (int) – Index of the polygon.

Returns:

Polygon at index.

Return type:

HyperPolygon

hypertiling.kernel.DUN07X.DunhamX.get_vertices(self, index: int) → array

Returns the p vertices of the polygon at index in Poincare disk coordinates. Since this kernel’s internal arithmetic is done in Weierstrass representation, this requires some coordinate transform.

Time-complexity: O(1) Overwrites method of base class.

Parameters:

index (int) – Index of the polygon.

Returns:

Array of shape (p,) containing vertices of the polygon.

Return type:

np.array

hypertiling.kernel.DUN07X.DunhamX.get_center(self, index: int) → complex128

Returns the center of the polygon at index in Poincare disk coordinates. Since this kernel’s internal arithmetic is done in Weierstrass representation, this requires a coordinate transform.

Time-complexity: O(1) Overwrites method of base class.

Parameters:

index (int) – Index of the polygon.

Returns:

Center of the polygon.

Return type:

np.complex128

hypertiling.kernel.DUN07X.DunhamX.get_angle(self, index: int) → float

Returns the angle to the center of the polygon at index.

Time-complexity: O(1)

Parameters:

index (int) – Index of the polygon.

Returns:

Angle of the polygon.

Return type:

float