حساب الحد الأدنى لمستطيل الحد الأدنى من الشكل 2D عن طريق الإحداثيات

Question

لدي حل يستخدم بيانات مكانية لتمثيل مجموعة من النقاط على الخريطة.لدي الحاجة إلى استخدام الإحداثيات التي تمثل النطاق من مجموعة للعثور على الحد الأدنى من المستطيل المحيط يمكن أن يحتوي على مجموعة من النقاط المذكورة.

هل توجد أي خوارزمية بسيطة لتكون قادرة على حساب هذا أو هل هناك أي وظيفة مدمجة في C # لتحقيق ذلك.أنا أدرك Nettopologysuite لكنني لست متأكدا من كيفية استخدام هذا / إذا استطعت استخدام هذا لتحقيق نفس الهدف.لدي قائمة بالإحداثيات، لذلك سأحتاج إلى اجتياز قائمة السلاسل هذه وتحصل على MBR.

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.