Математика:
Вычислительная геометрия:
Разное.

N точек на плоскости заданы своими координатами. Найти порядок, в котором можно соединить эти точки, чтобы получился N-угольник (т.е. не было бы пересечений сторон).

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

Вариант 1. Строим выпуклую оболочку данного множества точек (см. задачу 10).

Если все точки множества A лежат на контуре, то задача решена. Если же нет, то ищем точку l с минимальным расстоянием до контура -- пусть это минимальное расстояние до стороны фигуры (u,v) (если таких точек несколько, то берем любую из них), вставляем в контур точку l (вместо контура ... u,v ... будет ... u,l,v, ...).

Для оставшихся точек повторяем описанную выше процедуру, пока последняя не будет вставлена в контур.

Вариант 2. Строим выпуклую оболочку V данного множества точек (см. задачу 10).

Если все точки множества A лежат на контуре, то задача решена. Иначе обозначим через A₁ все внутренние точки выпуклой оболочки V. Строим для нового множества A₁ выпуклую оболочку V₁ (контуры V и V₁ не пересекаются!).

"Склеиваем" два контура:

Выберем по паре последовательных вершин p,s и p₁,s₁ на контурах V и V₁ соответственно так, чтобы в четырехугольнике с вершинами s,p,p₁,s₁ не лежало больше никаких других точек контуров V и V₁. Разрываем контуры V и V₁ (убирая ребра (p,s) и (p₁,s₁)) и объединяем их (добавляя ребра (p,p₁) и (s,s₁)).

Если внутри V₁ нет внутренних точек, то задача решена, иначе же с внутренними точками V₁ проделываем те же самые операции: находим выпуклую оболочку и пары последовательных точек на контурах, разрываем и склеиваем контуры, и т.д., пока не получим, что последняя построенная выпуклая оболочка содержит в себе 0, 1 или 2 точки.

Если точек 0, то задача решена. В противном случае присоединяем точки к ранее образованному контуру так, чтобы фигура осталась многоугольником (можно проводить присоединение, как и в варианте 1).

Вверх по странице, к оглавлению и навигации.