寻找凸包的最小外接矩形

Question

寻找凸包的最小外接矩形

3

假设我有一个n边形的凸包，现在如何得到该凸包的右/左上/下角？假设N是3，三角形坐标为0,0 50,0 0,50或其他某些值，我们知道哪些是角落，而且0,50既算作右上角又算作左侧，那么是否有一种方法可以得到这个结果，而不是像我这里一样，其中Left_Bottom等都是向量，values是一个向量数组。

    Left_Bottom = values[0];
    Left_Top = values[0];
    Right_Bottom = values[0];
    Right_Top = values[0];
    for (int i = 1; i < values.length; i++) {
        if (!Left_Bottom.XisLess(values[i])) {
            if (Left_Bottom.YisLess(values[i])) {
                Left_Bottom = values[i];
            }
        }

        if (!Left_Top.XisLess(values[i])) {
            if (!Left_Top.YisLess(values[i])) {
                Left_Top = values[i];
            }
        }

        if (Right_Bottom.XisLess(values[i])) {
            if (Right_Bottom.YisLess(values[i])) {
                Right_Bottom = values[i];
            }
        }

        if (Right_Top.XisLess(values[i])) {
            if (!Right_Top.YisLess(values[i])) {
                Right_Top = values[i];
            }
        }
    }

- Slymodi

你将在什么情况下使用它，即你寻找更好解决方案的原因是什么？此外，“values”向量是什么？仅仅是包含凸包中所有点的向量还是其他东西？ - pingul

此外，您的标题和问题有点不同步；您是想找到所有角落还是只有四个？（上/下/左/右） - pingul

只返回翻译文本：只需返回最极端的四个角，用于2D光照的应用程序，在OpenGL中实现。 - Slymodi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- herohuyongtao · Accepted Answer

如果你正在寻找有限点集的凸包问题，可以参考这里。你可以找到几种O(n*log n)的解决方案。

enter image description here

如果您只是想要这个凸包的边界矩形的四个角，实际上您正在寻找凸包的最小边界框。
- 如果边界框与坐标轴平行，只需在所有凸包点中查找min_x、min_y、max_x和max_y。然后四个角（顺时针方向）为：
  1. (min_x, min_y)
  2. (max_x, min_y)
  3. (max_x, max_y)
  4. (min_x, max_y)

enter image description here

如果边界框不与坐标轴平行，则会变得复杂。请参考这里和这里中介绍的参考资料进行实现。

enter image description here