경계 타원

Question

그래픽 모듈에 대한 할당이 주어 졌는데, 그 중 하나는 임의의 모양 집합의 최소 경계 타원을 계산하는 부분입니다. 타원은 축 정렬되지 않아도됩니다.

이것은 AWT 도형을 사용하여 java (euch)에서 작동하기 때문에 모든 객체 모양을 포함하는 컨테이너/교차를 검사하는 데 사용할 수있는 도구를 사용할 수 있습니다.

Answer 1

Minimum Volume Enclosing Ellipsoid 또는 2D 케이스에서 최소 면적을 찾고 있습니다. 이 최적화 문제는 볼록하고 효율적으로 해결할 수 있습니다. 필자가 포함시킨 링크에서 MATLAB 코드를 확인하십시오. 구현은 간단하고 행렬 반전보다 복잡한 것은 필요하지 않습니다.

수학에 관심이있는 사람은 누구나 this document이어야합니다.

또한 타원을 그리는 작업도 간단합니다.이 작업은 here입니다. 그러나 타원에 점을 생성하려면 MATLAB 관련 함수가 필요합니다. 당신은 당신이 정규의 형식에 방정식을 변환 할 수있는 방법을 보려면이 코드를 사용할 수 있습니다

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

그러나 알고리즘이 매트릭스 형태로 타원의 방정식을 반환하기 때문에,

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

Singular Value Decomposition (SVD)을 사용합니다. 그리고 나서 canonical form을 사용하여 타원을 그릴 수 있습니다.

다음은 10 개의 무작위 2D 포인트 (파란색) 집합에 대한 MATLAB 코드의 결과입니다. PCA 등

다른 방법은 타원 외부 포인트 편차의 지표이기 때문에, 분해 (eigen/특이 값)로부터 얻어진 타원 최소 경계 타원 보장하지 않는다.

편집 :

사람이 문서를 읽을 경우에 따라서, 2D에서 이것에 대해 이동하는 방법은 두 가지가 있습니다 : 여기에 최적의 알고리즘의 의사 코드의 - 최적 알고리즘이 명확하게 문서에 설명되어 있습니다 :

최적의 알고리즘 :

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;