LordOfRings
A Python module that finds rings in a sparse matrix and computes their radius and centre, optionally on the GPU. A university group project.
Stack: Python, CUDA (pycuda), NumPy, Matplotlib.
The problem
In an almost empty matrix, where the value 1 draws rings, you need the radius and centre of each ring and which ring each point belongs to. With many points, doing it naively is slow.
How it works
- 01
Circle fitting
A semi-parallel Taubin algorithm estimates the radius and centre of each ring.
- 02
Separating the rings
Ptolemy's theorem on quadrilaterals inscribed in a circle is used to tell points of different rings apart.
- 03
GPU and reference version
The computation uses CUDA through pycuda; without a GPU there is a sequential Python/NumPy implementation.
What I did
The repository is on Sara-a-r's profile and the work is shared: of 83 contributions, 47 are mine and 36 are Sara's. I do not remember exactly how the tasks were split, so I do not describe it.
Status
From August 2021 to January 2022. Documentation with tutorials on Read the Docs, tests on Travis CI.