找到凸集中面积最大的等腰三角形

Question

我在图像中有一个对象作为二进制掩码。该对象可以描述为凸集。我想找到 3 个点来定义一个 isosceles 三角形（两条相等的边），其最大面积完全包含在凸集内。我特别对“非暴力”方法感兴趣。三角形的三个顶点可以位于凸集内或凸集边上的任意位置。我已经看到一个关于一般三角形的类似问题的答案here。 我尝试过使用暴力方法。

Answer 1

这让我们很好地了解了需要多长时间以及输入的实际大小。您有足够的时间来设计形状周长为 O(n

2

) 的算法，因为：

W x H 图像中凸形的周长最多可为 2WH 像素。

• 形状周长为 O(n
2
• )，因此图像大小为 O(n)。 这就是做涉及整个图像的
任何事情
• 所需的时间，而我们一直在用户交互之后做这类事情。
所以在你的情况下，听起来我会使用像这样的简单图像处理算法：

将点 P1 设置在周边的任意位置，然后逆时针绕着形状走一圈。

1. 对于每个 P1，从 P2 = P3 = P1 开始，然后沿 P3 逆时针方向绕着形状走一圈。
2. 对于每一对 P1、P3，逆时针推进 P2，直至穿过 P1-P3 线段的垂直平分线。现在这 3 个点形成一个等腰三角形，您可以记住面积最大的那个。
由于 P2 的移动速度比 P3 慢，因此在第 3 步中，对于每个 P1、P3 对，P2 平均前进不到 1 个像素，并且该算法总共需要 O(n

2

) 时间，其中 n 是周边的像素。