c# - 通过坐标计算二维形状的最小边界矩形

Question

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

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

Answer 1

最简单的解决方案，我假设您最有可能正在寻找的解决方案是计算轴对齐的边界框，这只是找到最小/最大 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

在http://www.ceometric.com/products/g.html尝试 G#

它具有最小面积和最小周长包围矩形以及最小包围圆。