Gist for generating Loday's integer-coordinate realisation of the the Stasheff polytope (associahedron) https://arxiv.org/abs/math/0212126

associahedron.py

"""
Script to generate the (integer) vertices of Loday's realisation
of the n-associahedron in (n-1)-dimensional associahedron 
as calculated using planar binary trees in:
https://arxiv.org/abs/math/0212126
(Realisation of the Stasheff Polytope)

Loday construction is as follows:
- each planar binary tree has a canonical "left to right" labelling of its internal nodes
- given a planar binary tree so labelled, Loday prescribes a rule for generating a vector (of integers)
- the set of all these integer vectors over all planar binary trees with n leaves is the set of vertices of the n-associahedron.

The BinTree class encapsulates binary trees as needed for the calculation.
We write custom functions for labelling the trees as described in Loday's paper outside the tree class.
A separate function generates all planar binary trees with a given number of leaves.
The main function is associahedron_vertices.
"""

## CUSTOM TREE CLASS

class BinTree(object):
    
    def __init__(self, label=None):
        # initialize a tree with one node, possibly labelled
        self.left = None
        self.right = None
        self.label = label

        # track number of leaves
        self.num_leaves = 1       # in a more general class we could have to be careful 
        self.num_left_leaves = 0  # about managing these. Since we're only creating new 
        self.num_right_leaves = 0 # trees by initialising and "adding" them, we're safe.

    def set_label(self, label):
        self.label = label

    def set_left(self, other):
        """
        Set left child of self to be some other tree, update leaf counts
        """
        self.left = other
        # update leaf count
        self.num_left_leaves = other.num_leaves
        self.num_leaves = self.num_left_leaves + self.num_right_leaves

    def set_right(self, other):
        """
        Set right child of self to be some other tree, update leaf counts
        """
        self.right = other
        # update leaf count
        self.num_right_leaves = other.num_leaves
        self.num_leaves = self.num_left_leaves + self.num_right_leaves

    def __add__(self, other):
        """
        Sum of two trees is tree formed by grafting 
        left and right trees onto a new root node

        rtype: BinTree
        """
        new = BinTree()
        new.set_left(self)
        new.set_right(other)
        return new
    
    def isleaf(self):
        """
        Check whether self is a leaf (has no children).

        rtype: bool
        """
        return not bool(self.left or self.right)

    def get_nodes(self):
        """
        Return a list of all the nodes (Tree objects) in a tree.

        rtype: [BinTree]
        """
        if self.isleaf():
            return [self]
        
        else:
            return [self] + self.left.get_nodes() + self.right.get_nodes()
    
    def get_leaves(self):
        """
        Return a list of all the leaves (Tree objects with no children) in a tree.

        rtype: [BinTree]
        """
        return [node for node in self.get_nodes() if node.isleaf()]
    
    def get_internal_nodes(self):
        """
        Return a list of all the non-leaves (Tree objects with children) in a tree.

        rtype: [BinTree]
        """
        return [node for node in self.get_nodes() if not node.isleaf()]
             

## TREE FUNCTIONS
    
def label_leaves(tree, fst_label=0):
    """
    Label leaves in the tree from left to right, starting with value fst_label and incrementing by one. Returns the final label + 1.
    When called on the root with fst_label = 0 it labels the leaves 0,1,2,... from left to right and returns the number of leaves.
    """
    
    if tree.isleaf():
        tree.label = fst_label
        return fst_label + 1
    
    else:
        num_left_leaves = label_leaves(tree.left, fst_label=fst_label)
        num_leaves = label_leaves(tree.right, fst_label=num_left_leaves)
        return num_leaves

def leftmost_leaf(tree):
        """
        Helper function.
        Return the "leftmost" leaf of a tree.

        rtype: BinTree
        """
        if tree.isleaf():
            return tree
        else:
            return leftmost_leaf(tree.left)

