The General AntiParticle Spectrometer (GAPS) is an Antarctic balloon-borne detector designed to measure low-energy cosmic antinuclei (< 0.25 GeV/n), with a specific focus on antideuterons, as a distinctive signal from dark matter annihilation or decay in the Galactic halo. The instrument consists of a tracker, made up of ten planes of lithium-drifted Silicon Si(Li) detectors, surrounded by a plastic scintillator Time-of-Flight system. GAPS uses a novel particle identification method based on exotic atom capture and decay with the emission of pions, protons, and atomic X-rays from a common annihilation vertex. An important ingredient for the antinuclei identification is the reconstruction of the annihilation star topology. A custom antinucleus annihilation reconstruction algorithm, called the star-finding algorithm, was developed to reconstruct the annihilation star fully, determining the annihilation vertex position and reconstructing the tracks of the primary and secondary charged particles. The reconstruction algorithm and its performances were studied on simulated data obtained with the Geant4-based GAPS simulation software, which fully reproduced the detector geometry. This custom algorithm was found to have better performance in the vertex resolution and reconstruction efficiency compared with a standard Hough-3D algorithm.