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

Question

描述

程序接受一个2D向量的列表，比如说A，B，C。诸若此类。这些向量的一个排列以以下方式描述多边形：

1. 的起点是a=(0，0)
2. 我们取第一个矢量(A)并构建一条线a;b b=a+A
3. 我们获取下一个矢量(B)并构建一条线b;c c=b+B
4. ..and依此类推，直到我们超出矢量

<代码>H19我们构建一条线z;a其中z是前一条线的终点(我们只是关闭多边形链)<代码>H210<代码>G211

背景

通常情况下，整个程序需要找到输入向量列表的排列，该排列描述了面积最大的多边形。问题是上面提到的那些线可能会相交。此外，我选择了Shoelace公式(又称高斯面积公式)来计算面积，这需要排序的顶点列表。但如果需要，我可以选择其他方法。

摘要

因此，总的来说，我需要一个算法，既能找到构建多边形的所有顶点(考虑交叉点)，又能按照Shoelace公式的正确顺序进行排序，或者我需要一些其他的解决方案。

Answer 1

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

closure_vec = (0,0) - sum(vector_list)

• You不必担心交集。总会有至少一种向量排序是凸的--它没有交集。其中一个排序将具有最大面积。当你可以选择排列时，一个凸多边形的面积将比一个类似的具有intersection.

• I的多边形大得多，你可以很简单地构造最大的多边形:按方向对矢量进行排序(θ，在极坐标中)。按这个排序顺序使用它们；结果是凸的和最大的。

这能让你行动起来吗？