Qual è il modo più efficace per trovare la distanza euclidea in 3d usando mysql?

Question

Ho una tabella MySQL con migliaia di punti dati memorizzati in 3 colonne R, G, B. come posso trovare quale punto dati è più vicino a un dato punto (a, b, c) usando la distanza euclidea?

Sto salvando i valori RGB dei colori separatamente in una tabella, quindi i valori sono limitati a 0-255 in ogni colonna. Quello che sto cercando di fare è trovare la corrispondenza cromatica più vicina trovando il colore con la più piccola distanza euclidea.

Potrei ovviamente percorrere tutti i punti del tavolo per calcolare la distanza ma non sarebbe abbastanza efficiente da scalare. Qualche idea?

Answer 1

1. Dal momento che si sta cercando la distanza minima e non esatta distanza è possibile ignorare la radice quadrata. Penso che lo Squared Euclidean Distance si applichi qui.
2. Hai detto che i valori sono compresi tra 0-255, quindi puoi creare una tabella di ricerca indicizzata con 255 valori.

Ecco cosa sto pensando in termini di SQL.r0, g0 e b0 rappresentano il colore di destinazione. La tabella Vector manterrebbe i valori quadrati sopra menzionati in # 2. Questa soluzione visiterebbe tutti i record ma il set di risultati può essere impostato su 1 ordinando e selezionando solo la prima riga.

select 
    c.r, c.g, c.b, 
    mR.dist + mG.dist + mB.dist as squared_dist 
from 
    colors c, 
    vector mR, 
    vector mG, 
    vector mB 
where 
    c.r-r0 = mR.point and 
    c.g-g0 = mG.point and 
    c.b-b0 = mB.point 
group by 
    c.r, c.g, c.b 

Answer 2

Credo ci siano due opzioni.

Si deve o come si dice iterare su tutto il set e confrontare e confrontare con un massimo impostato inizialmente su un numero incredibilmente basso come -1. Funziona in tempo lineare, n volte (dal momento che stai confrontando solo 1 punto con ogni punto dell'insieme, questo scala in modo lineare).

Sto ancora pensando ad un'altra opzione ... qualcosa sulla falsariga di fare una prima ricerca di ampiezza lontano dal punto di input fino a quando un punto si trova nell'insieme nel punto cercato, ma questo richiede un po 'più di riflessione (Immagino che lo spazio 3D dovrebbe essere abbastanza popolato perché questo sia in media più efficiente).

Answer 3

Il primo livello di ottimizzazione che vedo che si può fare sarebbe quadrato la distanza a cui si desidera limitare la query in modo che non sia necessario eseguire la radice quadrata per ogni riga. Il secondo livello di ottimizzazione che incoraggerei sarebbe una pre-elaborazione per alleggerire la necessità di quadratura estranea per ogni query (che potrebbe creare un po 'di tempo extra per le grandi tabelle di RGB). Dovresti fare un po 'di benchmarking per vedere, ma sostituendo i valori di a, b, c edd e poi eseguendo la query, potresti alleviare lo stress da MySQL.

nota che la differenza di prestazioni tra le ultime due righe può essere trascurabile. Dovrai utilizzare le query di prova sul tuo sistema per determinare quale sia più veloce.

Ho appena riletto e ho notato che stai ordinando per distanza. In tal caso, la d dovrebbe essere rimossa, tutto dovrebbe essere spostato su un lato. È ancora possibile collegare le costanti per evitare un'ulteriore elaborazione su MySQL.

Answer 4

Se si attraversano tutti i punti e si calcola la distanza, non utilizzare la funzione radice quadrata, non è necessario. La più piccola somma di quadrati sarà sufficiente.

Questo è il problem che si sta tentando di risolvere. (Caso planare, selezionare tutti i punti ordinati da un asse x, yo Z. Quindi utilizzare PHP per elaborarli)

MySQL ha anche un Spatial Database che può avere questo come funzione. Non sono comunque positivo.

Answer 5

penso che le osservazioni di cui sopra sono tutte vere, ma sono - a mio modesto parere - non rispondere alla domanda originale. (Correggimi se sbaglio). Quindi, lasciatemi aggiungere i miei 50 cent:

Stai chiedendo un'istruzione select, che, data la tua tabella è chiamata 'colors', e date le tue colonne sono chiamate r, geb, sono numeri interi 0 ..255, e siete alla ricerca per il valore, nella tabella, più vicina a un dato valore, consente di dire: rr, gg, bb, quindi oserei provare il seguente:

select min(sqrt((rr-r)*(rr-r)+(gg-g)*(gg-g)+(bb-b)*(bb-b))) from colors; 

Ora, questa risposta è dato con un sacco di avvertimenti, in quanto non sono sicuro di aver risposto correttamente alla domanda, quindi conferma se è giusto o correggimi in modo da poterti aiutare.