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.

Mcdaniel

Unfortunately I have no idea where to begin with this problem. I am at the stage where I have my coordinates in a list of type string and am unsure as to how to move on from here. – Mcdaniel

@Well you have two types: the axis-aligned bounding box; which is found simply by finding the min x/y and max x/y. Or you have the arbitrarily oriented bounding box which is more complicated (en.wikipedia.org/wiki/Minimum_bounding_box_algorithms). This is made more complicated if you need to take into account the curvature of the earth (which I hope you don't), although technically you're still drawing a box, but it's actually a section of the surface of a sphere instead (probably too much for what you need) – Hargreaves

I see. I need a function that will supply 4 coordinates for the box. So the two X values and the two Y values. Would you suggest that the best way to do it would be to split my coordinates and then compare them all to find the lowest X value and the minimum Y value? If I was to do that then I assume I would only get a minX value and a maxY value? From those two figures is it possible to calculate the other X and Y values? Sorry if I seem a bit lost. Spatial is not my area at all. – Mcdaniel

Currently I dont have to consider curvature as I am using the british national grid srid but it may become a requirement over time but for now I just want to get a working function and can then move on from there. – Mcdaniel

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).

Hargreaves

That looks exactly what I am after. Thanks. – Mcdaniel

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.

Cognizance

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.

Backdate