如何在凸壳中除强力搜索外求最大三角形

是的,你可以比蛮力做得更好。

我假设你的意思是检查所有三个点,选择一个最大面积的点。这个跑进 O(n) ^三 时间 但事实证明,它不仅可以在0(n ^二 ) 但在 o(n)时间 !

[ 更新: 2017年发表的一篇论文举例说明,O(N)解决方案不适用于特定类别的多边形。见 this 请回答以了解更多详细信息。但是O(n) ^二 )算法仍然正确。]

通过首先对点进行排序/计算凸壳(在O(n log n)时间内),如果需要,我们可以假设我们有凸多边形/凸壳,这些点按它们在多边形中出现的顺序循环排序。调用点1、2、3、__,n.让(变量)点A、B和C分别以1、2和3开始(循环顺序)。我们将移动a,b,c直到a b c是最大面积三角形。(这个想法与 rotating calipers 方法,在计算 diameter (farthest pair) )

在A和B固定的情况下,只要三角形的面积增加,即只要面积(A、B、C+1)增大,前进C(例如,最初A=1,B=2,C前进C=3,C=4,Ω)。对于固定的A和B,该点C将是最大化面积(a b c)的点。(换句话说,功能区(a b c)是 单峰的 作为c.)的函数

接下来,前进B(不改变A和C),如果这增加了面积。如果是这样,再次按上述步骤推进C。如果可能的话,再向前移动b,这将得到最大面积三角形,其中a是顶点之一。

(到这里的部分应该很容易证明,简单地分别为每个a做这件事会得到一个o(n) ^二 )算法。

现在再次前进A,如果它改善了区域,等等。 _{(这部分的正确性更为微妙:多布金和斯奈德在他们的论文中给出了一个证明,但最近的一篇论文给出了一个反例。我还不明白。)}

虽然这有三个“嵌套”循环,但请注意,B和C总是前进“前进”,它们总共前进最多2n次(类似地,A最多前进N次),所以整个过程在O(n)时间内运行。

代码片段,在python中(到c的转换应该很简单):

 # Assume points have been sorted already, as 0...(n-1)
 A = 0; B = 1; C = 2
 bA= A; bB= B; bC= C #The "best" triple of points
 while True: #loop A

   while True: #loop B
     while area(A, B, C) <= area(A, B, (C+1)%n): #loop C
       C = (C+1)%n
     if area(A, B, C) <= area(A, (B+1)%n, C): 
       B = (B+1)%n
       continue
     else:
       break

   if area(A, B, C) > area(bA, bB, bC):
     bA = A; bB = B; bC = C

   A = (A+1)%n
   if A==B: B = (B+1)%n
   if B==C: C = (C+1)%n
   if A==0: break

该算法在Dobkin和Snyder中得到了验证。 On a general method for maximizing and minimizing among certain geometric problems ,focs 1979,上面的代码是他们的algol-60代码的直接翻译。为while-if-break结构道歉;应该可以将其转换为简单的while循环。

回答您的相关问题:

三角形的外接圆不一定是多边形的最小边界圆。要了解这一点,考虑一个非常平坦的等腰三角形,比如顶点位于(0,0)、(10,0)和(5,1)。最小的边界圆有中心(5,0)和半径5,但是这个圆不接触(5,1)处的顶点,所以它不是外接圆。(圆周有中心(5,-12)和半径13)

编辑:

选择较小的外接圆或包含多边形直径对极点的圆也不够,因为有可能构造具有最大三角形外接圆以外点的多边形。以五角大楼为例,其顶点位于:

(-5,  0)
(-4, -1)
( 5,  0)
( 4,  1)
(-4,  1)

最大三角形的顶点位于(-4,-1)、(5,0)和(-4,1)。它的外接圆不包括点在(-5,0)。

根据 this 本文中,有一类凸多边形,其中什里瓦察的答案所引用的算法失败了。本文还提出了一种求解该问题的O(N对数N)分治算法。

显然,更简单的O(n ^二 )移动点B和C的算法 全部的 A仍然有效。

