Das größte leere Rechteck (desorientiert) in der 2D Punktwolke finden

Question

Wie beschrieben, würde ich gerne das größte leere Rechteck in einer gegebenen 2D Punktwolke finden. Diese Information wird dann verwendet, um parallele Linien als grüne Linien in den Bildern zu erhalten, die dann verwendet werden, um den Winkel zu erhalten, den der LiDAR gedreht hat.

Ich habe versucht konvexe Hülle, Grenze und Alpha-Form-Funktionen in Matlab mit diesem Punkt Cloud-Daten. Von den Blicken von ihm, ich glaube, ich habe zu

(1) brechen die Punktwolke in zwei Stücke (Geschenkverpackung algo?) Und dann

(2) gelten Grenzfunktion; Mit Koordinatenauszügen von der Grenzfunktion,

(3) Ich denke, RANSAC Linie zu laufen zu führen.

Allerdings benötigt RANSAC mehr Punkte, um die "Fitness" der Linie zu beurteilen. Momentan erkunde ich Hough Transform, um zu sehen, ob diese Zeilenerkennung für diesen Fall funktioniert.

So hier ist die Frage,

(1) bin ich in der richtigen Spur, die grünen Linien zu finden? Oder gibt es einen besseren Weg?

(2) Wie den Winkelwert/Gefälle von der Linie zu erhalten, wenn die Leitung vertikal ist (tan (90) = inf)

Das zweite Bild des Ursprung zeigt in der Mitte der Trübungspunkte sein kann, oder bei einem Offset. Man kann davon ausgehen, es wird von der Mitte mit unterschiedlichem Abstand parallelen Linien sein

Answer 1

Sie KMeans Clustering zwei Cluster verwenden können, finden dann zwei Punkte finden jeweils aus einem Cluster, der zwischen ihnen Abstand 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