Алгоритм Джарвіса

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм Джарвіса (або алгоритм загортання подарунка) — алгоритм знаходження опуклої оболонки. Часова складність — О(n * h), де n — кількість точок, h — кількість точок опуклої оболонки. Тобто, алгоритм найбільш ефективний у випадку малої кількості точок опуклої оболонки.

Опис алгоритму[ред.ред. код]

Нехай шукана опукла оболонка множини P = \{p_1, p_2, ... p_n\} точок. У якості початкової беремо найлівішу точку (точку з найменшою x-координатою), якщо їх буде декілька, то виберемо серед них найнижчу (точку з найменшою y-координатою). Нехай знайдена точка — точка p_1 (її можна знайти за час O(n) звичайним проходом по всіх точках і порівнянням координат). Точка p_1 напевно є вершиною опуклої оболонки. Далі для кожної точки p_i шукаємо проти годинникової стрілки точки p_{i+1} шляхом знаходження за O(n) серед точок, що залишились, (включно з p_1) точку з найменшим полярним кутом p_{i-1}p_{i}p_{i+1}. Вона і буде наступною вершиною опуклої оболонки. При цьому не обов'язково обчислювати кут — достатньо обчислити векторний добуток (узагальненням векторного добутку для двовимірного випадку є псевдоскалярний добуток) між кутами p_{i}p'_{i+1} та p_{i}p''_{i+1}, де p'_{i+1} — знайдений на даний момент мінімум, p''_{i+1} — претендент (першим мінімумом може бути обрана довільна точка). Якщо векторний добуток від'ємний, то знайдено новий мінімум. Якщо рівний нулю, тобто p'_{i+1} та p''_{i+1} лежать на одній прямій, то мінімум — та, яка лежить далі від точки p_i. Алгоритм продовжує роботу доки p_{i+1} \neq p_1. Чому алгоритм зупиниться? Тому, що точка p_1 (найнижча серед найлівіших точок) у будь-якому випадку належить до точок опуклої оболонки.

Псевдокод[ред.ред. код]

Jarvis(P)
    1) p[1] = найнижча серед найлівіших точок множини P;
    2) i = 1;
    3) do:
         p[i+1] = довільна точка з P (крім вже зарахованих до опуклої оболонки, але включно з p[1]);
             (a)for (для кожної точки j з P, крім вже зарахованих до опуклої оболонки, але включно з p[1]
                 p[i+1] = min_polar_angle(p[i+1], P[j]); // мінімум через векторний добуток
             (b)i = i + 1;
       while p[i] != p[1]
    4) return p;


Реалізація на С++[ред.ред. код]

 
template <class POINT>
inline bool determinantSignum(const POINT &a, const POINT &b, const POINT &c){
	return (((b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y)) >= 0);
}
 
template <class POINT>
void jarvis(std::vector<POINT> &source, std::vector<POINT>& result) 
{
	std::vector<POINT> src = source;
	std::vector<POINT>::iterator leftDownIt = src.begin();
	POINT currentPoint;
	POINT leftDownPoint = *(leftDownIt);
 
	// Finding leftest lowest point
 
	for (it = leftDownIt + 1, end = src.end(); it != end; ++it) 
	{
		currentPoint = *it;
		if (currentPoint.x < leftDownPoint.x){
			leftDownPoint = currentPoint;
			leftDownIt = it;
		} 
		else if (currentPoint.x == leftDownPoint.x){
			if (currentPoint.y < leftDownPoint.y){
				leftDownPoint = currentPoint;
				leftDownIt = it;
			}
		}
	}
 
	// Add selected point to answer
	src.erase(leftDownIt);
	result.push_back(leftDownPoint);
 
	currentPoint = leftDownPoint;
 
	POINT nextPoint, tryPoint;
	typename std::vector<POINT>::iterator nextIt;
 
	do {			
		nextPoint = leftDownPoint;
		nextIt = it;
 
		for (it = src.begin(); it != src.end(); ++it){
			tryPoint = *it;
			if (determinantSignum(nextPoint, currentPoint, tryPoint)){
				nextPoint = tryPoint;
				nextIt = it;
			}
		}
 
		if (nextPoint != leftDownPoint){
			src.erase(nextIt);
			result.push_back(nextPoint);
			currentPoint = nextPoint;
		}
 
	} while(nextPoint != leftDownPoint);
}

Див. також[ред.ред. код]

Посилання[ред.ред. код]

Література[ред.ред. код]

  • Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. Раздел 3.3.3: М.: Мир, 1989.