由矢量构建的多边形 - 找到最大的区域，需要有序的顶点列表

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 是上一条线的终点（我们只是关闭多边形链）

背景

一般来说，整个程序都要找到输入向量列表的排列，它描述了面积最大的多边形。 问题是上面提到的那些线可以相交。此外，我选择鞋带公式（又名高斯面积公式）来计算面积，这需要有序的顶点列表。但如果需要，我可以选择其他方法。

总结

所以总的来说，我需要一种算法，既能找到构建多边形的所有顶点（考虑交叉点），又能按照鞋带公式的正确顺序对其进行排序，或者我需要一些其他解决方案。

Answer 1

1. 向量加法是可交换和结合的。因此，无论您排列矢量的顺序如何，您都将在同一点结束。

   closure_vec = (0,0) - 总和(vector_list)

2. 您不必担心交叉路口。总会有至少一种凸向量排序——它没有交集。这些顺序之一将具有最大面积。当您可以选择排列方式时，凸多边形的面积将大于具有交叉点的类似多边形的面积。

3. 我 认为 您可以相当简单地构造最大多边形：按方向（theta，在极坐标中）对向量进行排序。按排序顺序使用它们；结果是凸的和最大的。

这让你感动吗？