寻找凸集内面积最大的等腰三角形（非暴力求解方案）

核心前提 #

凸集内的最大面积等腰三角形，其三个顶点必然位于凸集的凸包上（若顶点在内部，沿对边垂线方向移动到凸包边界时面积只会增大）。因此第一步需将binary mask转换为凸包，大幅减少计算量。

步骤1：从Binary Mask提取凸包 #

1. 提取mask的边缘像素（可通过遍历mask或边缘检测算法实现）。
2. 对边缘点计算凸包，得到按逆时针排序的顶点序列 P = [p₀, p₁, ..., pₙ₋₁]，可使用Graham扫描（O(n log n)）或Jarvis步进算法实现。

步骤2：高效求解算法（非暴力） #

以下三种策略覆盖所有等腰三角形的类型，最终取三者中的最大面积结果：

策略A：两腰相等的等腰三角形（顶点在底边垂直平分线上）

针对顶点C满足 AC=BC 的情况：

• 遍历凸包上的每对顶点 (p_i, p_j) 作为底边AB：
  1. 计算AB的中点M，以及AB的垂直方向向量。
  2. 找到凸包与AB垂直平分线的交点中，距离AB最远的点C（该点在凸集内，且保证AC=BC）。利用凸包的有序性，可通过二分查找快速定位交点，无需遍历所有顶点。
• 优化：使用双指针法替代全量遍历——固定顶点 p_i，递增 p_j 时，最优的C点位置也会单调递增，将时间复杂度从O(n²)降至O(n)。
• 面积计算：用叉积公式 Area = 0.5 * |(B - A) × (C - A)| 避免浮点误差。

策略B：腰与底边相等的等腰三角形（如AB=AC）

针对顶点A满足 AB=AC 的情况：

• 遍历凸包上每个顶点 p_i 作为顶点A：
  1. 对每个A，遍历凸包上的点 p_j 作为B，计算半径 r = |p_i p_j|。
  2. 以A为圆心、r为半径画圆，找到圆与凸包的交点C，使得三角形ABC的面积最大（即C到直线AB的距离最大）。利用凸包的支撑函数，可快速找到垂直于AB方向的支撑点，若该点在圆内则直接取为C，否则计算圆与凸包边的交点。
• 优化：对每个A，用三分法在凸包上寻找最优的B点（面积函数关于B的位置呈单峰特性），将遍历复杂度从O(n)降至O(log n)。

策略C：基于支撑函数的三分法（最优效率）

利用凸集的支撑函数快速定位极值点，结合三分法找到全局最优：

1. 参数化等腰三角形的对称轴方向θ（θ∈[0, π)）。
2. 对每个θ，找到凸集在θ方向的支撑点作为顶角顶点，再找到垂直于θ方向的两个支撑点作为底边端点，计算该等腰三角形的面积。
3. 由于面积函数关于θ是连续单峰的，用三分法遍历θ的取值范围，找到最大面积对应的三角形。

• 时间复杂度：O(log n * log(1/ε))，其中ε为精度要求，是三种策略中效率最高的方案。

复杂度对比 #

• 暴力解法：O(n³)（n为凸包顶点数）
• 策略A（双指针）：O(n)
• 策略B（三分+二分）：O(n log n)
• 策略C（三分+支撑函数）：O(log n * log(1/ε))

内容的提问来源于stack exchange，提问作者Kirill Meisser