def loday_label(tree, fst_leaf_label=0):
    """
    Label the nodes of a binary tree as follows:
    * label leaves 0, 1, 2, ... from left to right
    * the (unique) internal node falling between leaf i-1 and leaf i is given label i
    * equivalently, the label of an internal node is the label of the leftmost leaf of the node's right branch.
    """

    # first label the leaves
    label_leaves(tree)
    
    # then label internal nodes
    internal_nodes = tree.get_internal_nodes()
    for node in internal_nodes:
        node.label = leftmost_leaf(node.right).label
    return 


def associahedron_coord(tree):
    """
    Given a binary tree (with n leaves), find the associated integer point
    in (n-1)-d space as described in Loday's paper.

    tree: BinTree
    rtype: [int]
    """

    # label tree
    loday_label(tree)
    
    # put internal leaves in order
    internal_nodes_ordered = [None]*(tree.num_leaves - 1) # 1 fewer internal nodes than leaves in binary tree
    for node in tree.get_internal_nodes():
        i = node.label
        internal_nodes_ordered[i-1] = node
        
    # return (a_i*b_i), i = 1, .., n , where
    # a_i | b_i = leaves on left|right branch of internal node i
    return [
        node.num_left_leaves*node.num_right_leaves 
        for node in internal_nodes_ordered
    ]

def all_trees(nleaves):
    """
    Return a list of all Binary Trees with nleaves leaves.
    (Length of the list should be the (nleaves-1)st Catalan number.)
    
    nleaves: int
    rtype: [BinTree]
    """
    
    if nleaves < 1:
        return []

    elif nleaves == 1:
        return [BinTree()]
    
    else:
        trees = []
        for i in range(1, nleaves):
            trees += [ltree + rtree 
                      for ltree in all_trees(i) 
                      for rtree in all_trees(nleaves-i)
                     ]
        return trees


## MAIN FUNCTION

def associahedron_vertices(degree):
    """
    Get vertices of associahedron of degree degree
    Vertices are integer-coordinate vectors in dimension degree-1
    all lying in a hyperplane of dimension degree-2.

    degree: int
    rtype: [[int]], inner lists of length degree-1.
    """
    trees = all_trees(degree)
    coords = [
        associahedron_coord(tree)
        for tree in trees
    ]
    return coords 

create5AssociahedronSTL.py

import numpy as np
from trimesh import Trimesh
from associahedron import associahedron_vertices


def main(filename="repr/loday-5-associahedron.stl"):

    # vertices of 5 associahedron in (3D subspace of) R^4
    verticesR4 = associahedron_vertices(5)

    # helper function to convert vertex coordinates to 3D
    def toR3(vec):
        """
        Send vector in R^4 to its image under an isometry of R^4 that sends 
        H = {vec|∑vec_i = 10} (hyperplace containing 5-associahedron) to {vec|vec_0 = 0}.
        
        vec: np.array (in R^4,)
        rtype: np.array (in)
        
        """
        # check input is acceptable
        if vec.shape != (4,):
            raise ValueError("Input should be in R^4")
        if sum(vec) != 10:
            raise ValueError("Input should be in hyperplane {vec|∑vec_i = 10}")
        
        # perform euclidean motion to hyperplane vec_0 = 0
        t = np.array([5/2, 5/2, 5/2, 5/2]) # vector from origin to H, normal to H
        M = np.array(
            [
                [1/2, 1/2, 1/2, 1/2],
                [1/2, 1/2, -1/2, -1/2],
                [1/np.sqrt(2), -1/np.sqrt(2), 0, 0],
                [0, 0, 1/np.sqrt(2), -1/np.sqrt(2)]
            ]
        ) # orthogonal matrix sending normal to H to x_0 axis
        vec = M @ (vec - t) # do motion

        return vec[1:] # drop zero 1st coord

    # transform associahedron vertices to R3
    verticesR3 = [
        toR3(np.array(coord)) 
        for coord in verticesR4
        ] 

    # create mesh and fill in faces using convex hull
    ass_mesh = Trimesh(vertices=verticesR3).convex_hull

    # export
    ass_mesh.export(filename, file_type='stl')
    return


## MAIN

if __name__ == "__main__":
    main()