:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Разное » Найти ломаную без самопересечений
  Найти порядок, в котором можно соединить N точек, чтобы получился N-угольник (те не было бы пересечений сторон)



Рассмотрим два из возможных алгоритмов.

Вариант 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).