查找凸多边形的最大 y 坐标

Question

我有一个数组V[1,2,....,n]，其中数组的每个元素以坐标对 (x,y) 的形式表示凸多边形的一个顶点。

设V[1]为x坐标最小的顶点，顶点V[1,2,....,n]按逆时针方向排列，如图。还假定顶点的 x 坐标都是不同的，顶点的 y 坐标也是如此。

现在，我想找到具有最大 y 坐标值的顶点。我们都知道朴素的 O(n) 方法，但是否有可能在 O(log(n)) 中找到它？

我利用V[1]是x坐标最小的顶点的信息，在O(log(n))时间内找到了x坐标最大的顶点。但是有可能做到最大 y 坐标吗？

感谢您的帮助！

Answer 1

您可以按照 here.

中所述使用二进制搜索找到任何方向的极值点

基本思想是检查端点和中点处的向量，并以此来确定要扩展的部分。

Answer 2

因为多边形是凸的，连续点之间的矢量角度从 270 度（向下。称之为 -90 度）到 0（右）、90（上）、180（左）等单调增加., 当您围绕多边形从一个点移动到下一个点时。

因此可以二分查找大于180度的最小角。到下一个点的向量变为> 180度的点（你的例子中的V[8]）是多边形从向上或向左转向向下的位置，并且该点必须具有最大的Y坐标。

我认为 Peter 链接到的文章说的是同一件事，但对于这样一个简单的想法，要阅读很多文字。

Answer 3

长版

二进制搜索被认为是这里几个地方的解决方案，但它只适用于某些情况。

顶点的分布可以有多种不同的方式。你可以在一个点附近有许多聚集，而在其他地方有一个孤立，你可以有形成抛物线形状的顶点（以你的图表为例，消除顶点 7、8 和 9 作为例子），你可以有一个类似对数的分布（例如只有顶点 1、2、3 和 4)，或者实际上任何其他数量的可能性。在所有这些不同的情况下，局部最大值和最小值的数量和位移都会不同。

很可能您需要结合多种方法来估计分布，然后应用适合分布类型的策略。

让我们试着描述这样一个策略：

首先，请记住，您有一个这样的顶点数组，按照逆时针旋转的严格顺序排列。这很重要，也是所有进一步假设和推理的基础。

观察V[n]的行为。如果 V[n] 的 y 坐标 V[n].y 小于 V[1] 或 V[n].y < V[1].y 的坐标，您可以得出结论，所有其他顶点 V[2, n-1] 也必须具有 y-坐标低于 V[1]（考虑为什么一定是这种情况）。因此 V[1] 具有最大的 y 坐标。

现在，此分析的其余部分将要求我们更改多边形的概念模型以简化其表示，从而简化我们要解决的问题。不是绘制点 (V[i].x, V[i].y) 来获得多边形的形状，而是绘制 (i, V[i].y) 来表示想象的连续函数 f(i) = V[i].y。我们问题的解决方案现在是找到函数 f(i) = V[i].y.

的全局最大值的解决方案

考虑到这一点，对于 V[n].y > V[1].y 的所有其他情况，我们必须执行二进制搜索，但我们有两种可能的情况需要考虑：

V[2] 的 y 坐标小于 V[1]。
V[2] 的 y 坐标大于 V[1]。

这很重要，因为情况 1 告诉我们 V[1] 不是不是局部最小值，而情况 2 告诉我们 V[1] 是局部最小值（再次考虑为什么一定是这种情况）。

情况 2 是一个不错的简单情况，因为 V[1] 是局部最小值。这意味着在 V[n] 处只能有一个额外的局部最小值，或者根本没有其他局部最小值。因此，我们可以执行二进制或类似二进制的搜索，以便我们逐渐收敛于曲线上唯一的局部最大值。

您的图表是情况 1 的示例，这是较难的情况。 V[1] 不是局部最小值，因此它是局部最大值。更重要的是，您有两个可能的局部最大值，它们位于 V[1] 和 V[n-k]，其中 n-k > 1。为了帮助可视化，如果绘制函数 f(i) = V[i].y 的点，您将看到抛物线形状或正弦曲线形状。因此，V[n-k] 处的第二个局部最大值要么是抛物线的最右端，要么是正弦曲线的峰值。

（注意：本段是一个可选的优化步骤。）让我们考虑如何确定我们正在处理的局部最大值类型：如果V[n]有y 坐标大于 V[n-1]，则 V[n] 必须是第二个局部最大值（再次考虑为什么这一定是真的）事实上我们可以立即确定 V[n] 具有最大y 坐标。否则，存在一些 k 使得 V[n-k] 是我们的局部最大值，这意味着我们需要执行搜索。

现在只剩下我们考虑如何进行搜索，以避免无意中收敛到 V[1]（我们需要找到一个局部最大值，因为 V[1] 是一个局部最大值我们可能不小心会聚在它上面）。

使用以下约束执行二进制搜索：

对于给定的 V[i]，如果 V[i].y < V[1].y 则向 V[n] 收敛。
如果V[i].y > V[1].y则收敛于增加y的方向（只需比较V[i]与V[i-1]和V[i+1]）。

这应该允许您安全地收敛到最右边的局部最大值并在 log(n) 时间内隔离该值。

