通過座標計算2D形狀的最小邊界矩形

Question

我有一個解決方案，它使用空間數據來表示地圖上的一組點。我需要使用表示集羣範圍的座標來查找可以包含所述點集的最小邊界矩形。

是否有任何簡單的算法能夠計算出來，或者是否有C＃中的任何內置功能來實現這一點。我知道NetTopologySuite，但我不知道如何/如果我可以使用它來實現相同的目標。我有一個座標列表，所以我需要將這個字符串列表傳遞給它並獲取MBR。

Answer 1

最簡單的解決方案，我假設您最可能尋找的解決方案是計算軸對齊邊界框，它只是找到最小值/最大值的情況，然後從這些構建一個盒子。

我會給你爲僞代碼，因爲你還沒有公佈於是給了這些，你的幾何形狀在...

type point { float x; float y; } 
type box { point topleft; point topright; point bottomleft; point 

function bounding_box(points) 
{ 
    xmin = min(points.x) 
    xmax = max(points.x) 
    ymin = min(points.y) 
    ymax = max(points.y) 

    return new box{ 
    topleft = { x = xmin, y = ymax }, 
    topright = { x = xmax, y = ymax }, 
    bottomleft = { x = xmin, y = ymin }, 
    bottomright = { x = xmax, y = ymin } 
    }; 
} 

表達的類型：

point[] points = [[x = -2, y = 0], [x = 1, y = 2], [x = 1, y = 1], [x = -1, y = -2]]; 
box bounds = bounding_box(points); 

下面的一切會是真的：

bounds.topleft == [x = -2, y = 2]; 
bounds.topright == [x = 1, y = 2]; 
bounds.bottomleft == [x = -2, y = -2]; 
bounds.bottomright == [x = -1, y = -2]; 

當然，如果座標系具有最低的座標在T op（例如就像一個典型的顯示器） - 那麼你必須反轉計算;或先計算對象空間中的結果，然後再轉換爲邏輯空間。

注意：如果您將來決定更新到未來的任意對齊框，我已經選擇了表示所有四個角的框的類型（儘管出於同樣的原因，您可以使用一個點+ 2個矢量）。

Answer 2

一種可能，雖然簡單，這樣做可能是這樣的：

public Rectangle Test(List<Point> points) 
{ 
    // Add checks here, if necessary, to make sure that points is not null, 
    // and that it contains at least one (or perhaps two?) elements 

    var minX = points.Min(p => p.X); 
    var minY = points.Min(p => p.Y); 
    var maxX = points.Max(p => p.X); 
    var maxY = points.Max(p => p.Y); 

    return new Rectangle(new Point(minX, minY), new Size(maxX-minX, maxY-minY)); 
} 

這並不當然假設你正在尋找的是垂直和水平排列的矩形。所以，如果你正在尋找最小的矩形，不管它如何旋轉，這都不適合你。

Answer 3

嘗試G＃在http://www.ceometric.com/products/g.html

它具有最小面積和周長最小包圍矩形，並且還最小外接圓。