在 2D 点云中查找最大的空矩形（迷失方向）

Question

如上所述，我想在给定的二维点云中找到最大的空矩形。然后，此信息将用于获取图像中显示为绿线的平行线，然后用于获取 LiDAR 旋转的角度。

我已经在 matlab 中使用此点云数据尝试了凸包、边界和 alpha 形状函数。看样子，我想我必须

(1) 将点云分成两块（礼品包装算法？）然后

(2) 应用边界函数；从边界函数中提取坐标，

(3) 我正在考虑运行 RANSAC 线拟合。

但是RANSAC需要更多的点来判断直线的"fitness"。目前我正在探索霍夫变换，看看这种线检测是否适用于这种情况。

因此这里的问题是，

(1) 我是否在正确的轨道上找到绿线？或者有更好的方法吗？

(2) 直线垂直时如何从直线中得到angular value/gradient (tan(90) = inf)

第二张图片描绘的原点可能位于云点的中心或偏移处。可以假设会有距离中心不同距离的平行线

Answer 1

您可以使用 kmeans 聚类找到两个聚类，然后从它们之间的距离最小的聚类中分别找到两个点

%a function for rotation of points
function out = rot(theta,data)
    mat = [cos(theta), -sin(theta);
           sin(theta), cos(theta)];
    out = data * mat.';
end
a= [rand(505,1)*.4 , rand(505,1) ];
b= [rand(500,1)*.4 + .6 , rand(500,1)];
a = [a;b];
rt = rot(.4,a);
%kmeans clustering
km=kmeans(rt,2);
class1 = rt(km==1,:);
class2=rt(km==2,:);
%find min distance
[srch, d] = dsearchn(class1, class2);
[mn, I] = min(d);

plot(rt(:,1), rt(:,2),'.')
hold on
p1 = class1(srch(I),:);
p2 = class2(I,:);
plot(p1(1),p1(2),'*r')
plot(p2(1),p2(2),'*g')
xy = [class1(srch(I),:);class2(I,:)]
plot(xy(:,1),xy(:,2),'-g')
axis equal

在 2D 点云中查找最大的空矩形（迷失方向）

Finding largest empty rectangle(disorientated) in 2D Point Cloud

matlab

image-processing

discrete-mathematics

point-clouds