задачу, что, к сожалению,
задачу, что, к сожалению, усложнит ее: будем выбирать подмножество точек-вершин Ncover так, чтобы получившийся многоугольник содержал внутри все остальные точкиN \Ncover. Стоит отметить, что сформулированная задача весьма актуальна и встречается во многих приложениях, в частности, в прикладных задачах теории графов; не случайно у подмножества Ncover есть специальное название - выпуклая оболочка.
Актуальность задачи породила немалое число конкурентоспособных алгоритмов ее решения, работающих для “больших” N (иначе рентабелен обыкновенный перебор всевозможных подмножеств N-).
Рассмотрим здесь один из вариантов решения - алгоритм Грэхема. Он состоит из нескольких этапов, реализация каждого из которых, в отдельности, нам уже знакома.
*
Инициализируем набор из N точек с декартовыми координатами Xi и Yi(i=1:N).
*
Найдем какую-нибудь внутреннюю точку будущего многоугольника. Для этой цели можно воспользоваться одним из следующих способов:
*
либо выбрать тройку точек
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
