Блог

У меня есть несколько заданных 2D-точек, и я хочу нарисовать многоугольник, используя эти точки. Этот многоугольник должен проходить через все заданные точки, что означает, что нет такой точки, которая находится внутри или снаружи многоугольника.

Например: если у меня есть точки, подобные: (0,0), (1,1), (-1,-1),(-1,1) и (1,-1), и если я хочу нарисовать многоугольник, используя их, то мой массив точек должен быть отсортирован следующим образом:

(1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (0,0) -> (1,1) ИЛИ

(1,1) -> (0,0) -> (-1,1) -> (-1,-1) -> (1,-1) -> (1,1)

но это не может быть:

(1,1) -> (0,0) -> (-1,-1) -> (-1,1) -> (-1,1) -> (1,-1) -> (1,1)

Для рисования многоугольника я использую функцию DrawLine и рисую линии от одной к другой точке и, наконец, от последней к первой точке.

Существует ли какой-либо алгоритм или код, доступный для этого?

Спасибо!!

Быстрый поиск в Google: алгоритмы выпуклой оболочки, и вот реализация Java.

РЕДАКТИРОВАТЬ: перечитал ваш вопрос и понял, что это не то, что вы хотели. Название «Выпуклая оболочка» может ввести в заблуждение…

Я думаю, что ваша проблема не так тривиальна, как кажется. ИМХО, это особая форма задачи коммивояжера, но без пересекающихся путей.