## 4 Location Algorithm Based on Ranging
### Trilateral Centroid Positioning Algorithm  
The positioning method of the UWB positioning system can use the trilateral centroid positioning algorithm (TCPA). Figure 9 shows the schematic diagram of the original trilateral centroid positioning algorithm.  
In the two-dimensional plane coordinate system, it is known that the coordinates of the three anchors are \(A(x_{1},y_{1}),A(x_{2},y_{2}),A(x_{3},y_{3})\), and the coordinates of the tag are \(T(x,y)\). The distances between the tag and the three anchors are \(r_{1},r_{2}\) and \(r_{3}\), respectively. Taking the three anchor coordinates as the center and the corresponding \(r\) as the radius, three circles can be formed. They have the following relationship:  
\[\begin{cases}(x-x_{1})^{2}+(y-y_{1})^{2}=r_{1}^{2}\\ (x-x_{2})^{2}+(y-y_{2})^{2}=r_{2}^{2}\\ (x-x_{3})^{2}+(y-y_{3})^{2}=r_{3}^{2}\end{cases} \tag{17}\]  
Ideally, as shown in the Figure 9a, three circles intersect at a point. However, when there are errors in \(r_{1},r_{2}\), and \(r_{3}\) as shown in the Figure 9b, they will not intersect at one point. Tag is in the blue area, where the optimal position needs to be found.  
Figure 9: Schematic diagram of the trilateral centroid positioning algorithm. The black point represents the position of the anchor. (**a**) Ideal case: Three circles intersect at a point. (**b**) Non-ideal case: Three circles do not intersect at a point. The blue area indicates an error in the distance measurement.  
The principle of TCPA is to use the centroid of a triangle determined by pairs of circles as the location result. There are five types of relations between two circles: intersection, inner tangent, outer tangent, inner separation, and the outer separation. Figure 10 shows the schematic diagram of the two positioning processes including these five relations.  
When two circles are tangent, the tangent point(\(P_{t}\) in the Figure 10a,b) is directly used as the vertex determined by the two circles.  
When two circles are separated, the vertex determined by the two circles is the midpoint at which they are closest to each other, just as point \(P_{s}\) in Figure 10a,b.  
When the two circles intersect, the vertex determined by the two circles is the intersection point at which the sum of the sides of the triangle with the other vertices determined or to be determined is the smallest, just as the point \(P_{i1}\) in Figure 10a and the point \(P_{i2}\) in Figure 10b.  
After determining the vertex of the triangle, we calculate the centroid of the triangle, which is the positioning result of TCPA. When we calculate the centroid coordinates of a triangle determined by the TCPA, it may fall outside the boundary of the map if we display it directly. So it needs to be corrected when it falls outside the boundaries of the map. Figure 11 shows a schematic diagram of the corrected positioning results.  
Figure 11: Map boundary restriction. Map restriction scheme for the positioning results that need to be corrected. \(P_{k-1}\) is the final positioning result at \(k-1\), \(P_{k}\) is the centroid coordinates of the triangle determined by the trilateral centroid positioning algorithm at \(k\), and \(\tilde{p}_{k}\) is the corrected positioning result.  
Figure 10: The special case in the TCPA where the three circles do not intersect at a point. The triangle formed by the red line segment is the triangle selected by the trilateral centroid positioning algorithm, and the red five-pointed star is the centroid of the triangle, which is also the positioning result. (**a**) Circle A1 and circle A3 are outer separated. (**b**) Circle A1 and circle A3 are inner separated.  
We oass point \(P_{k}\) to take a normal line of the map boundary and extend it. The corrected positioning result should fall on the normal line; pass point \(P_{k-1}\) to take a parallel line (or curve) of the map boundary, then it will intersect the normal at point \(\widehat{p}_{k}\). Point \(\widehat{p}_{k}\) must fall within the map boundaries, therefore taking it as the corrected result.