如何在 c++ 中找到任意方向的最小边界框
假设我有一个 N 对正长坐标（点）的列表。
如何找到包含所有这些的最小矩形？
矩形还可以具有浮动坐标并以任意角度旋转并进一步缩小......不仅仅是X、Y、宽度和高度！
我已经知道如何找到最小的多边形或未旋转的矩形，但是这不是我需要的......我想知道如何找到任意方向的最小边界框。
So let's say I have a list of N pairs of positive long coordinates (points).
How do I find the smallest rectangle containing all of them?
The rectangle can also have floating coordinates and be rotated in any angle and further shrunk... Not just X, Y, Width and Height!
I already know how to find the smallest polygon or not rotated rectangle, but it's not what I need...I wish to know how to find the arbitrarily oriented minimum bounding box.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
请参阅 http://www.geometrictools.com/Source/ComputationalGeometry.html
部分“最小面积盒子”有各种例子。
例如
https://www.geometrictools.com/Samples/Geometrics.html#MinimumAreaBox2D
https://www.geometrictools.com/GTE/Mathematics/MinimumAreaBox2.h
See http://www.geometrictools.com/Source/ComputationalGeometry.html
The section "Minimum-area box" has various examples.
e.g.
https://www.geometrictools.com/Samples/Geometrics.html#MinimumAreaBox2D
https://www.geometrictools.com/GTE/Mathematics/MinimumAreaBox2.h
这个维基百科页面指出，您可以通过使用最小矩形必须具有一个事实来解决此问题边缘与凸包的边缘之一共线。
This wikipedia page notes that you can solve this problem by using the fact that the minimum rectangle must have an edge collinear with one of the edges of the convex hull.
也许这篇论文可以提供帮助：任意方向的最小 k 点包围矩形
Maybe this paper can help: Smallest k point enclosing rectangle of arbitrary orientation
我不知道这对你是否有帮助，但这是我对如何解决这个问题的想法。
您需要函数来找到“最角落”的点（在您的示例中，左边 2 个点和右边 2 个点）。给定这 4 个点，用线将它们连接起来。
（请注意，在您的示例图像中，生成的矩形不会包含顶点，所以......）
然后，您需要一个函数来确定生成的矩形是否包含所有给定点；如果不是，则将端点（在本例中为生成的矩形的顶部 2 个点）扩展 N（这可以是单个度量......比如说一个像素，或者如果您很聪明，则可以是到输出点的距离边界加/减一取决于方向）并重新评估。
I don't know if this would be of help to you, but here's my thoughts on how I'd approach the problem.
You'll need functions to find your "corner-most" points (in your example, the left 2 and right 2 points). Given those 4 points, connect them with lines.
(Note in your example image, the top point would not be contained by the generated rectangle, so...)
You'll then need a function to determine if the rectangle generated contains all given points; if not, extend the endpoints (in this case, the top 2 points of the generated rectangle) by N (which is either a single measure ... say a pixel, or if you're smart, the distance to the point that's out of bounds plus/minus one dependant on the direction) and re-evaluate.
也许这对你有用：
Maybe this works for you: