给定一组有序的2D像素位置(相邻或相邻对角线),形成一条没有重复的完整路径,如何确定多边形的最大线性尺寸,其周长是该像素集？(其中GLD是集合中任何一对点的最大线性距离)
就我的目的而言,明显的O(n ^ 2)解决方案对于数千个点的数字可能不够快.是否有良好的启发式或查找方法使时间复杂度更接近O(n)或O(log(n))？
可能重复:
如何在蛮力搜索之外找到凸包中的最大三角形
我有一组随机点,我想从中找到最大的三角形区域,其中每个点都在其中一个点上.
到目前为止,我已经发现最大三角形的顶点将只位于点云(或凸包)的外部点上,所以我编写了一个函数来做到这一点(在nlogn时间使用格雷厄姆扫描).
然而,这就是我被困住的地方.我能弄清楚如何从这些点找到最大三角形的唯一方法是在n ^ 3时使用蛮力,这在平均情况下仍然是可接受的,因为凸壳算法通常会踢出绝大多数点.然而,在最坏的情况下,点在圆上,这种方法会失败.
任何人都知道算法更有效地做到这一点？
注意:我知道CGAL在那里有这个算法,但他们没有详细说明它是如何完成的.我不想使用库,我想学习它并自己编程(并且还允许我将其调整到我希望它操作的方式,就像graham扫描,其中其他实现获取共线点我不想要).
我正在寻找一种方法来找到面积最大的四边形。我已经计算了凸包的点并按顺时针方向对它们进行排序。我尝试过蛮力，但当然它太慢了。所以我在这里找到了最大三角形的算法：
看起来真的很不错，所以我尝试重新制作它。我有一个函数，可以通过将任何四边形划分为两个三角形来计算任何四边形的面积（在这个函数中，我对输入点进行排序，以确保我计算的是直角三角形）。这里是：
int n = convexHull.size();
int A = 0; int B = 1; int C = 2; int D = 3;
int bestA = A; int bestB = B; int bestC = C; int bestD = D;
while(true) { // loop A
while(true) { // loop B
while(true) { // loop C
while(quadrangleArea(A, B, C, D) <= quadrangleArea(A, B, C, (D+1)%n) ) { // loop D
D = (D+1)%n;
}
if(quadrangleArea(A, B, C, D) <= quadrangleArea(A, B, (C+1)%n, …我试图解决 topcoder 领域的练习问题：http://topcoder.bgcoder.com/print.php ?id=417
根据我的理解，问题的目的是找到一个最大面积的 k 边形，给定一组点 D 并且 k<=n，n 是一个固定值。
令 D 的凸包 = C(D)
如果n=3，我已经证明可以通过假设它的顶点是C(D)的子集来构造这样的三角形。因此很容易找到 k=3 的解决方案：/sf/answers/113533941/
但是，对于 n>3，我不知道该怎么做。
这是我尝试的方法：
设|C(D)| = l 即凸包是一个 l 边形，
如果 n > li 我非常确定面积最大的 k 边形将是凸包本身，即 C(D)
如果 n < li 非常确定最大 k 边形的顶点将是 C(D) 的子集，我无法证明 k>3，而且我无法想出一种算法来解决甚至如果这是一个正确的假设。
谁能帮我解决这个问题，我的方法正确吗？你能帮我进一步进行吗？
我在2D平面中给出一组N个点,表示为(x,y)坐标对.什么是选择三个点的快速算法,以便这些点形成的三角形具有最大周长？