Jarvis(P)http://ru.wikipedia.org/wiki/Алгоритм_Джарвиса
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://www.pm298.ru/preobr4.php
Комментариев нет:
Отправить комментарий