通过坐标计算二维形状的最小外接矩形

Question

我有一个解决方案，它使用空间数据来表示地图上的一组点。我需要使用表示簇范围的坐标来查找可以包含所述点簇的最小边界矩形。

是否存在能够计算此值的简单算法，或者 C# 中是否有任何内置功能可以实现此目的。我知道 NetTopologySuite，但不确定如何/是否可以使用它来实现相同的目标。我有一个坐标列表，因此我需要将此字符串列表传递到其中并取出 MBR。

Answer 1

最简单的解决方案（我认为您最有可能正在寻找的解决方案）是计算轴对齐边界框，这只是查找最小/最大 x 和 x 的情况。 y 值，然后根据这些值构建一个盒子。

鉴于您还没有发布几何图形所表达的类型，我将为您提供伪代码...

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

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

当然，如果坐标系具有顶部的最低坐标（例如，像典型的显示器一样）-那么您必须反转计算；或者先在对象空间中计算结果，然后再转换到逻辑空间。

请注意，我已经选择了表达所有四个角的框的类型，以防您将来决定更新为任意对齐的框（尽管出于同样的原因，您可以只使用点 + 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尝试 具有最小面积和最小外接矩形以及最小外接圆。