Recherche du plus grand rectangle vide (désorienté) dans le nuage de points 2D

Question

Comme décrit, j'aimerais trouver le plus grand rectangle vide dans un nuage de points 2D donné. Ces informations seront ensuite utilisées pour obtenir des lignes parallèles représentées par des lignes vertes dans les images, qui seront ensuite utilisées pour obtenir l'angle de rotation du LiDAR.

J'ai essayé des fonctions de coque convexe, de limite et de forme alpha dans matlab avec ces données de nuages ​​de points. Des regards de celui-ci, je pense que je dois

(1) briser le nuage de points en deux morceaux (cadeau algo wrap?) Puis

(2) appliquer la fonction limite; Avec des extraits de coordonnées de la fonction de frontière,

(3) Je pense à exécuter le raccord de ligne RANSAC.

Cependant, RANSAC a besoin de plus de points pour juger de la "condition physique" de la ligne. Actuellement, j'explore Hough Transform pour voir si cette détection de ligne fonctionnerait dans ce cas.

La question est donc ici,

(1) Je suis dans la bonne voie pour trouver les lignes vertes? Ou y a-t-il un meilleur moyen?

(2) Comment obtenir la valeur angulaire/gradient de la ligne lorsque la ligne est verticale (tan (90) = inf)

La deuxième image montre l'origine peut se trouver au centre des points de trouble ou à un décalage. On peut supposer qu'il y aura des lignes parallèles à distance variant du centre

Answer 1

Vous pouvez utiliser le regroupement des centres mobiles pour trouver deux groupes trouvent alors deux points chacun d'un cluster distance entre eux est minimum

%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