Come illustrato qui , quello che stai cercando è il 1 ° ordine 2 -dimensional diagramma di Voronoi sotto Manhattan o L1-metric . Questo è un problema abbastanza banale (da risolvere in modo efficiente), fortunatamente con molti algoritmi e software esistenti.
In realtà vuoi che il sottoinsieme del diagramma di Voronoi coincida con la griglia discreta definita dalle coordinate della matrice, ma è semplice trovare i punti del diagramma che hanno coordinate integrali.
I "punti fissi" sono chiamati siti, semi, generatori o punti sorgente in diversi contesti. Poiché il numero di siti è ridotto, è più appropriato utilizzare un algoritmo geometria computazionale , ovvero trovare un vector rappresentazione dei segmenti di linea del diagramma, indipendentemente dalla dimensione della matrice (per 10 siti, dovrebbe essere estremamente veloce).
Una libreria altamente riconosciuta è CGAL , che include un gran numero di algoritmi di geometria computazionale in C ++ e in particolare 2D segmenti grafici Delaunay (diagrammi di Voronoi) . Il manuale utente parla solo della distanza euclidea, ma c'è anche una demo del diagramma di Voronei L1 , quindi spero che troverai la tua strada.
Un'altra prospettiva è una rappresentazione raster , usando algoritmi che spazzano l'intero piano (la tua matrice) una volta, in un ordine particolare simile alla propagazione delle onde. Questo è consigliato se il numero di siti è grande, formando forme arbitrarie sul piano. È correlato alla trasformazione a distanza , asse mediale e lo scheletro topologico . Le ultime due sono generalizzazioni del diagramma di Voronoi, in quanto consistono in curve piuttosto che in segmenti di linea in generale, indipendentemente dalla metrica.
Un'ottima soluzione in questa prospettiva è le trasformazioni di distanza delle funzioni campionate , dando anche codice sorgente . Questo è limitato al calcolo della distanza trasformata e alle metriche di distanza separabili per esempio al quadrato Euclideo o L1 (il tuo caso).
Per trovare l'asse mediale dato la trasformazione della distanza, una buona scelta è il mio rivelatore di feature mediale , con codice binario disponibile . Questo lavoro utilizza anche un metodo alternativo per il calcolo della trasformazione della distanza che non ha limiti sulla metrica della distanza. È più lento del precedente ma è ancora lineare rispetto alla dimensione del dominio (la tua matrice). Il calcolo dell'asse mediale stesso è estremamente veloce (tempo lineare sul numero di punti dell'asse mediale).
Asse mediale 2D sotto metrica euclidea http://image.ntua.gr/iva/tools /mfd/fig/biarcs_med_res.png
Ad esempio, puoi dare un'occhiata a questa immagine , dove bianco i punti sono i siti (in realtà formano una curva chiusa sul piano) e le curve rosso-giallastre sono l'asse mediano (euclideo). Nota che questi ultimi hanno una precisione sub-pixel, cioè appaiono come curve anti-alias ad 1 pixel di pixel, sebbene i siti di input no. Questo dimostra che hai le informazioni richieste (posizione esatta) per scoprire se un punto candidato sull'asse mediale ha o meno coordinate integrali. Per avere un'idea della velocità, questo risultato è stato generato in circa 300 ms.
Se ti preoccupi dell'efficienza, il mio consiglio è di cercare algoritmi o codici esistenti. Se insisti sulla tua implementazione, dovrai leggere molto prima, in modo da avere una buona comprensione del problema.
