Алгоритмы и структуры данных

Выпуклая оболочка с использованием алгоритма Джарвиса

Представляет собой алгоритм, используемый для поиска выпуклой оболочки набора точек.

Алгоритм:
1. Инициализируйте p как крайнюю левую точку.
2. Делаем следующее, пока не возвращаемся к первой (или крайней левой) точке:
⁃ Следующая точка q — это точка такая, что тройка (p, q, r) направлена ​​против часовой стрелки для любой другой точки r.
⁃ Чтобы найти это, мы просто инициализируем q как следующую точку, а затем проходим через все точки.
⁃ Для любой точки i, если i больше против часовой стрелки, т. е. ориентация (p, i, q) против часовой стрелки, то мы обновляем q как i.
⁃ Нашим окончательным значением q будет точка, расположенная крайним против часовой стрелки.
⁃ next[p] = q (сохраните q как следующее из p в выходной выпуклой оболочке).
⁃ p = q (установите p как q для следующей итерации).

Сложность: O(m * n), где n — количество входных точек, а m — количество выходных точек или точек оболочки (m <= n).

www.tgoop.com/the_algorithms/4681

5.4K viewsedited  Jan 26, 2024 at 09:00

Выпуклая оболочка с использованием алгоритма Джарвиса

Представляет собой алгоритм, используемый для поиска выпуклой оболочки набора точек.

Алгоритм:
1. Инициализируйте p как крайнюю левую точку.
2. Делаем следующее, пока не возвращаемся к первой (или крайней левой) точке:
⁃ Следующая точка q — это точка такая, что тройка (p, q, r) направлена ​​против часовой стрелки для любой другой точки r.
⁃ Чтобы найти это, мы просто инициализируем q как следующую точку, а затем проходим через все точки.
⁃ Для любой точки i, если i больше против часовой стрелки, т. е. ориентация (p, i, q) против часовой стрелки, то мы обновляем q как i.
⁃ Нашим окончательным значением q будет точка, расположенная крайним против часовой стрелки.
⁃ next[p] = q (сохраните q как следующее из p в выходной выпуклой оболочке).
⁃ p = q (установите p как q для следующей итерации).

Сложность: O(m * n), где n — количество входных точек, а m — количество выходных точек или точек оболочки (m <= n).

BY Алгоритмы и структуры данных