Полигон, построенный по векторам - найти самую большую площадь, нужен упорядоченный список вершин

Question

Описание

Программа принимает список двухмерных векторов, скажем, A, B, C .. и так далее.Одна перестановка этих векторов описывает многоугольник следующим образом:

1. Начальная точка a = (0,0)
2. Мы берем первый вектор (A) и строим линию [a; b] где b = a + A
3. Мы берем следующий вектор (B) и строим линию [b; c], где c = b + B
4. .. и т. д.пока у нас нет векторов
5. Мы строим линию [z; a], где z - точка конца предыдущей строки (мы просто закрываем многоугольную цепочку)

Фон

Как правило, вся программа должна найти перестановку входного списка векторов, который описывает многоугольник с наибольшей площадью.Проблема в том, что упомянутые выше линии могут пересекаться.Кроме того, я выбрал формулу Shoelace (формула Гаусса), чтобы вычислить области, для чего требуется список упорядоченных вершин.Но я могу выбрать другой метод, если это необходимо.

Резюме

Итак, мне нужен алгоритм, который находит все вершины построенного многоугольника (с учетом пересечений) и упорядочивает его в правильном порядке для шнурка.формула или мне нужно другое решение.

Answer 1

1. Добавление вектора является коммутативным и ассоциативным.Таким образом, вы закончите в той же точке, независимо от того, в каком порядке вы расположите свои векторы.

   closure_vec = (0,0) - сумма (vector_list)

2. Вам не нужно беспокоиться о перекрестках.Всегда будет хотя бы один порядок выпуклых векторов - он не имеет пересечений.Один из этих заказов будет иметь максимальную площадь.Когда у вас есть выбор расположения, выпуклый многоугольник будет иметь большую площадь, чем аналогичный с пересечением.

3. I думаю , что вы можете построить максимальныйПолигон довольно прост: отсортировать векторы по заголовку (тета, в полярных координатах).Используйте их в таком порядке;результат выпуклый и максимальный.

Это заставляет вас двигаться?