---
title: "LordOfRings"
url: "https://edoardogabrielli.com/it/progetti/lordofrings"
lang: "it"
updated: "2026-11-02"
---

# LordOfRings

> LordOfRings: un metodo per trovare gli anelli in una matrice sparsa, con una versione su GPU. Progetto di gruppo.

Un modulo Python che trova gli anelli in una matrice sparsa e ne calcola raggio e centro, anche con la GPU. Progetto universitario fatto in gruppo.

**Stack:** Python, CUDA (pycuda), NumPy, Matplotlib.

## Il problema

In una matrice quasi vuota, dove il valore 1 disegna degli anelli, bisogna ricavare raggio e centro di ciascun anello e capire a quale appartiene ogni punto. Con molti punti farlo in modo ingenuo è lento.

![Anelli individuati in una matrice sparsa](https://edoardogabrielli.com/media/originals/2026/10/ff2193bc58004ab68e8c9ec148e58478/lordofrings.png)

## Come funziona

### 1. Adattamento del cerchio

Un algoritmo di Taubin semi-parallelo stima raggio e centro di ogni anello.

### 2. Separare gli anelli

Il teorema di Tolomeo sui quadrilateri inscritti in una circonferenza serve a distinguere i punti di anelli diversi.

### 3. GPU e versione di riferimento

Il calcolo usa CUDA tramite pycuda; senza GPU c'è un'implementazione sequenziale in Python e NumPy.

### Cosa ho fatto io

Il repository è sul profilo di Sara-a-r e il lavoro è condiviso: degli 83 contributi, 47 sono miei e 36 di Sara. Non ricordo di preciso la divisione dei compiti, quindi non la descrivo.

### Stato

Da agosto 2021 a gennaio 2022. Documentazione con tutorial su Read the Docs, test su Travis CI.

[Codice su GitHub](https://github.com/Sara-a-r/LordOfRings) · [Documentazione](https://lordofrings.readthedocs.io/en/latest/)

[← Tutti i progetti](https://edoardogabrielli.com/it/progetti)