Рассчитать минимальный ограничивающий прямоугольник 2D фигуры по координатам - PullRequest
Новая
       37

Рассчитать минимальный ограничивающий прямоугольник 2D фигуры по координатам

9 голосов
/ 27 января 2012

У меня есть решение, которое использует пространственные данные для представления группы точек на карте. Мне нужно использовать координаты, которые представляют экстенты кластера, чтобы найти минимальный ограничивающий прямоугольник, который может содержать указанный кластер точек.

Существует ли какой-либо простой алгоритм для расчета этого или есть какие-либо встроенные функции в C # для достижения этого. Мне известно о NetTopologySuite, но я не уверен, каким образом / если бы я мог использовать это для достижения той же цели. У меня есть список координат, поэтому мне нужно передать этот список строк и получить MBR.

Ответы [ 3 ]

13 голосов
/ 27 января 2012

Самое простое решение, и я предполагаю, что наиболее вероятное решение - вычислить ограничивающий прямоугольник, выровненный по оси, что является просто случаем нахождения значений min / max 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 вектора для этого).

7 голосов
/ 27 января 2012

Один из возможных, хотя и простых, способов сделать это может быть следующим: 

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

Это, конечно, предполагает, что вы ищете прямоугольник, выровненный по вертикали и горизонтали. Поэтому, если вы ищете наименьший возможный прямоугольник, независимо от того, как он вращается, это не для вас.

0 голосов
/ 05 ноября 2012

Попробуйте G # на http://www.ceometric.com/products/g.html

Имеет минимальную площадь и минимальные периметры, окружающие прямоугольники, а также минимальные окружающие круги.

...