如何找到 3D 点列表的“内部边界”/“内部凸包”？

Question

我需要一些帮助来编写这个算法。

给定一组线在空间中，我试图找到原点（参考点）时的可访问体积0.5,0.5,0.5，我执行以下操作：

对于每条直线，计算距离和直线上离原点最近的点（0.5,0.5,0.5 )，然后收集所有这些点。

之后，我想计算内部（既不是boundary也不是convhull），因为我想评估 ( 0.5,0.5,0.5)处球的可访问体积。它不是凸包或边界多边形。

---

例如，我想在这个简单的例子中获得绿色（内线）：

---

配置：

从原点 ( 0.5,0.5,0.5) 到直线 的最近点

只有我想要“内部边界”的点，这意味着在内部外部或其边界上限制所有点的形状。

这是我想要其他东西而不是的代码convhull：

close all
N=30;

S1 = cell(1, N);
for k = 1:N, S1{k} = rand(1, 3); end
S2 = cell(1, N);
for k = 1:N, S2{k} = rand(1, 3); end

M1 = cat(3, S1{:});
M2 = cat(3, S2{:});
M  = permute(cat(1, M1, M2), [1, 3, 2]);
figure
plot3(M(:, :, 1), M(:, :, 2), M(:, :, 3))
hold on
[x,y,z] = sphere;
x=x/100;y=y/100;z=z/100;
plot3(x+0.5,y+0.5,z+0.5)


figure 
hold on

NearestIntersectionPoints = cell(1,N); 
for k = 1:N 
    tmp1 = M(1,k,:); tmp2 = M(2,k,:);
    v1=tmp1(1,:); v2=tmp2(1,:);
    [d, intersection] = point_to_line([0.5,0.5,0.5], v1, v2);

    [x,y,z] = sphere;
    x=x/500;y=y/500;z=z/500;
    plot3(x+intersection(1),y+intersection(2),z+intersection(3))
    NearestIntersectionPoints{k} = intersection;

end


MHull = cat(3,NearestIntersectionPoints{:});
X=MHull(:,1,:); Y=MHull(:,2,:); Z=MHull(:,3,:);
X=X(:); Y=Y(:); Z=Z(:);
k = boundary(X,Y,Z);
hold on

plot3(X(k),Y(k),Z(k), 'r-*')


function [d,intersection] = point_to_line(pt, v1, v2)
      a = v1 - v2;
      b = pt - v2;
      d = norm(cross(a,b)) / norm(a);
      theta = asin(norm(cross(a,b))/(norm(a)*norm(b)));
      intersection = v2 + a * cos(theta);

end

Answer 1

我会这样做：

1. 四面体化你的点云

   因此，创建一个由四面体组成的网格，其中四面体不与任何其他面体相交或包含任何点。我这样做：

   1. 结构

   你需要点、三角形和四面体的列表。每个三角形都需要一个计数器，它会告诉您它是否被使用一次或两次。

   2. 创建第一个四面体

   通过 4 个嵌套循环遍历所有点，并检查形成的四面体内部是否不包含任何点。如果没有停止，因为你发现了你的第一个四面体。但O(n^5)由于有很多有效的四面体，它永远不会达到如此高的运行时间......现在只需将此四面体添加到三角形和四面体列表中即可。

   3. 找到下一个四面体

   现在循环遍历所有曾经使用过的三角形。对于每个形式的四面体，使用它所使用的 3 个点，并以与#2中相同的方式找到第 4 个点。有效的四面体不得包含任何点，也不得与列表中任何现有的四面体相交。

   为了确保整个体积被填充而没有孔，您需要通过优先选择列表中已有更多三角形的四面体来确定该过程的优先级。所以首先搜索 4 个三角形，如果没有找到超过 3 个，等等......

   对于每个找到的有效四面体，将其添加到列表中，然后再次查看，直到无法形成有效的四面体......整个过程就在周围，O(n^2)因此要小心点云中的点太多。另外，存储三角形的法线可以大大加快测试速度......

2. 外边界

   外边界由列表中只使用过一次的三角形组成

3. 内部边界

   内部间隙四面体应大于所有其他四面体。因此，请根据平均尺寸检查它们的尺寸，如果较大，则很可能存在间隙。因此，将它们分组到列表中。每个间隙只有大四面体，并且所有四面体必须共享至少一个面（三角形）。现在只需计算每个组的三角形使用情况，所有仅使用一次的三角形将形成您的间隙/孔/内部边界/网格。

如果你的点密度是均匀的，你可以调整这个：

• 在二维点集中寻找漏洞？

并创建点密度的体素图...没有密度的体素要么是间隙，要么是外层空间。这可用于更快更好地选择内部四面体。