tilezz

This repository provides the following main features:

1. practical implementation of various cyclotomic rings, which are subsets of complex numbers that admit exact representation
2. exact representation of a rich family of polygonal tiles based on these rings, using a minimalistic and discrete form of turtle semantics
3. some useful string-based algorithms to work with these objects and visualize them

These features taken together grant us multiple freedoms:

1. freedom of floating-point numbers and subtle bugs due to numerical issues
2. freedom of coordinates, as polygons are described by relative angles and movements to trace out their boundary
3. freedom of a (typical) grid, when using the polygons in the context of tiles and tilings

The target audience are primarily math enthusiasts (like myself) or researchers working on (a)periodic tiles or other areas where exact representation of polygons is crucial and where numerical approximation and the use of floating point arithmetic are not acceptable for the given purpose, yet the use of more generic solutions, such as computer algebra systems is not desirable, too inconvenient or too inefficient.

The concepts this work is based on are described in the following blog posts:

• https://pirogov.de/blog/perfect-precision-2d-geometry-complex-integers/
• https://pirogov.de/blog/intersecting-segments-without-tears/
• TODO: write followup post

Note that due to time constraints, this is a work-(not-so-fast-)in-progress.

Usage

Essential Concepts

This crate provides the abstract geometric API for using concrete representations of constructible cyclotomic rings for some fixed root of unity, and polygonal tiles build on top of these rings.

Instead of representing polygons by segments and coordinates, they are described using a form of turtle semantics, i.e. interpreting a sequence of exterior angles as instructions for tracing out a polygon or segment chain from a given starting point by performing unit-length steps in some direction. This, together with the fact that we use cyclotomics for actual coordinates, helps avoiding dependence on floating point numbers and explicit coordinates.

Here is a conceptual mapping for the relevant geometrical objects:

• a point corresponds to a turtle, which is an "oriented point" (it has an angle, defining its facing direction)
• a polygonal chain corresponds to a snake, which consists of instructions for a turtle
• a polygon corresponds to a closed snake, which I call a rat (for rational tile)
• a tile patch corresponds to a pack, which is a collection of combined rats

A tile is a simple polygon, i.e. a polygon without holes or self-intersections, and a segment chain, polygon, or tile is rational if all the side lengths can be expressed as integer multiples of a common length.

By using cyclotomic integers for coordinates and expressing all geometric objects in terms of unit steps into some direction, each simple polygon allows for a natural representation as a sequence of exterior angles along its boundary. As the sequence is cyclic, there is one cyclicaly shifted sequence for each starting vertex. The canonical representation is then simply the lexicographically minimal such sequence. Note that this gives us a simple and efficient equivalence check on polygons: two polygons are equal iff they have the same canonical angle sequence. Treating (rational) polygons as strings of angles also allows us to use other efficient string-based algorithms, e.g. to compute combinations of tiles.

This library also provides some plotting functionality based on plotterrs, which means that you can easily render tiles built with this crate into various backends, including PNG, SVG, web pages (HTML5/WASM), including interactive usage in Jupyter.

Interactive (Jupyter Notebook)

Thanks to the capabilities of the plotters library, it is easy to use Jupyter notebooks with this crate to visualize polygonal tiles.

Requirements

• Jupyter Notebook (Arch Linux users see here)
• evcxr
• evcxr_jupyter

If you have all the dependencies installed correctly and can create/open Jupyter Notebooks using a Rust kernel (check out the official evcxr documentation), then you are already set up for using this crate interactively.

Rendering the Spectre Tile Over the Cyclotomic Integer Ring ZZ12

Here is how you can quickly construct and render the spectre tile:

Step 1: (Recommended) This step is only needed if you want to use the most recent development version from this repository.

Clone this repository and change to its directory, i.e. in a terminal run:

git clone https://github.com/apirogov/tilezz
cd tilezz

Step 2: Run jupyter notebook

