时间戳

首页 > 解决方案 > 由向量构建的多边形 - 找到最大的区域，需要有序的顶点列表

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

问题描述

描述

该程序需要一个二维向量列表，比如 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 是前一条线的终点（我们只是关闭多边形链）

背景

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

概括

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

标签： algorithmvectorgeometrypolygonarea

解决方案

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

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

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

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

这会让你感动吗？

推荐阅读