Fak*_*ken 9 computational-geometry
可能重复:
如何在蛮力搜索之外找到凸包中的最大三角形
我有一组随机点,我想从中找到最大的三角形区域,其中每个点都在其中一个点上.
到目前为止,我已经发现最大三角形的顶点将只位于点云(或凸包)的外部点上,所以我编写了一个函数来做到这一点(在nlogn时间使用格雷厄姆扫描).
然而,这就是我被困住的地方.我能弄清楚如何从这些点找到最大三角形的唯一方法是在n ^ 3时使用蛮力,这在平均情况下仍然是可接受的,因为凸壳算法通常会踢出绝大多数点.然而,在最坏的情况下,点在圆上,这种方法会失败.
任何人都知道算法更有效地做到这一点？
注意:我知道CGAL在那里有这个算法,但他们没有详细说明它是如何完成的.我不想使用库,我想学习它并自己编程(并且还允许我将其调整到我希望它操作的方式,就像graham扫描,其中其他实现获取共线点我不想要).
在我的脑海中，也许你可以做一些涉及将点的集合网格化/分成组的事情？也许...将点分成三组（不过，不确定在这种情况下最好的方法是什么），做一些事情来丢弃每组中比其他点更接近其他两组的点同一组，然后使用剩余的点找到每组中有一个顶点的最大三角形？这实际上会使所有点都在一个圆上的情况变得更加简单，因为您只需关注每个组中包含的圆弧中心附近的点，因为这些点将是每个组中距圆弧最远的点另外两组。
不过，我不确定这是否能为您提供某些三角形/点分布的正确结果。在某些情况下，生成的三角形可能不是最佳面积，因为分组和/或顶点选择不是最佳的。类似的事情。
无论如何，这些是我对这个问题的想法。我希望我至少能够为您提供有关如何开展工作的想法。