Step 3: Open the example notebook OR Create a new Rust notebook (which is powered by evcxr) and add the following code into a cell:

:dep plotters = { version = "^0.3.7", features = ["evcxr", "all_series"] }
// 1(a) if you want to use a published version of this crate:
// :dep tilezz = "*"
// 1(b) (RECOMMENDED) if you cloned this repository and want to use the current development version:
:dep tilezz = { path = "." }

use plotters::prelude::*;
use tilezz::snake::constants::spectre;
use tilezz::snake::{Snake, Turtle};
use tilezz::plotters::plot_tile;
use tilezz::zz::ZZ12;

evcxr_figure((500,500), |root| {
    let s: Snake<ZZ12> = spectre();
    let tile = s.to_polyline_f64(&Turtle::default());

    let _ = root.fill(&WHITE);
    let root = root.margin(10, 10, 10, 10);

    plot_tile(
        &mut ChartBuilder::on(&root)
            .caption("Spectre tile", ("sans-serif", 40).into_font())
            .x_label_area_size(20)
            .y_label_area_size(40),
        &tile,
    );
    root.present()?;
    Ok(())
})

After waiting for some seconds (the required dependencies have to be built first, after that it is faster), you should see a plot showing the spectre tile.

TODO: improve/finalize API, update the example and add a screenshot.

See Also

Tiles and Tilings

It seems that people who work on/with tiles use software like:

• computer algebra systems, such as SageMath
• SAT or SMT solvers, such as Z3
• PolyForm Puzzle Solver

SageMath or similar systems are of course much more heavy and require deeper algebraic understanding to even ask what you want. This crate provides much simpler (and I hope more efficient) solutions to much more specific problems.

Similarly, SAT or SMT solvers are excellent tools for certain NP-complete problems (I have some experience using them), but encoding tiling problems into suitable formulas is far from trivial and requires some thought and work (even though it sometimes is possible). It can really pay off and work well if you have enough knowledge about SAT/SMT encoding tricks and also have a deeper grasp on the structure of the problem at hand. But it is not something I'd pull out to just quickly come up with a polygon and check its behavior as a tile.

The PolyForm Solver seems to have some adoption by the tiling community and looks like a mature and feature-rich package that I eventually want to try out myself. From a cursory look, it seems like the biggest conceptual difference is that the PolyForm Solver is grid-based - it requires selecting some underlying grid of primitive cells from which the polyform tiles can be built from. My approach is grid-free, so it is more general. Technically, the cyclotomic integers do provide another kind of grid, but it is not a typical periodic cell grid as typically used to describe tiles and tilings. This means that more exotic and irregular tiles can be expressed, but also that there is less fixed structure to work with and exploit, and I don't provide any sophisticated solvers (yet).

Cyclotomic Integer Rings (i.e. Complex Integers)

I have no clue about abstract algebra and number theory (I just stumbled into this topic trying to represent some tiles exactly), but it seems like there are a few very general implementations of cyclotomic fields.

• https://github.com/CyclotomicFields/cyclotomic (Rust)
• https://github.com/walck/cyclotomic (Haskell)

Compared to these packages, I do not try to implement the full set of cyclotomic integers (i.e. one type that includes and works with all roots of unity at once). This crate provides a separate ring/field for each supported root of unity instead, which then serves as the backbone for representing geometry of suitable polygons.

The corresponding underlying representations are optimized for and limited to the respective ring, there is no overhead due to management of symbolic representations or anything like that, because for each ring, the provided data type encodes the values of each ring as vectors over a linearly independent set base of units (and all their distinct symbolic products), together with a ring-specific implementation of multiplication, which hard-codes the symbolic simplifications of expressions that appear during the evaluation of multiplication.

I have have not tried to compare this crate to the other approaches or benchmark anything yet, because the implementations of the complex integers were not the intended main feature of this crate. If someone is mainly interested in this crate for the implementation of the cyclotomic integer rings, I would be happy to get some feedback on how this compares to the more generic implementations with similar features.