如何找到在凸包大三角除了蛮力搜索凸包大
给定一个凸多边形，我怎么发现的3点，也就是具有最大面积的三角形。
相关：这是真的，那个三角形的外接圆也将定义多边形的最小外接圆？
解决方案是的，你可以做的比蛮力显著更好。
通过蛮力我假设你的意思是检查点的所有三元组，并挑选一个最大的区域。这将运行在为O（n 3 ）时间，但事实证明，这是可以做到的它不只是为O（n 2 ）但在 O（n）的时间！
首先分拣点/计算的凸包（在为O（n log n）的时间），如果有必要，我们可以假设我们有凸多边形/船体循环排序它们出现在多边形的顺序之分。调用点1，2，3，...，N。让（可变）点A，B和C，开始为1，2，和3分别（在循环顺序）。我们将移动A，B，C，直到农行是最大面积的三角形。 （我们的想法是类似于旋转卡钳的方法中，作为计算的直径（最远的一对）。）
使用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）的时间。
code片段，在Python（翻译到C应该是直接的）：
＃假设点已经被排序，如0 ...（N-1）
A = 0; B = 1; C = 2
BA = A; BB = B;公元前= C＃系统最佳三联点
而真：#LOOP一
而真：#LOOP乙
而区域（A，B，C）＆LT; =面积（A，B，（C + 1）％N）：#LOOPÇ
C =（C + 1）％N
如果区域（A，B，C）＆LT; =面积（A，（B + 1）％N，C）：
B =（B + 1）％N
继续
其他：
打破
如果区域（A，B，C）＆GT;区（BA，BB，BC）：
BA = A; BB = B;公元前= C
A =（A + 1）％N
如果A == B：B =（B + 1）％N
在B == C：C =（C + 1）％N
如果A == 0：突破
此算法证明在多布金与斯奈德的 在一个通用的方法最大化和其中某些几何问题，最大限度地减少 的，FOCS 1979年，和code以上是他们的ALGOL-60 code的直接翻译。道歉的同时，如果断构造;它应该可以把它们转化为简单的while循环。
Given a convex polygon, how do I find the 3 points that define a triangle with the greatest area.
Related: Is it true that the circumcircle of that triangle would also define the minimum bounding circle of the polygon?
解决方案Yes, you can do significantly better than brute-force.
By brute-force I assume you mean checking all triples of points, and picking the one with maximum area. This runs in O(n3) time, but it turns out that it is possible to do it in not just O(n2) but in O(n) time!
By first sorting the points / computing the convex hull (in O(n log n) time) if necessary, we can assume we have the convex polygon/hull with the points cyclically sorted in the order they appear in the polygon. Call the points 1, 2, 3, … , n. Let (variable) points A, B, and C, start as 1, 2, and 3 respectively (in the cyclic order). We will move A, B, C until ABC is the maximum-area triangle. (The idea is similar to the rotating calipers method, as used when computing the diameter (farthest pair).)
With A and B fixed, advance C (e.g. initially, with A=1, B=2, C is advanced through C=3, C=4, …) as long as the area of the triangle increases, i.e., as long as Area(A,B,C) ≤ Area(A,B,C+1). This point C will be the one that maximizes Area(ABC) for those fixed A and B. (In other words, the function Area(ABC) is unimodal as a function of C.)
Next, advance B (without changing A and C) if that increases the area. If so, again advance C as above. Then advance B again if possible, etc. This will give the maximum area triangle with A as one of the vertices. (The part up to here should be easy to prove, and simply doing this separately for each A would give O(n2). But read on.) Now advance A again, if it improves the area, etc. (The correctness of this part is a bit harder to prove, left as an exercise :-))
Although this has three "nested" loops, note that B and C always advance "forward", and they advance at most 2n times in total (similarly A advances at most n times), so the whole thing runs in O(n) time.
Code fragment, in Python (translation to C should be straightforward):
# 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
This algorithm is proved in Dobkin and Snyder, On a general method for maximizing and minimizing among certain geometric problems, FOCS 1979, and the code above is a direct translation of their ALGOL-60 code. Apologies for the while-if-break constructions; it ought to be possible to transform them into simpler while loops.
