Come ridurre i punti di chiusura

Question

Come ridurre i punti di chiusura

#1 da (1 voti)
#2 da (0 voti)

1

input: matrice C 2xN (punti 2D)

output: matrice C 2xM (punti 2D) con punti uguali o inferiori.
Diciamo che abbiamo una matrice C 2xN che contiene diversi punti 2D, e sembra qualcosa del genere:

Quellochevogliamoèraggruppareipunti"vicini" a un punto, misurato dalla media degli altri punti. Ad esempio, nella seconda immagine, ogni gruppo di cerchi blu sarà un punto, la coordinata del punto sarà il punto medio di tutti i punti nel cerchio blu. anche dicendo "vicino", intendo che: la loro distanza l'una dall'altra sarà più piccola del DELTA (noto scalare). L'output desiderato è:

Riguardo al tempo di esecuzione dell'algoritmo, non ho la richiesta di limite superiore ma chiamo quel metodo più volte ...
Sto usando Matlab e quello che ho provato è questo:

function C = ReduceClosePoints(C ,l_boundry)
    x_size = abs(l_boundry(1,1)-l_boundry(1,2)); %220
    DELTA = x_size/10;
    T = [];
    for i=1:size(C,2)
        sum = C(:,i);
        n=1;
        for j=1:size(C,2)
            if i~=j     %not same point
                D = DistancePointToPoint(C(:,i),C(:,j));
                if D < DELTA
                    sum = sum + C(:,j);
                    n=n+1;
                end
            end
        end
        sum = sum./n; %new point -> save in T matrix
        T = [T sum];
    end
    C = T;
end

E non funziona :( Anche io sono nuovo di Matlab.
Grazie per il tuo aiuto !!

algorithms matlab

posta Matan Touti 25.01.2014 - 14:34

fonte

2 risposte

0

Il problema non è banale!

Assumi tre punti A, B, C in cui la distanza d (A, B) è inferiore a DELTA, d (B, C) è inferiore a DELTA, ma non d (A, C). Ora puoi selezionare la distanza minima per unire due punti (diciamo A e B) e ottenere un risultato intermedio AB e C. Supponiamo che la distanza d (AB, C) sia minore di DELTA otterrai un punto ABC che non è la "media" di tre punti.

Credo che mettere una griglia su tutti i punti e le coordinate del punto di serraggio su quella griglia siano migliori.

risposta data 25.01.2014 - 15:46

fonte

Leggi altre domande sui tag algorithms matlab

Dove si trova il codice non MVVM in un'app MVVM? Notifica a più ascoltatori

score 1 · Accepted Answer

Devi farlo in due passaggi. In primo luogo, raggruppa i punti vicini insieme. Quindi, sostituisci ciascun gruppo di un punto.

Lascia che s sia un sottoinsieme non vuoto dei tuoi punti e distance(p,s) la minima distanza tra p e qualche elemento di s. Ora ecco alcuni pseudocodici per creare gruppi di "point clusters":

 input: pointlist
 groups:={}   // will contain groups of points, disjoint subsets of "pointlist"
 for each p in pointlist
     let newgroup:={p} 
     for each g in groups where 'distance(p,g)<DELTA'
          newgroup := join(newgroup, g)  // join the two sets
          remove g from groups
     next g
     add newgroup to groups
 next p
 output: groups

Si noti che questo algoritmo non garantisce che ogni coppia di punti di un gruppo abbia una distanza < DELTA, solo che ciascun gruppo trovato non può essere diviso in due gruppi più piccoli con distance > = DELTA. Devi decidere da solo se è sufficiente, ma come ha sottolineato @ DieterLücking, non aspettarti di trovare un algoritmo per risolvere il problema esattamente come l'hai descritto in origine.

Dopo aver calcolato i tuoi gruppi di punti, puoi sostituire ciascun gruppo in base al valore mediano dei suoi punti.

Riguardo al tempo di esecuzione: il tempo di esecuzione dipende molto dal calcolo della funzione distance veloce. Quindi, nel caso in cui l'implementazione diretta di sottoinsiemi da liste o array non sia abbastanza veloce (che dovresti testare prima di iniziare a ottimizzare!), Allora potresti prendere in considerazione l'uso di una struttura dati migliorata qui. Ad esempio, puoi tenere traccia del "rettangolo di selezione" di tutti gli elementi di un sottoinsieme, poiché se distance(p, boundingbox(s))>=DELTA , puoi essere sicuro che anche distance(p, s)>=DELTA .