给定一个凸多边形，我怎么找了3个点定义与面积最大的三角形。
相关阅读：这是真的，那个三角形的外接圆还要定义多边形的最小边界圈？
Answer 1:
是的，你可以做得比蛮力显著更好。
通过蛮力我假设你的意思是检查点的所有三元组，并挑选一个最大的区域。 这个运行在O（N 3）时间 ，但事实证明，这是可以做到的它不只是为O（n 2），但在O（n）的时间 ！
[ 更新：发表于2017年的论文由实施例表明，为O（n）的解决方案不特定类的多边形的工作。 见这个答案的更多细节。 但是O（N 2）算法仍然是正确的。]
首先分拣点/计算的凸包（在为O（n log n）的时间），如果必要，我们可以假设我们有一个在它们出现在多边形的顺序循环地排序的点的凸多边形/船体。 调用点1，2，3，...，N。 让（变量）的点A，B，和C，开始分别为1，2，和3（在循环顺序）。 我们将移动A，B，C，直到ABC是最大面积的三角形。 （我们的想法是类似于旋转卡钳方法中，作为计算时所使用的直径（最远对） ）。
与A和B固定，推进C作为长为一体的三角形的面积增加，即，只要（例如最初，其中A = 1，B = 2，C通过C = 3，C = 4，...高级）区域（A，B，C）≤区域（A，B，C + 1）。 这点C将是一个，对于那些固定最大化区（ABC）A和B（换句话说，该功能区（ABC）是单峰的为C.的函数）
接着，前进B（不改变A和C）如果增加的区域。 如果是这样，又推进C作为以上。 然后，如果可能的再次前进B，等，这将得到具有A作为顶点之一的最大面积三角形。
（该部分高达这里应该很容易证明的，只是这样做单独为每个A将给出一个O（N 2）算法。）
现在，再次推进，如果它改善了区域，依此类推。 （这部分的正确性是更加微妙：多布金与斯奈德在他们的论文给予了证明，但最近的一篇文章显示了反我没有理解它。）
虽然这有三个“嵌套”的循环，注意，B和C始终走“向前”，而他们最多2n倍于总（同样，一个进步至多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
该算法被证明在多布金和Snyder， 在用于最大化以及某些几何问题中最小化的一般方法 ，1979年FOCS，和上述代码是他们ALGOL-60代码的直接翻译。 道歉的同时，如果断裂构造; 它应该可以把它们转化成简单的while循环。
Answer 2:
在回答你的相关的问题：
三角形的外接圆不一定是多边形的最小外接圆。 看到这一点，考虑一个非常平坦的等腰三角形，说与（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）点。
Answer 3:
根据这个文件，还有一类凸多边形，其中由ShreevatsaR的回答中引用的算法失败的。 该文件还提出了为O（n log n）的分而治之算法求解的问题。
显然，在你移动的点B和C 全部 A简单的O（N 2）算法仍然有效。
Answer 4:
从http://www.wolframalpha.com/input/?i=triangle三角形的面积= SQRT（（A + BC）（A-B + C）（-a + B + C）*（A + B + C））/ 4如果您使用连接到您的凸多边形的结束点C，如果A和b将触动你的凸多边形，你可以遍历周围的多边形允许种植和b缩小，直到你找到你的最大面积。 我将开始中点，并尝试每个方向一个更大的区域。
Answer 5:
我知道这是一个老的文章，但通过参考答案上面我能够修改代码以最大限度地为n边形的区域。
注：凸包使用发现Emgu OpenCV库 。 我使用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);
}
文章来源: How to find largest triangle in convex hull aside from brute force search
