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

本文关键字：边界 二维 坐标 计算 | 更新日期: 2023-09-27 18:21:50

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

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

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

最简单的解决方案，我认为你最可能寻找的解决方案是计算轴对齐的边界框，这只是找到最小/最大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个向量）。

一种可能但简单的方法是：

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));
}

当然，这是假设你正在寻找一个垂直和水平对齐的矩形。因此，如果你正在寻找尽可能小的矩形，无论它如何旋转，这都不适合你。

在http://www.ceometric.com/products/g.html

它有最小的面积和最小的周长包围矩形，也有最小的包围圆。

相关文章：