现在我们已经介绍了 V[1].y < V[n].y 的两种不同情况，让我们注意这种受约束的二分搜索在情况 2 中的工作方式与在情况 1 中一样准确。因此我们可以概括通过遵循对这两种情况的约束二分搜索规则来搜索情况 1 和情况 2。这显着降低了算法的复杂性。

总而言之，对于任何一般情况，您应该能够达到 O(log n) 时间，还有一些 O(1) 边缘情况。

总结

这个问题背后的诀窍是解构多边形的概念，绘制点 (i, V[i].y) 而不是 (V[i].x, V[i].y)，并将这些点想象成连续函数。那么这个问题的解就变成了问题"what is the global maximum of f(i) = V[i].y?"的解。由于凸多边形的属性和顶点的排序方式，我们可以确定 V[1] 绝对是局部最大值。考虑到这一点，V[1] 要么是全局最大值，要么不是，这是我们可以在一开始就在常数时间内确定的。如果它不是全局最大值，那么我们可以执行约束二分搜索，防止我们在 V[1] 上收敛，从而允许我们在对数时间内确定全局最大值。如果我们觉得更复杂，我们还可以确定 V[n] 是否是常数时间内的全局最大值，作为额外的优化步骤。

精简版

当V[1].y > V[n].y时，最大值为V[1].y。您的解决方案应仅在 V[1].y < V[n].y 的情况下使用二进制搜索。给定一个任意的 V[i]:

这个二进制搜索必须遵守以下约束

基本情况：如果V[1].y > V[i].y，收敛于V[n]的方向。
标准情况：如果V[i].y < V[i+1].y，向V[n]的方向收敛； else if V[i].y < v[i-1].y，向V[1]的方向收敛；否则 V[i].y 是最大值。

对于 V[1].y < V[n].y 和 V[n].y > V[n-1].y 的边缘情况，还有一个可选的优化可以执行。可以安全地跳过此优化，并可以简化解决方案的概念化和实施。

对应算法的伪代码如下：

优化解决方案

如果V[1].y > V[n].y，那么V[1].y就是最大值。

如果V[1].y < V[n].y和V[n].y > V[n-1].y，则V[n].y是最大值。

如果V[1].y < V[n].y和V[n].y < V[n-1].y，则执行约束二分查找。

此策略有两个 O(1) 边缘案例和一个标准 O(log n) 案例。

没有优化的解决方案

如果V[1].y > V[n].y，那么V[1].y就是最大值。

如果V[1].y < V[n].y，则执行约束二分查找。

此策略有一个 O(1) 边缘案例和一个标准 O(log n) 案例。

Answer 4

令 V[m] 为具有最大 y 坐标的顶点。

要考虑的最简单的情况是 m=1，当 V[2].y < V[1].y > v[n].y。由于排除这种情况会使后续推理更简单，我们将假设对这种情况进行了初步检查。

考虑以 V[i] 为原点的边 E[i]，其中 1<i<=n。鉴于所有 x 和 y 坐标都不同的约束，E[i] 必须位于 4 个平面象限之一：

鉴于我们已经排除了 m=i=1 的情况，对于位于象限 I、II 或 IV 的 E[i]，它必须是 m>i 的情况。如果 E[i] 位于象限 III，则 m=i（如果 V[i].y > V[i-1].y 为真）或 m<i。

我们可以使用这个推理作为二进制搜索的基础，在每次迭代中我们执行：

if E[i] lies in Quadrant III
   if V[i].y > V[i-1].y then m=i
   else consider left half
else
   consider right half

这里有一些 Java 代码来说明：

static Point maxY(Point[] v)
{       
    // check for max at origin
    if(v[1].y < v[0].y && v[v.length-1].y < v[0].y)
    {
        return v[0];
    }

    int left = 0; 
    int right = v.length-1;     
    Point maxY = null;
    while(left <= right)
    {
        int mid = left + (right-left)/2;
        if(v[(mid+1)%v.length].y < v[mid].y && v[(mid+1)%v.length].x < v[mid].x)
        {
            // Quadrant III
            if(v[mid].y > v[mid-1].y) 
            {
                maxY = v[mid];
                break;
            }
            right = mid - 1;
        }
        else 
        {
            left = mid + 1;
        }
    }
    return maxY;
}

以及一些简单的测试用例：

public static void main(String[] args)
{
    Point[][] tests = {
            {new Point(0, 10), new Point(10, 0), new Point(9, 5)},
            {new Point(0, 0), new Point(9, 5), new Point(10, 10)},
            {new Point(0, 0), new Point(10, 10), new Point(5, 8)},
            {new Point(0, 5), new Point(9, 0), new Point(10, 10)},
            {new Point(0, 5), new Point(6,0), new Point(10, 6), new Point(5,10)}};

    for(Point[] coords : tests) 
        System.out.println(maxY(coords) + " : " + Arrays.toString(coords));
}

输出：

(0, 10) : [(0, 10), (10, 0), (9, 5)]
(10, 10) : [(0, 0), (9, 5), (10, 10)]
(10, 10) : [(0, 0), (10, 10), (5, 8)]
(10, 10) : [(0, 5), (9, 0), (10, 10)]
(5, 10) : [(0, 5), (6, 0), (10, 6), (5, 10)]

查找凸多边形的最大 y 坐标

Find max y coordinate of a convex polygon

algorithm

geometry

max

convex

convex-polygon