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

Question

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

是否存在任何简单的算法来计算这个，或者 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 个向量)。