# An Approach of Path Optimization Algorithm for 3D Concrete Printing Based on Graph Theory
## 2 Materials and Methods
### Model Partition  
Convert the slicing model created in the previous section into computer-processed geometry (Figure 3) to use the partitioning algorithm in this section. The intersection of multiple line segments in the geometric figure is marked as a geometric point (Figure 4) and assigned numbers as \(S_{1},\ \ S_{2},\ \ S_{3}\ \ldots\ \ldots\ S_{n}\). Then, each geometric point is assigned a Cartesian coordinate value as \((x_{1},y_{1}),\ (x_{2},y_{2}),\ \ \ (x_{3},y_{3})\ \ldots\ \ldots\ (x_{n},y_{n})\) according to the geometric data measured in the 3D concrete printing component model. For each line segment in the geometric figure, a matrix \(T\) describes their length and the number of intersections, and the elements in the matrix as weights. In this paper, the number of elements in \(T\) represents the intersection point of the nozzle running path, and the number of line segments in the geometric figure represents the connection path between these intersection points. Therefore, there is a linear relationship between the number of line segments in the geometric figure and the number of elements in \(T\), and the length of the line segments and the size of elements in \(T\) are also linear. Create a matrix \(T_{1}\) to describe whether each geometric point in the geometric figure is connected. Among them, the elements in \(T_{1}\) of the row vector are the numbers of the marked geometric points, and the elements in \(T_{1}\) of the column vector represent their connection relationship. To obtain the elements in \(T_{1}\), it is needed to traverse the elements in \(T\) and find the geometric points that meet the following four rules:  
(1) \(y_{i}=y_{j}\) && \(x_{i}<x_{j}\) && \(T_{ij}\
eq 0\) && \(T_{ij}\
eq inf\);  
(2) \(x_{i}=x_{j}\) && \(y_{i}<y_{j}\) && \(T_{ij}\
eq 0\) && \(T_{ij}\
eq inf\);  
Figure 1: The 3D concrete component model created in Sketch Up. Figure 2: The 3D concrete component slice model in Cura. (3) \(y_{i}=y_{j}\) && \(x_{i}>x_{j}\) && \(T_{ij}\
eq 0\) && \(T_{ij}\
eq inf\); (4) \(x_{i}=x_{j}\) && \(y_{i}>y_{j}\) && \(T_{ij}\
eq 0\) && \(T_{ij}\
eq inf\);  
These rules do not need to be satisfied for all elements in \(T\). When rule (1) is satisfied, the corresponding geometric point is put into \(T_{1}\). When rule (1) and rule (2) are satisfied simultaneously, the priority of putting the geometric point is lower than the first one, and so on. \[ \begin{array}{ccccc}0&S_{1}&S_{2}&S_{3}&\cdots&S_{n}\\ S_{1}&0&1&2&\cdots&inf\\ S_{2}&1&0&3&\cdots&inf\\ T=S_{3}&2&3&0&\cdots&1\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ S_{n}&inf&inf&1&\cdots&0\\ \end{array} \]  
\[ \begin{array}{ccccc}S_{1}&S_{2}&S_{3}&S_{4}&\cdots&S_{n}\\ S_{5}&S_{7}&S_{2}&S_{1}&\cdots&S_{n-3}\\ S_{2}&S_{3}&S_{5}&S_{4}&\cdots&S_{n-6}\\ S_{3}&S_{5}&S_{1}&S_{7}&\cdots&S_{n-1}\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ S_{6}&S_{6}&S_{n-5}&S_{3}&\cdots&S_{n-4}\\ \end{array} \]  
Start the first partition search phrase as \(T_{1}\) creation is completed. At this time, matrix \(B\) is created to record the connection times of each geometric point in the geometric figure. The first-row element in \(B\) is the number of the marked geometric point; the second-row  
Figure 4: Geometric points marked in the geometric model. Figure 3: Geometric model. element in \(B\) is the number of connections between each geometric point and the rest of the geometric point; and the initial value is 0. Select a starting point \(S_{i}\) in the first row of an element in \(T_{1}\) to connect to the point \(S_{j}\) in the next row, set the element in \(T\) to inf, and add 1 to the element in \(B_{2j}\). After finding column \(S_{j}\) in \(T_{1}\), repeat the above operation to find the partition that can traverse at once. The following are the connection rules:  
1. [label=(1)]
2. Connect \(S_{i}\), \(S_{j}\), make \(T_{ij}=inf,B_{2i}=B_{2i}+1\);
3. Find \(S_{j}\), \(S_{j1}\), if \(T_{ij}\
eq inf\)&& \(B_{2j}<B_{2j1}\), connect \(S_{j}\), \(S_{j1}\);  
\[B= \begin{matrix}S_{1}&S_{2}&S_{3}&S_{4}&\cdots&S_{n}\\ 0&0&0&0&\cdots&0\\ \end{matrix}