algorithm - 如何识别周围的矩形

Question

如何识别给定点的近似包围矩形？

预期输出:如下图上半部分所示。

输入:下半部分。

Answer 1

我的建议是执行以下两个步骤:

1. 找到 convex hull的点
2. 找到一个可以在 O(n) 中解决的凸多边形的最小边界框，接下来是 algorithm

已编辑:好的，实际上上述 2 个步骤不足以成为一个正确且被接受的答案。

在这两个步骤之前，您必须先对点集进行预处理。

1. 检查是否有任何3个或更多点共线，删除除两个端点之外的那些点。
2. 在第 1 步之后，您现在应该得到一组没有 3 个或更多点共线的点。

检查集合的大小:如果它只剩下 1 点或 2 点，你必须特殊处理它们(对于 1 点，你可以通过你自己的方法找到任何最小的盒子来包含它；对于 2 点，可能使它们成为边界框的对角线？)

如果结果集还剩下 >= 3 个点，那么就按照我原来的 2 个步骤:凸包 + 旋转卡尺

干杯。