볼록 껍질
점 집합의 볼록 껍질
이 계산기에 대하여
볼록 껍질 계산기는 앤드루의 단조 연쇄 알고리즘으로 2D 점 집합을 감싸는 가장 작은 볼록 다각형을 찾습니다. 껍질의 꼭짓점을 시계 반대 방향 순서로 나열하고, 껍질 위와 안쪽에 있는 점의 수를 세며, 정확한 넓이와 둘레를 결과 윤곽선이 그려진 산점도와 함께 보여 줍니다. 중복된 점과 한 직선 위의 점도 올바르게 처리합니다.
볼록 껍질을 구하는 방법
- 점을 쉼표로 구분한 x,y 쌍으로 입력하세요. 순서는 상관없습니다.
- 계산기가 중복된 점을 합치고 점을 왼쪽에서 오른쪽으로 정렬합니다.
- 정렬된 점을 차례로 훑어 아래쪽과 위쪽 경계를 만들며, 윤곽선이 왼쪽으로 꺾이는 꼭짓점만 남깁니다.
- 껍질 꼭짓점, 넓이, 둘레를 확인하고 점들 위에 그려진 윤곽선을 살펴보세요.
대표적인 예
- 정사각형 꼭짓점 0,0 6,0 6,4 0,4와 내부 점 3,2, 2,1 → 껍질 꼭짓점 4개, 넓이 24, 둘레 20
- 삼각형 0,0 4,0 0,3 → 껍질 꼭짓점 3개, 넓이 6, 둘레 12
- 한 직선 위의 점 0,0 1,1 2,2 3,3 → 퇴화된 껍질 (선분), 넓이 0
- 정사각형 0,0 4,0 4,4 0,4와 꼭대기 점 2,5 → 꼭대기 점이 윗변을 넓혀 껍질 꼭짓점 5개
자주 묻는 질문
볼록 껍질이란 무엇인가요?
점 집합의 볼록 껍질은 모든 점을 포함하는 가장 작은 볼록 다각형입니다. 가장 바깥쪽 점들에 고무줄을 걸었다가 놓아 팽팽하게 조여진 모양과 같습니다.
어떤 점이 껍질 꼭짓점이 되나요?
가장 바깥쪽 모서리에 있는 점만 껍질 위에 놓입니다. 도형 안쪽에 있는 점과 껍질의 변 위에 정확히 놓인 점은 꼭짓점으로 나열되지 않습니다.
중복된 점이나 한 직선 위의 점은 어떻게 처리하나요?
먼저 같은 점을 하나로 합칩니다. 모든 점이 한 직선 위에 있으면 껍질은 넓이 0인 선분으로 퇴화하며, 계산기는 이를 퇴화된 껍질로 표시합니다.
점이 몇 개 필요한가요?
넓이가 양수인 껍질을 만들려면 한 직선 위에 있지 않은 서로 다른 점이 3개 이상 필요합니다.