알고리즘 - Convex Hull 문제

오늘 다룰 내용은 Convex Hull 이라고 불리우는 알고리즘 문제입니다. 

이 문제는 무작위로 배치된 다수의 점들사이에서 다른 모든점들을 감싸는 직선들을 만들고

그 직선들을 이루는 점들을 찾는 문제입니다.이 점들을 감싸는 직선은 볼록다각형의 형태를 가지고있어야하며

그 외의 형태는 인정되지않습니다.

위 사진 처럼 점들이 나열되어있을때 

이러한 형태로 만드는것이 목표입니다.

 

이를 위한 방법에는 여러가지가 있는데 그중 가장 간단한 두 점을 기준으로 하는방법을 설명하겠습니다.

그라함 스캔이라는 방법도 있는데 이 방법은 추후 설명하겠습니다.

 

우선 두점을 잇는 직선을 하나 그려줍니다.

그 후 그 직선을 기준으로 다른 점들의 위치를 계산해줍니다.

모든점이 한쪽에만 위치한다면 두 점은 컨벡스헐을 이루는 점이되고 그렇지않다면 다른 점으로 넘어갑니다.

이를 반복하면 컨벡스헐을 완성하게 됩니다.

이처럼 모든 경우를 탐색하여 답을 찾는 알고리즘을 브루트 포스라고 지칭합니다.

std::set<int> hullBruteForce ( std::vector< Point > const& points ) {
	int num_points = points.size();
	if ( num_points < 3 ) throw;
	std::set<int> hull_indices;
	std::pair<bool, bool> trigSide;
	std::pair<bool, bool> getSide;
	for (int i = 0; i < num_points - 1; i++)
	{
		for (int j = i; j < num_points; j++)
		{
			trigSide.first = true;
			trigSide.second = true;
			for (int k = 0; k < num_points && (trigSide.first || trigSide.second); k++)
			{
				getSide = get_location(points[i].x, points[i].y, points[j].x, points[j].y, points[k].x, points[k].y);
				if (i != k && j != k)
				{
					trigSide.first = getSide.first && trigSide.first;
					trigSide.second = getSide.second && trigSide.second;
				}
			}
			if (trigSide.first || trigSide.second)
			{
				hull_indices.insert(i);
				hull_indices.insert(j);
			}
		}
	}
	return hull_indices;
}

위 코드가 해당 내용을 바탕으로 구현한 코드입니다.

for (int i = 0; i < num_points - 1; i++)
	{
		for (int j = i; j < num_points; j++)
		{
			trigSide.first = true;
			trigSide.second = true;
			for (int k = 0; k < num_points && (trigSide.first || trigSide.second); k++)
			{
				getSide = get_location(points[i].x, points[i].y, points[j].x, points[j].y, points[k].x, points[k].y);
				if (i != k && j != k)
				{
					trigSide.first = getSide.first && trigSide.first;
					trigSide.second = getSide.second && trigSide.second;
				}
			}
			if (trigSide.first || trigSide.second)
			{
				hull_indices.insert(i);
				hull_indices.insert(j);
			}
		}
	}

우선 첫 점을 기준으로 잡고 다른 점 하나를 찾습니다. 

trigSide.first = true;
trigSide.second = true;

이 두 플래그는 참으로 시작해서 get_location 함수를 통해 좌우 위치를 확인합니다. 위치에 따라 각각 참,거짓을 리턴하기때문에 한쪽에만 있을경우 하나의 값만 참이 되고 다른경우엔 두 값 모두 거짓이 되게 됩니다.

trigSide.first = getSide.first && trigSide.first;
trigSide.second = getSide.second && trigSide.second;

위의 부분이 해당내용입니다.

trigSide.first || trigSide.second

아래 내용이 두 값이 모두 거짓일때 루프를 탈출하게하는 부분입니다.

if (trigSide.first || trigSide.second)
{
		hull_indices.insert(i);
		hull_indices.insert(j);
}

성공적으로 루프를 나왔을때 나온 두 값을 리턴할 값에 넣어줍니다.

set 컨테이너에 들어있기에 중복되는 값을 처리해줍니다.