检查点是否位于多维椭球内

Check if point lies inside mulit-dimensional ellipsoid

我无法确定某些点是否位于多维椭球体内部。 真正的问题是由潜在的转换(旋转、平移)引起的,我不知道如何将它们应用到我的计算中。

在我的工作中,我将有一组点,我需要找到这些点的最小体积封闭椭球体。然后我将不得不检查其他点集并确定它们中的哪些点属于找到的椭圆体。

我决定使用 here:

中的代码
function [] = Checkup()
points  = [[ 0.53135758, -0.25818091, -0.32382715] 
    [ 0.58368177, -0.3286576,  -0.23854156,] 
    [ 0.18741533,  0.03066228, -0.94294771] 
    [ 0.65685862, -0.09220681, -0.60347573]
    [ 0.63137604, -0.22978685, -0.27479238]
    [ 0.59683195, -0.15111101, -0.40536606]
    [ 0.68646128,  0.0046802,  -0.68407367]
    [ 0.62311759,  0.0101013,  -0.75863324]];
P = points\'; % <- remove the \ symbol here
dimen = length(P(:,1));

% c - vector with ellipse centers
[A, c] = MinVolEllipse(P, 0.01);
[~, Q, V] = svd(A);
radiuses = 1:dimen;

% Calculate radiuses
for i = 1:dimen
    radiuses(1, i) = 1 / sqrt(Q(i,i));
end

% Check if points lie within ellipse and print Ok for every point inside ellipsoid
for i = 1:length(P(1,:)) % length(P(1,:)) is number of points
    value = 0;
    for j = 1:dimen
        %adding ((p_i - c_i) / (r_i))^2 value
        value = value + ( ( (P(j,i) - c(j, 1) )^2 ) / (radiuses(1, j)^2));

    end
    if value <= 1
        disp('Ok')
    end
end

现在这段代码不打印 Ok 文本(但它应该打印 8 次)。

根据this:"V is the rotation matrix that gives you the orientation of the ellipsoid" 我认为这是我的代码工作需要使用的最后一个元素。

我的做法

好的,所以我对我的代码做了一些修改。 现在我尝试做这样的事情:

假设我有椭圆体的中心及其半径。

对于每个点:

  1. 按如下方式更新位置:point = point - center -> 换句话说,将其翻译成椭圆体的中心点 (0, 0, ... 0)

  2. 像椭球平行于所有轴一样旋转它:point = invert(V) * point

  3. 使用等式检查点是否位于椭球内:(point.x / radius.x)^2 + ... + (point.i / radius.i)^2 其中 i 是维数

  4. 如果等式给出的结果 <= 1 则点位于椭圆内。

这个方法好吗?我的意思是 - 我不知道我是否可以反转 V 矩阵并将其用作反转之前的旋转...

正确的解决方案

看来我提出的方法不错,但还有一个更好:

function [result] = Ellipse()
% Returns vector consisting of 10 entries
% that represent error ratio for every test set 

result = 0:9;

% Run tests for all point sets
for pointSet = 0:9
    [Ptraining, Ptest] = LoadPointSet(pointSet);
    count = 0;

    % c - vector with ellipse centers
    [A, c] = MinVolEllipse(Ptraining, 0.00001);

    % Check if points lie within ellipse
    for i = 1:length(Ptest(1,:)) % length(P(1,:)) is number of points
        pp = Ptest(:, i) - c;
        value = pp' * A * pp;    
        if value > 1
            count = count + 1;
        end
    end

    % Get the error ratio
    index = pointSet + 1;
    result(index) = count / length(Ptest(1,:));
end

end

Right now this code does not print Ok text (but it should print it 8 times).

首先,没有理由期望 MinVolEllipse 函数等近似算法会给出封闭椭圆的精确最小体积。您正在为 MinVolEllipse 提供公差,因此您应该预料到该函数的结果会出现一些错误。

更重要的是,你不需要在这里使用奇异值分解(但详见下文)。椭球面的方程是 (x-c)TA(x-c)=1。您需要检查的是每个点的 (x-c)TA(x-c) 是否小于一(加上一些公差):

tol_mvee = 0.01;
tol_dist = 0.1;

[A, c] = MinVolEllipse(P, tol_mvee);

% Check if points lie within ellipse and print Ok for every point inside ellipsoid
for i = 1:length(P(1,:)) % length(P(1,:)) is number of points
    x   = P(i,:);
    x_c = x-c;
    d   = dot(x_c, A*x_c);
    if d < 1+tol_dist
        disp('Ok');
    end
end

你的第一个点显然在椭圆体内。所有其他七个点都在或非常接近真正的最小体积封闭椭球的边界。该算法在这方面会遇到一些麻烦,并且由于生成的椭球体明显是椭圆体而不是球形这一事实也会遇到一些麻烦(请参阅下面的条件编号)。

奇异值分解可能有助于告诉您来自 MinVolEllipseA 矩阵是否病态,在这个特定问题中就是这种情况。您矩阵的条件数超过 200,这意味着您最好不要期望得到公差远小于 1e-6 的结果。