rettangolo ellisse

Question

mi è stato dato un assegnazione di un modulo di grafica, una parte dei quali è calcolare l'MBR ellisse di un insieme di forme arbitrarie. L'ellisse non deve essere allineata sull'asse.

Ciò sta funzionando in java (yuk) utilizzando le forme AWT, così posso utilizzare tutti gli strumenti forma fornisce per controllare il contenimento/intersezione di oggetti.

Answer 1

Stai cercando il Minimum Volume Enclosing Ellipsoid, o nel tuo caso 2D, la superficie minima. Questo problema di ottimizzazione è convesso e può essere risolto in modo efficiente. Controlla il codice MATLAB nel link che ho incluso: l'implementazione è banale e non richiede nulla di più complesso dell'inversione della matrice.

Chiunque sia interessato alla matematica dovrebbe leggere this document.

Inoltre, tracciare l'ellisse è anche semplice - questo può essere trovato here, ma avrete bisogno di una funzione specifica di MATLAB per generare punti sull'ellisse.

Ma poiché l'algoritmo restituisce l'equazione dell'ellisse in forma matriciale,

matrix form http://mathurl.com/yz7flxe.png

è possibile utilizzare questo codice per vedere come è possibile convertire l'equazione per la forma canonica,

canonical http://mathurl.com/y86tlbw.png

utilizzando Singular Value Decomposition (SVD). E quindi è abbastanza facile tracciare l'ellisse usando lo canonical form.

Ecco il risultato del codice MATLAB su un insieme di 10 punti 2D casuali (blu).

Altri metodi come PCA non garantisce che l'ellisse ottenuto dalla decomposizione (eigen/valore singolare) sarà minimo delimitazione dell'ellisse poiché punti esterni dell'ellisse è un'indicazione della varianza.

EDIT:

Quindi, se qualcuno ha letto il documento, ci sono due modi per andare su questo in 2D: ecco il pseudocodice dell'algoritmo ottimale - l'algoritmo non ottimale è chiaramente spiegato nel documento:

algoritmo ottimale:

Input: A 2x10 matrix P storing 10 2D points 
     and tolerance = tolerance for error. 
Output: The equation of the ellipse in the matrix form, 
     i.e. a 2x2 matrix A and a 2x1 vector C representing 
     the center of the ellipse. 

// Dimension of the points 
d = 2; 
// Number of points 
N = 10; 

// Add a row of 1s to the 2xN matrix P - so Q is 3xN now. 
Q = [P;ones(1,N)] 

// Initialize 
count = 1; 
err = 1; 
//u is an Nx1 vector where each element is 1/N 
u = (1/N) * ones(N,1)  

// Khachiyan Algorithm 
while err > tolerance 
{ 
    // Matrix multiplication: 
    // diag(u) : if u is a vector, places the elements of u 
    // in the diagonal of an NxN matrix of zeros 
    X = Q*diag(u)*Q'; // Q' - transpose of Q  

    // inv(X) returns the matrix inverse of X 
    // diag(M) when M is a matrix returns the diagonal vector of M 
    M = diag(Q' * inv(X) * Q); // Q' - transpose of Q 

    // Find the value and location of the maximum element in the vector M 
    maximum = max(M); 
    j = find_maximum_value_location(M); 

    // Calculate the step size for the ascent 
    step_size = (maximum - d -1)/((d+1)*(maximum-1)); 

    // Calculate the new_u: 
    // Take the vector u, and multiply all the elements in it by (1-step_size) 
    new_u = (1 - step_size)*u ; 

    // Increment the jth element of new_u by step_size 
    new_u(j) = new_u(j) + step_size; 

    // Store the error by taking finding the square root of the SSD 
    // between new_u and u 
    // The SSD or sum-of-square-differences, takes two vectors 
    // of the same size, creates a new vector by finding the 
    // difference between corresponding elements, squaring 
    // each difference and adding them all together. 

    // So if the vectors were: a = [1 2 3] and b = [5 4 6], then: 
    // SSD = (1-5)^2 + (2-4)^2 + (3-6)^2; 
    // And the norm(a-b) = sqrt(SSD); 
    err = norm(new_u - u); 

    // Increment count and replace u 
    count = count + 1; 
    u = new_u; 
} 

// Put the elements of the vector u into the diagonal of a matrix 
// U with the rest of the elements as 0 
U = diag(u); 

// Compute the A-matrix 
A = (1/d) * inv(P * U * P' - (P * u)*(P*u)'); 

// And the center, 
c = P * u;