由 n 个点组成的包围矩形的最小面积
use*_*009 5 algorithm geometry convex-hull computational-geometry
我想找到 n 个点集的最小外接矩形。首先我找到了凸包。如果我有一个来自点集的凸包（我通过格雷厄姆扫描得到它）存储为排序列表。通过二分搜索，我从凸包的每条边找到了距离最远的点。现在有了最大距离的一个边缘和点，我怎样才能找到其余的 2 个点，以便我可以制作一个矩形。我知道该凸包的至少两个极值点必须位于最小外接矩形（Xmin，Xmax，Ymin，Ymax）上。我该如何使用它？是否需要位于多边形的边缘，有什么办法可以做到这一点？我这样做的原因是我需要 O(nlogn) 时间复杂度。感谢您的每一次帮助。
例子：
在此示例中，我们在矩形上有 Xmin 和 Ymax，但没有 Xmin 或 X max