查找凸包的最小邊界框

假設我有一個雙凸包，現在我該如何獲得所述凸包的右/左上/下角，現在我們假設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中介紹的參考資料。