Calculate Minimum Bounding Rectangle Of 2D Shape By Coordinates

Question

I have a solution that uses spatial data to represent a cluster of points on a map. I have the need to used the coordinates that represent the extents of a cluster to find the minimum bounding rectangle that can contain said cluster of points.

Does any simple algorithm exist to be able to calculate this or is there any built in functionality in C# to achieve this. I am aware of the NetTopologySuite but am not sure how/if I could use this to achieve the same goal. I have a list of coordinates so I would need to pass this list of strings into it and get the MBR out.

Answer 1

The easiest solution, and I assume the one you're most likely to be looking for, is to calculate the axis-aligned bounding box, which is simply a case of finding the min/max x & y values, then constructing a box from those.

I'll give you pseudo-code for that, given that you haven't posted the types that your geometry is expressed in...

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

So given these:

point[] points = [[x = -2, y = 0], [x = 1, y = 2], [x = 1, y = 1], [x = -1, y = -2]];
box bounds = bounding_box(points);

All of the following will be true:

bounds.topleft == [x = -2, y = 2];
bounds.topright == [x = 1, y = 2];
bounds.bottomleft == [x = -2, y = -2];
bounds.bottomright == [x = -1, y = -2];

Of course, if the coordinate system has the lowest coordinates at the top (e.g. like a typical display) - then you have to invert the calculation; or calculate the result in object-space first and then translate to logical space afterwards.

Notice I've gone for a type for the box that expresses all four corners, in case you decide in the future to update to an arbitrarily aligned box in the future (although by the same token you could just use a point + 2 vectors for that).

Answer 2

One possible, though simple, way to do it could be like this:

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

This does of course assume that you're looking for a rectangle that is aligned vertically and horizontally. So if you're looking for the smallest possible rectangle, no matter how it is rotated, this is not for you.

Answer 3

Try G# at http://www.ceometric.com/products/g.html

It has minimum area and minimum perimeter enclosing rectangles and also minimum enclosing circles.