Нарисуйте выпуклый корпус, используя заданные точки в Java / Android

Question

У меня есть несколько 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 и рисую линии от одной к другой точке и, наконец, от последней к первой точке.

Есть ли для этого какой-либо алгоритм или код?

спасибо !!

Answer 1

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

Answer 2

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

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