Поиск большого пустого прямоугольника (дезориентированного) в 2D-облаке точек

Question

Как описано, я хотел бы найти самый большой пустой прямоугольник в данном облаке 2D-точки. Эта информация затем будет использоваться для получения параллельных линий, обозначенных зелеными линиями на изображениях, которые затем будут использоваться для получения угла, который LiDAR повернул.

Я пробовал функции выпуклой оболочки, границы и альфа-формы в Matlab с данными облака облаков. Судя по ней, я думаю, что я должен

(1) разбить облако точек на два куски (подарочная упаковка Algo?), А затем

(2) применять граничную функцию; С координатами выдержки из граничной функции

(3) Я собираюсь запустить линию RANSAC.

Однако RANSAC нуждается в большем количестве баллов, чтобы судить о «пригодности» линии. В настоящее время я изучаю Hough Transform, чтобы узнать, будет ли обнаружение этой линии работать в этом случае.

Таким образом, вопрос здесь,

(1) я в правильном направлении, чтобы найти зеленые линии? Или есть лучший способ?

(2) Как получить угловое значение/градиент от линии, когда линия по вертикали (тангенс (90) = инф)

Второе изображение изображает источник может находиться в центре точек облака или на смещение. Можно предположить, что будут параллельные линии с переменным расстоянием от центра

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