最大周长边框为一组点 [英] Maximum-perimeter bounding rectangle for a set of points

问题描述

我一直在挣扎了很长一段时间这个看似简单的问题。我给出一组点（我还进一步简化为一个凸包）和我的任务是找到一个矩形（不一定轴线对齐），它包括他们所有的人，大约有没有多余的空间（所以它是紧身周围点），并有可能的最大周长。这是没有问题，我找到最小的一个，但是这已经被证明是一个难啃的骨头。当搜索的最小边界矩形，我能够使用的假设是矩形的一侧总是与船体的一侧对齐的，但在这里我没有看到任何这样的情况下在这里。我失去了一些东西非常明显？我能想出到目前为止的唯一方法是测试对跖点对，如果他们能投影到矩形的边，并使用一些触发发挥最大的功用，但我只是失去了我自己的计算。

I've been struggling for quite a while with this seemingly simple problem. I am given a set of points (which I have further simplified down to a convex hull) and my task is to find a rectangle (not necessarily axis-aligned) that encompasses all of them, has no extra space around (so that it is tight-fitting around the points) and has the maximum possible perimeter. It was no trouble for me to find the minimal one, but this has proven to be a tougher nut to crack. When searching for the minimal bounding rectangle, I was able to use the assumption that one of the rectangle's sides was always aligned with one of the hull's sides, but here I don't see any such case here. Am I missing something painfully obvious? The only way I could come up so far is to test antipodal pairs of points if they can project onto the sides of the rectangle and use some trig to maximize the function, but I just lost myself in the calculations.

在此先感谢！

推荐答案

首先，计算你点集的凸包。

First, compute the convex hull of your point set.

现在，想想周围旋转的多边形和计算最小的封闭轴对齐矩形。注意，顶部点，左边点，右点，和底点将从一个顶点继续顺时针围绕凸包到下一个。

Now, think about spinning the polygon around and computing the smallest enclosing axis-aligned rectangle. Notice that the top point, the left point, the right point, and the bottom point will proceed clockwise around the convex hull from one vertex to the next.

您不能想尽一切可能的角度明确。你可以，但是，做一个扫描线的把戏。给定的角度，不过，可以旋转多边形由该角度以及所述第一顶端的，左边，底部，和右边的点，你继续旋转以改变身份后计算的顶部，左边，底部，和右边点多边形。所以，你得到一个角度范围为当前您的顶级选择，左，底部和右侧是正确的;另外，你知道的下一步的正确选择顶部，左，下，右为。

You can't try every possible angle explicitly. You can, however, do a sweep-line trick. Given an angle, though, you can compute the top, left, bottom, and right points after spinning the polygon by that angle as well as the first of the top, left, bottom, and right points to change identity as you continue rotating the polygon. So you get a range of angles for which your current choices of top, left, bottom, and right are correct; further, you know what the next correct choice of top, left, bottom, and right is.

对于每一个合法的选择外，左，下，右，你拉闸不必计算* SIN（THETA）+ B * COS（THETA）固定a和b的最大值超过theta的一定范围内。从trig的记得，*罪（THETA）+ B * COS（THETA）=开方（一^ 2 + B ^ 2）COS（THETA - 反正切（B / A））。您评估功能，在您的区间边界，那里的导数为零（在反正切（B / A）加上任何整数倍PI），你是金色的。

For each legitimate choice of top, left, bottom, and right, You wind up having to compute the maximum value of a*sin(theta) + b*cos(theta) for fixed a and b over some range of theta. Recall from trig that a*sin(theta) + b*cos(theta) = sqrt(a^2+b^2) cos(theta - arctan(b/a)). You evaluate the function at the boundaries of your interval and where the derivative is zero (at arctan(b/a) plus any integer times pi) and you're golden.

这篇关于最大周长边框为一组点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！