Рассмотрим два из возможных алгоритмов. Вариант 1. Строим выпуклую оболочку данного множества точек. Если все точки множества A лежат на контуре, то задача решена. Если же нет, то ищем точку l с минимальным расстоянием до контура -- пусть это минимальное расстояние до стороны фигуры (u,v) (если таких точек несколько, то берем любую из них), вставляем в контур точку l (вместо контура ... u,v ... будет ... u,l,v, ...). Для оставшихся точек повторяем описанную выше процедуру, пока последняя не будет вставлена в контур. Вариант 2. Строим выпуклую оболочку V данного множества точек. Если все точки множества A лежат на контуре, то задача решена. Иначе обозначим через A1 все внутренние точки выпуклой оболочки V. Строим для нового множества A1 выпуклую оболочку V1 (контуры V и V1 не пересекаются!). "Склеиваем" два контура: Выберем по паре последовательных вершин p,s и p1,s1 на контурах V и V1 соответственно так, чтобы в четырехугольнике с вершинами s,p,p1,s1 не лежало больше никаких других точек контуров V и V1. Разрываем контуры V и V1 (убирая ребра (p,s) и (p1,s1)) и объединяем их (добавляя ребра (p,p1) и (s,s1)). Если внутри V1 нет внутренних точек, то задача решена, иначе же с внутренними точками V1 проделываем те же самые операции: находим выпуклую оболочку и пары последовательных точек на контурах, разрываем и склеиваем контуры, и т.д., пока не получим, что последняя построенная выпуклая оболочка содержит в себе 0, 1 или 2 точки. Если точек 0, то задача решена. В противном случае присоединяем точки к ранее образованному контуру так, чтобы фигура осталась многоугольником (можно проводить присоединение, как и в варианте 1).  8  Комментарии к статье  8 8  Обсудить в чате