围绕点拟合矩形 [英] Fit rectangle around points
问题描述
我试图在一组8个2D点周围拟合一个矩形，同时尝试最小化覆盖区域。
示例：
矩形可以缩放和旋转。但是，它需要保留一个矩形。
我的第一种方法是用力对每个可能的旋转进行旋转，使矩形尽可能靠近，并计算覆盖面积。那么最合适的选择就是面积最小的旋转。
但是，这听起来并不是最好的解决方案。
有没有更好的方法？
I不知道您所说的尝试每个可能的旋转是什么意思，因为它们无限多，但是这个基本想法实际上产生了一个非常有效的解决方案：
第一步是计算凸包。实际节省多少取决于数据的分布，但是
那么，让我们做一下数学。边界框区域由 | a，c |给出* | b，d | 。但是 | a，c | 只是投影到矩形方向上的向量（AC）。设 u 为平行于 a 和 c 的向量令 v 为垂直向量。让它们在整个范围内平稳变化。在矢量措辞中，该区域变为（（（AC）.v）/ | v | *（（BD）.u）/ | u | = {（（AC）.v）（（BD）.u）} / {| u | | v |} 。让我们还选择 u =（1，y）。然后 v =（y，-1）。如果 u 是垂直的，这会带来一个涉及限制和无穷大的小问题，所以让我们选择 u 为水平那样的话。为了保持数值稳定性，我们只需在（1，-1）..（（1,1） u 旋转90°。 $ c>。如有需要，可以将区域转换为笛卡尔形式，供读者练习。
I'm trying to fit a rectangle around a set of 8 2D-Points, while trying to minimize the covered area.
Example:
The rectangle may be scaled and rotated. However it needs to stay a rectangle.
My first approach was to brute force each possible rotation, fit the rectangle as close as possible, and calculate the covered area. The best fit would be then the rotation with the lowest area.
However this does not really sound like the best solution.
Is there any better way for doing this?
I don't know what you mean by "try every possible rotation", as there are infinitely many of them, but this basic idea actually yields a very efficient solution:
The first step is to compute the convex hull. How much this actually saves depends on the distribution of your data, but for points picked uniformly from a unit disk, the number of points on the hull is expected to be O(n^1/3). There are a number of ways to do that:
- If the points are already sorted by one of their coordinates, the Graham scan algorithm does that in O(n). For every point in the given order, connect it to the previous two in the hull and then remove every concave point (the only candidate are those neighboring the new point) on the new hull.
- If the points are not sorted, the gift-wrapping algorithm is a simple algorithm that runs at O(n*h). For each point on the hull starting from the leftmost point of the input, check every point to see if it's the next point on the hull.
his the number of points on the hull. - Chen's algorithm promises O(n log h) performance, but I haven't quite explored how it works.
- another simle idea would be to sort the points by their azimuth and then remove the concave ones. However, this only seems like O(n+sort) at first, but I'm afraid it actually isn't.
At this point, checking every angle collected thus far should suffice (as conjenctured by both me and Oliver Charlesworth, and for which Evgeny Kluev offered a gist of a proof). Finally, let me refer to the relevant reference in Lior Kogan's answer.
For each direction, the bounding box is defined by the same four (not necessarily distinct) points for every angle in that interval. For the candidate directions, you will have at least one arbitrary choice to make. Finding these points might seem like an O(h^2) task until you realise that the extremes for the axis-aligned bounding box are the same extremes that you start the merge from, and that consecutive intervals have their extreme points either identical or consecutive. Let us call the extreme points A,B,C,D in the clockwise order, and let the corresponding lines delimiting the bounding box be a,b,c,d.
So, let's do the math. The bounding box area is given by |a,c| * |b,d|. But |a,c| is just the vector (AC) projected onto the rectangle's direction. Let u be a vector parallel to a and c and let v be the perpendicular vector. Let them vary smoothly across the range. In the vector parlance, the area becomes ((AC).v) / |v| * ((BD).u) / |u| = {((AC).v) ((BD).u)} / {|u| |v|}. Let us also choose that u = (1,y). Then v = (y, -1). If u is vertical, this poses a slight problem involving limits and infinities, so let's just choose u to be horizontal in that case instead. For numerical stability, let's just rotate 90° every u that is outside (1,-1)..(1,1). Translating the area to the cartesian form, if desired, is left as an exercise for the reader.
这篇关于围绕点拟合矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
