从一组点中找到最大的三角形

Question

可能重复：如何查找凸包中除暴力搜索以外的最大三角形 我有一组随机点，希望找到一个由这些点构成且面积最大的三角形，其中每个顶点位于其中一个点上。

到目前为止，我已经发现最大三角形的顶点只会位于点云（或凸包）的外部点上，因此我编写了一个使用Graham扫描在nlogn时间内执行此操作的函数。

然而，这就是我卡住的地方。我唯一能想出来的从这些点中找到最大三角形的方法是采用n ^ 3时间的暴力搜索，虽然在平均情况下凸包算法通常会排除绝大多数点，但仍是可以接受的。然而，在最坏情况下，也就是点在圆上的情况下，这种方法将失败。

是否有人知道更有效的算法来执行此操作？

注意：我知道CGAL有此算法，但他们没有详细说明它的实现方式。我不想使用库，我想要学习并自己编写代码（还允许我微调它的操作方式，就像Graham扫描一样，在其中其他实现会捕捉到我不想要的共线点）。

- Faken

---

@Faken：源代码没有说明CGAL::maximum_area_inscribed_k_gon_2使用了什么算法。但你可能想看一下它（http://www.cgal.org/Manual/latest/include/CGAL/extremal_polygon_2.h），看看是否可以重构逻辑。 - andand

@andand：嗯，我是一名机械工程师，所以看专业程序员的代码就像翻译法语一样...无论如何，感谢您提供的起点，我会看看能做些什么。 - Faken

这是一个完全重复的问题，与 https://dev59.com/13I-5IYBdhLWcg3w487k 相同。接受的答案提供了清晰明了的 O(n) 解决方案。 - andand

@andand：我也曾经想过类似的方法，但很快就放弃了，因为我无法证明它总是能得到最大的三角形（更糟糕的是，我还以为自己有反例，但实际上没有在纸上测试）。这个想法非常简单，感谢你指出来，给了我另一个探索的方向，但说实话，我仍然有些怀疑，O(n)时间？听起来太美好了。 - Faken

@Faken：在计算凸包之后，它是O(n)的，因此在您的情况下是O(nlogn)。 - Aryabhatta

Answer 1

不知道这是否有帮助，但如果您从凸包中选择两个点，并旋转凸包的所有点，使得这两个点的连接线与x轴平行，那么具有最大或最小y坐标的点将与首先选择的两个点一起形成最大面积的三角形。

当然，一旦您已经测试了一个点的所有可能基线，就可以将其从列表中删除。

- Landei

Answer 2

从我的经验来看，也许你可以考虑将点的集合分成几组并进行网格化/分割。也许...将这些点分成三组（不确定在这种情况下最好的方法是什么），对每组中那些距离同一组中其他点比距离另外两组更近的点进行处理，然后使用剩余的点找到一个最大的三角形，使得每个顶点都在不同的组中？这实际上会使所有点都在圆上的情况变得简单得多，因为你只需要关注每个组内包含的弧的中心附近的点，因为这些点是每个组中距离其他两个组最远的点。

但我不确定这是否会给出某些三角形/点分布的正确结果。可能存在由于分组和/或顶点选择不够优化而导致结果三角形面积不是最优的情况。类似这样的情况。

总之，这些是我对这个问题的想法。我希望我至少能够给你提供解决问题的思路。

- JAB

Answer 3

关于如何将其降至O(n² log n)的想法。我对计算几何一无所知，因此我将其标记为社区维基；请随意改进。

通过找到每个点上线段斜率的范围，使得集合完全位于线段的一侧，来预处理凸包。然后反转这种关系：使用叶节点中带有点的斜率构建斜率区间树，这样当查询斜率时，您可以找到那些存在切线的点。

如果凸包上没有三个或更多共线点的集合，则每个斜率最多有四个点（两个在每侧），但在共线点的情况下，我们可以忽略中间点。

现在，遍历凸包上所有点对(P,Q)。我们要找到点R，使得三角形PQR具有最大面积。以PQ为三角形的底边，我们要通过尽可能远离线段PQ来最大化高度。通过与PQ平行的线穿过R，必须使所有点都位于该线的一侧，因此我们可以使用预构建的区间树在O(log n)的时间内找到有限数量的候选项。

为了在实践中进一步改进，可以在点对集合中使用分支定界法：找到任何三角形高度的上界（例如两点之间的最大距离），并且丢弃任何距离乘以此上界小于迄今为止发现的最大三角形的距离的点对。

- Jouni K. Seppänen

---

我对计算几何一无所知，所以我会将它标记为社区维基。既然我们处于同样的境地，我想我也会将我的标记为 CW。 - JAB

我不知道为什么你把它标记为社区维基，任何有用的东西都可以被视为实际答案的基础。 - Faken

Answer 4

我认为旋转卡尺算法在这里可能适用。

- lhf

---

我在研究中遇到了这个问题，但只是匆匆一瞥。乍一看，我并不太明白它是如何工作的，你对此有什么想法？ - Faken

使用计算直径的相同算法：对于每个凸包边缘，距离它最远的点定义了以该边为底的最大三角形。旋转一次并找到整体最大的三角形。但这并不是一个证明... - lhf

这样计算的时间复杂度为n^2。有了显著的改进。不幸的是，最大的三角形没有保证会在外壳上有一个边缘。例如，取6个形成完美六边形的点。 - Faken

Answer 5

从凸包中逐个删除点如何？从凸包开始，计算由相邻三个点（p1p2p3、p2p3p4等）形成的三角形的面积。找到面积最小的三角形，然后删除形成该三角形的三个点中间的那个点。（换句话说，如果最小面积三角形是p3p4p5，则删除P4。）现在你有一个具有N-1个点的凸多边形。重复相同的过程，直到只剩下三个点。这应该需要O(N^2)时间。

我不会感到惊讶，如果有一些病态情况，这种方法可能不起作用，但我预计它将适用于大多数情况。（换句话说，我没有证明这一点，也没有引用任何来源。）

- John

---

嗯，我不认为那是正确的。考虑一个完美的六边形。我们知道其中最大的三角形将连接每个其他点。所述算法首先会通过移除一个点（无论哪个点，它们都是相同的）来开始。我们剩下了5个点。如果该算法删除点左侧或右侧两个点的下一个点，则会产生正确的答案。然而，如果它删除与已删除点相对的点，则会产生错误的答案。尽管如此，你的尝试让我思考许多。 - Faken