从 http://www.wolframalpha.com/input/?i=triangle 三角形的面积=sqrt((a+b-c) (aB+C) (-a+b+c)*(a+b+c))/4 如果使用C连接到凸多边形的端点 如果A和B会碰到你的凸多边形 你可以在多边形周围迭代 让A增长,B收缩,直到你找到你的最大面积。 我会从中间点开始,尝试每个方向的面积更大。

我知道这是一篇老文章,但是通过引用 answer above 我可以修改代码来最大化N边多边形的面积。

注:发现凸面船体时使用 Emgu OpenCV library . 我在用 CvInvoke.ContourArea() 方法计算多边形的给定面积。这是用C写的。它还假定这些点是按顺时针顺序排列的。这可以在方法中指定 CvInvoke.ConvexHull() .

private PointF[] GetMaxPolygon(PointF[] convexHull, int vertices)
{
         // validate inputs
        if(convexHull.Length < vertices)
        {
         return convexHull;
        }
        int numVert = vertices;
        // triangles are the smalles polygon with an area.
        if (vertices < 3)
           numVert = 3;        

        PointF[] best = new PointF[numVert]; // store the best found
        PointF[] next = new PointF[numVert];  // test collection of points to compare
        PointF[] current = new PointF[numVert]; // current search location.

        int[] indexes = new int[numVert]; // map from output to convex hull input.
        int[] nextIndices = new int[numVert];

        //starting values 0,1,2,3...n
        for(int i = 0; i < numVert; i++)
        {
            best[i] = convexHull[i];
            next[i] = convexHull[i];
            current[i] = convexHull[i];
        }

        // starting indexes 0,1,2,3... n
        for(int i = 0; i < numVert; i++)
        {
            nextIndices[i] = i;
            indexes[i] = i;                
        }

        //  starting areas are equal.
        double currentArea = GetArea(current);
        double nextArea = currentArea;
        int exitCounter = 0;

        while(true)
        {
            // equivelant to n-1 nested while loops 
            for(int i = numVert - 1; i > 0; i--)
            {
                while (exitCounter < convexHull.Length)
                {
                    // get the latest area
                    currentArea = GetArea(current);
                    nextIndices[i] = (nextIndices[i] + 1) % convexHull.Length;
                    next[i] = convexHull[nextIndices[i]]; // set the test point
                    nextArea = GetArea(next);
                    if (currentArea <= nextArea) // compare.
                    {
                         indexes[i]= (indexes[i]+1) % convexHull.Length;
                         current[i] = convexHull[indexes[i]];
                         currentArea = GetArea(current);
                         exitCounter++; // avoid infinite loop.
                    }
                    else //stop moving that vertex
                    {
                        for(int j = 0; j< numVert; j++)
                        {
                            nextIndices[j] = indexes[j];
                            next[j] = convexHull[indexes[j]];//reset values.

                        }
                        break;
                    }
                }
            }

            // store the best values so far.  these will be the result.
            if(GetArea(current)> GetArea(best))
            {
                for (int j = 0; j < numVert; j++)
                {
                    best[j] = convexHull[indexes[j]];
                }
            }
            // The first index is the counter.  It should traverse 1 time around.
            indexes[0] = (indexes[0] + 1) % convexHull.Length;

            for(int i = 0; i < vertices-1;i++)
            {
                if(indexes[i] == indexes[i+1])// shift if equal.
                {
                    indexes[i + 1] = (indexes[i + 1] + 1) % convexHull.Length;
                }
            }

            //set new values for current and next.
            for(int i = 0; i < numVert; i++)
            {
                current[i] = convexHull[indexes[i]];
                next[i] = convexHull[indexes[i]];
            }

            // means first vertex finished traversing the whole convex hull.
            if (indexes[0] == 0)
                break;


        }
        return best;
}

使用的面积法。这可能会根据最大化所需的内容而改变。

private double GetArea(PointF[] points)
{
    return CvInvoke.ContourArea( new Emgu.CV.Util.VectorOfPointF(points),false);
}