通过坐标计算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

它具有最小面积和周长最小包围矩形，并且还最小外接圆。