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

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

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