algorithm - 如何找到 3D 点列表的 "interior boundary"/"interior convex hull"？

Question

我需要一些帮助来编写这个 algorithm .

对于一组给定的空间线，我试图在原点(引用点)为 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. 结构

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

   1. 创建第一个四面体

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

   1. 找到下一个四面体

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

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

   对于每个找到的有效四面体，将其添加到列表中并再次查看，直到不能形成有效的四面体......整个过程大约是 O(n^2) 所以要小心太多点云中的点。存储三角形的法线也可以大大加快测试速度......

2. 外边界

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

3. 内部边界

   内部间隙四面体应该比所有其他四面体都大。因此，请将它们的大小与平均大小进行比较，如果更大，则很可能是差距。因此，将它们分组到列表中。每个间隙只有大四面体，并且它们都必须至少共享一个面(三角形)。现在，只需单独计算每个组的三角形使用情况，仅使用一次的所有三角形将形成您的间隙/孔/内部边界/网格。

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

• Finding holes in 2d point sets?

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