(Open3D)#5 포인트 클라우드로 직사각형 단면 수치 정보 확인하기 - Convex Hull 알고리즘 개념

(Open3D)#4 포인트 클라우드로 직사각형 단면 수치 정보 확인하기 - RANSAC 알고리즘 적용 (tistory.com)

(Open3D)#4 포인트 클라우드로 직사각형 단면 수치 정보 확인하기 - RANSAC 알고리즘 적용

 

 

 

 

 

지난 글에서 RANSAC 알고리즘을 통해 실제 공사현장의 포인트 클라우드에서 바닥 평면의 포인트클라우드 데이터를 뽑아냈다.
 
최적의 평면 데이터, 즉 최적의 plane에서 이제 수치 정보(가로,세로)길이를 확인할 것이다.
 
Convex hull 알고리즘을 활용하여 단면의 수치 정보를 확인할 것인데, 확인하기 전에 간단하게 Convex Hull 알고리즘에 대해 정리하고자 한다.
 
먼저, Convex Hull 이란
주어진 어떤 점들을 중에서 가장 외각의 점들을 연결한 다각형을 의미한다.
다시 말해서, 주어진 어떤 점들을 모두 포함하는 넓이가 최소인 볼록 다각형이다.
볼록 다각형의 모든 내각의 크기는 180도 이하이다.

Convex Hull 알고리즘의 원리는 다음과 같다.
1. 기준점을 찾는다. (보통 왼쪽 하단 아니면 오른쪽 하단이 기준점이 되어 시작한다.)
2. 기준점을 기준으로 다른 모든 점들을 반시계 방향으로 정렬한다.
3. 정렬된 점들을 차례대로 스택에 넣는다.
4. 차례대로 스택에 넣는 과정에서 반시계방향이 아닌, 시계방향으로 이루어진 점이 들어가게 되면 그 점을 스택에서 제거하고, 다른 점을 찾아서 다시 스택에 넣어 확인한다.
5. 이러한 과정을 반복하여 모든 스택이 쌓이면 볼록 껍질이 완성된다.
 

 
위 사진과 같은 상황이 오면 스택을 제거하고 다시 다른 점들을 찾고, 올바른 점을 찾으면 스택에 넣는 것이다.
 

 
이러한 Convex Hull 알고리즘을 활용하여 원하는 결과값을 얻을 수 있도록 조금 응용할 것이다.
 
이렇게 간단하게 Convex Hull 에 대하여 알아보았다.
 
마지막으로 다음 글에서 Convex Hull을 응용하여 단면의 수치정보를 확인할 것이다.

 

 

(Open3D)#6 포인트 클라우드로 직사각형 단면 수치 정보 확인하기 - Convex Hull 알고리즘 활용 (tistory.com)

(Open3D)#6 포인트 클라우드로 직사각형 단면 수치 정보 확인하기 - Convex Hull 알고리즘 활용