Minimum Area Rectangle1 [알고리즘] 2차원 점군을 감싸는 최소면적의 직사각형 그리기(작성중) 본 과정은 Convex Hull과 Rotating Caliper 알고리즘을 학습해 가는 과정입니다. 결론만 얻고 싶은 분은 다른 분의 포스팅을 참고하시길 추천드립니다. 페이스북에서 우연히 읽게 된 질문글이다. 2차원 평면상에 수십여개의 점이 있을 때, 이 점을 모두 포함하는 최소 면적의 직사각형 그리는 방법? 여러가지 해법이 있겠지만, (막연하게나마 Convex Hull과 Rotating Caliper 알고리즘에 대해선 들은 적이 있었다.) 아주 단순한 방식을 들어 풀 수 있을 것 같다는 생각이 들었다. 아래와 같은 점군이 있다고 가정하자. 대략 아래처럼 직사각형이 그려져야 한다. 직사각형이 회전하지 않아도 된다는 가정하에는 그냥 x_min, x_max, y_min, y_max 네 점을 찾아서 직사각형을.. 2024. 1. 14. 이전 1 다음
