2D 점 구름에서 가장 큰 빈 사각형 찾기 (방향이 어긋남)

Question

설명했듯이 주어진 2D 점 구름에서 가장 큰 빈 사각형을 찾고 싶습니다. 이 정보는 이미지에 녹색 선으로 표시된 평행선을 얻는 데 사용되며, LiDAR가 회전 한 각도를 얻는 데 사용됩니다.

나는이 점 구름 데이터로 matlab에 convex hull, boundary, alpha shape 함수를 시도했다. 그것의 모습에서, 나는 내가 생각에

(1) 점 두 조각으로 클라우드 (선물 포장 너 한테?)하고 휴식 후

(2) 경계 기능을 적용; 경계 함수에서 좌표를 추출하면

(3) RANSAC 라인 피팅을 실행하려고합니다.

그러나 RANSAC은 라인의 "적합성"을 판단하기 위해 더 많은 포인트가 필요합니다. 현재 나는 Hough Transform을 탐색하여 해당 라인 감지가이 경우에 효과가 있는지 확인합니다.

따라서 여기 질문은,

(1) 나는 녹색 선을 발견 할 수있는 권리 트랙에 무엇입니까? 아니면 더 좋은 방법이 있습니까?

(2) 라인이 수직 일 때 라인의 각도 값/기울기를 얻는 방법 (탄 (90) = INF)

번째 이미지 원점 클라우드 포인트의 중심에있을 수 도시

또는 오프셋에서. 하나는 그들 사이의 거리가 클러스터에서 두 지점을 각각 찾아 당신은 두 개의 클러스터를 찾을 수 kmeans 클러스터링을 사용할 수 있습니다

Answer 1

중심에서 다양한 거리에 평행선있을 것입니다 가정 할 수있다 최소

%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