понедельник, 18 июня 2012 г.

Алгоритм заворачивания подарка

Нахождение выпуклой оболочки при заданных координатах точек
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;
http://ru.wikipedia.org/wiki/Алгоритм_Джарвиса
http://www.pm298.ru/preobr4.php

Комментариев нет: