查找凸包的最小边界框

假设我有一个双凸包，现在我该如何获得所述凸包的右/左上/下角，现在我们假设N可能是3，三角形坐标是0,0 50,0 0,50或其他东西，我们知道角落是什么，0,50既是右上角也是左下角，所以有什么方法可以得到这个结果，而不是我在这里得到的结果其中LEFT_BOTTOM等的载体和值是一个矢量阵列查找凸包的最小边界框

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]; 
      } 
     } 
    }

来源

2013-12-22 Slymodi

在什么情况下你会使用这个，即什么是你正在寻找一个更好的解决方案的原因是什么？另外：什么是“价值”矢量？只是一个载体，包含船体中的所有点或其他东西？ – pingul

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

只是四个最极端的角落，对于2D照明的应用，我已经下了，但在opengl – Slymodi

如果你正在寻找查找有限组点的凸包的问题，看看here。你可以找到一些解决方案，为此在为O（n * log n）的

如果你只是寻找边框的四个角这个凸包，实际上你正在寻找最小包围盒为凸包。

如果边界框是平行于坐标轴，只要找到所有这些凸包点之间的min_x，min_y，max_xmax_y和。然后四个角（顺时针）为：

（MIN_X，MIN_Y）

（MAX_X，MIN_Y）

（MAX_X，MAX_Y）

（MIN_X，MAX_Y ）

如果边界框不平行于坐标轴，这变得复杂。请参阅here和here中介绍的参考资料。