# Multistep Evolution Method to Generate Topological Interlocking Assemblies
## 3 Polygon Evolution
### Evolution Step
That is, \(v^{\prime}_{i,j}\) lies at both the positive half-space defined by plane \(P_{C}\) in direction \(\hat{N}\) and the negative half-space defined by plane \(P_{D}\) in the opposite direction to \(\hat{N}\) or \(P_{D}\) itself. Otherwise, \(v^{\prime}_{i,j}\) is out of the evolution range. In such case, we consider the intersection points \(v^{\prime}_{i,D}=L_{i}\cap P_{D}\) and \(v^{\prime}_{j,D}=L_{j}\cap P_{D}\), which are within evolution range. The bottom-right subfigure in Figure 4 shows an evolved \(n\)-polytope \(f^{\prime}\) defined by the intersection points between lines \(L_{i}\) and the plane \(P_{D}\). Let \(V^{\prime}\) be the set of intersection points within the evolution range; then, \(V^{\prime}\) defines the endpoints of the evolved \(n\)-polytope \(f^{\prime}\). Let \(E^{\prime}\) be the set of edges of \(f^{\prime}\). Each tuple, \(e^{\prime}\in E^{\prime}\), is defined by the indices of consecutive vertices in \(V^{\prime}\) as they are calculated. The last tuple in \(E^{\prime}\) must connect the last and the first vertices in \(V^{\prime}\). We call \(f^{\prime}=\textsc{Evolve}(f,\Theta,\lambda)\) the described procedure that evolves \(f=\{V,E\}\) into \(f^{\prime}=\{V^{\prime},E^{\prime}\}\). We refer to \(f\) as the seed polygon when used as a parameter in an evolution step. Algorithm 1 shows the pseudocode for the Evolve procedure. The algorithm requires three traversals through the \(n\) edges of the seed polygon: The first loop defines the planes incident to each edge. The second loop calculates the line segments, incident to each vertex, representing the intersection of the respective incident edges. The third loop calculates the vertices of the evolved polygon, \(f^{\prime}\), by checking the intersection between the respective line segments per edge and its location regarding the polygon plane and the evolution plane. Each loop structure has \(n\) iterations, resulting in \(\textsc{Evolve}\in O(n)\). The cardinality of \(V^{\prime}\) determines the type of \(n\)-polytope of \(f^{\prime}\). Polytope \(f^{\prime}\) is a single point if \(|V^{\prime}|=1\), a line segment if \(|V^{\prime}|=2\), or a polygon with \(n^{\prime}=|V^{\prime}|\) sides if \(|V^{\prime}|\geq 3\). When \(|V^{\prime}|>3\), we need to check whether all points in \(V^{\prime}\) are coplanar. If at least one point \(v^{\prime}_{i}\in V^{\prime}\) is not coplanar, then \(f^{\prime}\) is a degenerated evolution of \(f\) (i.e., the sequence of edges \(E^{\prime}=\{(0,1),(1,2),\ldots,(n^{\prime}-2,n^{\prime}-1),(n^{\prime}-1,0)\}\) does not describe a planar polygon). In such a case, adjusting either \(f\), \(\Theta\), or \(\lambda\) such that the resultant \(n\)-polytope \(f^{\prime}=\{V^{\prime},E^{\prime}\}\) describes either a point, a line segment, or a planar polygon solves the issue. Figure 5, shows examples of evolved \(n\)-polytopes from regular seed polygons. An evolution step generates the geometry of a prismatoid whose vertices are \(\{V\cup V^{\prime}\}\). Such a set of vertices, along with the set of tilting angles \(\Theta\), describes the type of the generated prismatoid. Table 1 shows the requirements for vertices and angles to describe a specific polyhedron from the prismatoids family. \begin{table}
\begin{tabular}{c c c} \hline
**Family** & **Vertices** & **Angles** \\ \hline Pyramids & \(|V|\geq 3,|V^{\prime}|=1\) & \(\theta>0,\ \forall\theta\in\Theta\) \\ Wedges & \(|V|\geq 3,|V^{\prime}|=2\) & \(\theta>0,\ \forall\theta\in\Theta\) \\ Parallelepipeds & \(|V|=|V^{\prime}|=4\) & \(\theta_{0}=\theta_{2}=0,\ \theta_{1}=\theta_{3}\) \\ Prisms & \(|V|=|V^{\prime}|\geq 3\) & \(\theta=0,\ \forall\theta\in\Theta\) \\ Cupolae & \(|V|>|V^{\prime}|\geq 3\) & \(\theta>0,\ \forall\theta\in\Theta\) \\ Frusta & \(|V|=|V^{\prime}|\geq 3\) & \(\theta>0,\ \forall\theta\in\Theta\) \\ \hline \end{tabular}
\end{table} 
Table 1: Prismatoid families based on the original vertices, \(V\), evolved vertices, \(V^{\prime}\), and tilting angle parameters, \(\Theta\), using a single evolution step.