# A Voting-Based Star Identification Algorithm Using a Partitioned Star Catalog
## 2 Star Catalog Partitioning
### A Method for Uniform Partitioning of the Star Catalog  
Generally, in a star catalog, the right ascension is in the range of \(0\sim 360^{\lx@math@degree}\), and the declination is in the range of \(-90\sim+90^{\lx@math@degree}\). During the work of the star sensor, its field of view limits it to capturing only a portion of the sky, meaning only a subset of stars in the star catalog is included in the field of view of the star sensor. However, the majority of algorithms require repeated retrieval of stars from the entire star catalog during the star identification process. This frequent retrieval increases the time taken for feature matching, which easily leads to redundant and false matching and significantly affects the identification speed and rate. Therefore, we propose a method for uniform partitioning of the star catalog which approximates the entire celestial region as a celestial sphere, evenly divides the celestial sphere into several regions, and maps them to the stars in the star catalog. As illustrated in Figure 2, \(o_{c}-x_{c}y_{c}z_{c}\) depicts a celestial coordinate system, and connections between the center of the celestial sphere \(o_{c}\) and the vertices of an arbitrary face in a regular icosahedron form a pyramid. The pyramid intersects with the celestial sphere, uniformly dividing it into 20 regions, each of which is numbered \(S_{1}\sim S_{20}\). Each of these 20 regions is uniformly further subdivided into \(\left(N+1\right)^{2}\) zones, resulting in a total of \(20(N+1)^{2}\) zones across the entire celestial sphere. The theoretical range for \(N\) is \(N\in\left[0,+\infty\right)\), but the appropriate value should be chosen based on the field of view of the star sensor in practical applications. Once parameter \(N\) is determined, the stars in the star catalog are mapped to the corresponding celestial sphere zones to complete the star catalog partitioning. Taking the regular triangle \(\Delta AEF\) in Figure 2 as an example, let the spatial coordinates of vertex \(A\) be \(P_{0}\), vertex \(E\) be \(P_{1}\), and vertex \(F\) be \(P_{2}\). Then, the spatial coordinate of any point within the triangle \(\Delta AEF\) can be expressed as follows:  
\[P_{\Delta AEF}=(1-u-v)P_{0}+uP_{1}+vP_{2} \tag{2}\]  
where \(u\) and \(v\) are the weight values. Defining the spatial coordinate of a star \(X\) on the celestial sphere as \(D\), the ray equation from the center of the celestial sphere \(o_{c}\) to the star \(X\) can be represented as follows:  
\[l_{o_{c}D}=o_{c}+Dt \tag{3}\]  
where \(t\) is a weight value. Figure 2: Uniform partitioning of celestial sphere. The points A, B and C are the vertices of the regular icosahedron described by dotted lines. If the star \(X\) belongs to the celestial sphere zone corresponding to triangle \(\Delta AEF\), then the ray \(I_{O_{c}D}\) intersects with triangle \(\Delta AEF\), meaning that there is a common solution between Formulas (2) and (3), which implies the existence of a set of weight values \(t\), \(u\), \(v\) that satisfy the following:  
\[O_{c}+Dt=(1-u-v)P_{0}+uP_{1}+vP_{2} \tag{4}\]  
Letting \(E_{1}=P_{1}-P_{0}\), \(E_{2}=P_{2}-P_{0}\) and \(T=O_{c}-P_{0}\), Formula (4) is updated to the following:  
\[[-D\;E_{1}\;E_{2}] \begin{bmatrix}t\\ u\\ v\end{bmatrix} =T \tag{5}\]  
Solving Equation (5) results in the following:  
\[ \begin{bmatrix}t\\ u\\ v\end{bmatrix} =\frac{1}{|-D\;E_{1}\;E_{2}|} \begin{bmatrix}T&E_{1}&E_{2}\\ -D&T&E_{2}\\ -D&E_{1}&T\end{bmatrix}  \tag{6}\]  
If the solution of Equation (6) satisfies \(t,u,v>0\) and \(u+v<1\), the star X belongs to the celestial sphere zone corresponding to triangle \(\Delta AEF\); conversely, the star X does not belong to the zone. Figure 3 visually demonstrates the scenario in which the star belongs to the celestial sphere zone. The ray from the center of the celestial sphere to the star intersects with the equilateral triangle in the regular icosahedron corresponding to the celestial sphere zone. Following the described method, the star catalog can be partitioned.