从一组点的最大四边形

我正在寻找一种方法来找到最大面积的四边形。我已经计算了凸包的点数，并将它们顺时针排序。我试图蛮力，但当然它太慢了。所以，我在这里发现了这个算法的最大的三角形：从一组点的最大四边形

How to find largest triangle in convex hull aside from brute force search

它看起来真的不错，所以我试图改造它。我有一个函数，通过将它分割成两个三角形来计算任何四边形的面积（在这个函数中，我正在对输入点进行排序以确保我正在计算直角三角形）。它是：

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, D)) { 
       C = (C+1)%n; 
       continue; 
      } 
      else break; 
     } 
     if(quadrangleArea(A, B, C, D) <= quadrangleArea(A, (B+1)%n, C, D)) { 
      B = (B+1)%n; 
      continue; 
     } 
     else break; 
     } 
     if(quadrangleArea(A, B, C, D) > quadrangleArea(bestA, bestB, bestC, bestD)) { 
     bestA = A; bestB = B; bestC = C; bestD = D; 
     } 
     A = (A+1)%n; 
     if (A==B) B = (B+1)%n; 
     if (B==C) C = (C+1)%n; 
     if (C==D) D = (D+1)%n; 
     if (A==0) break; 
}

它看起来很好，并为我的简单测试提供良好的结果，但恐怕有些事情是不对的。继续推理，我可以为每个具有n个顶点的多边形制定算法 - 但凭直觉我认为这是不可能的。我对吗？

我正试图解决"SHAMAN"关于spoj的问题，并且我有错误的答案。我99％肯定我的程序的其余部分是可以的，所以上面的代码有些问题。你能帮我改进吗？也许你有一些棘手的测试，可以证明这种算法无法正常工作？我会很感激任何提示！

来源

2013-05-28 conradus

相关：http://stackoverflow.com/questions/16233959/largest-quadrilateral-from-a-set-of-points – finnw

你应该参考引用的Dobkin论文http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4567996。他们对待更高阶的多边形，但似乎无法证明除三角形以外的算法。 – agentp

我会将凸包分成两半，在每一半中找到最大的三角形，计算总和 - 然后在凸包上旋转“分隔线”。就像这样：

size_t n = convexHull.size(); 
size_t A = 0; 
size_t B = n/2; 
size_t C, D; 
size_t maxarea = 0; 
size_t area; 
size_t maxQuad[4]; 

// size_t findLargestTriangle(convHullType c, int& tip); 
// make this search the hull "c" with the assumption 
// that the first and last point in it form the longest 
// possible side, and therefore will be base of the 
// triangle with the largest area. The "other" point 
// will be returned, as will be the size. 
while (A < n/2 && B < n) { 
    // this is partially pseudocode, as you need to treat 
    // the container as "circular list", where indices wrap 
    // around at container.size() - i.e. would have 
    // to be container[n + x] == container[n]. No ordinary 
    // C++ std:: container type behaves like this but it's 
    // not too hard to code this. 
    // This simply says, "two sub-ranges". 
    area = 
     findLargestTriangle(convexHull[A..B], C) + 
     findLargestTriangle(convexHull[B..A], D); 
    if (area > maxarea) { 
     maxarea = area; 
     maxQuad = { A, B, A + C, B + D }; 
    } 
    A++; B++; 
}

我不是一个伟大的数学的人，因此不能完全确定（不能证明），你可以旋转A和B一起这个样子。希望有人能填补这个空白...总是渴望学习我自己;-)

来源

2013-05-28 12:23:39

从一组点的最大四边形

回答

相关问题