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

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

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


c# algorithm spatial mbr
person CSharpened    schedule 27.01.2012    source источник
comment
К сожалению, я не знаю, с чего начать. Я нахожусь на этапе, когда у меня есть свои координаты в списке строк типа, и я не уверен, как двигаться дальше.   -  person CSharpened    schedule 27.01.2012
comment
@ Ну, у вас есть два типа: ограничивающая рамка, выровненная по оси; который находится просто путем нахождения минимального x / y и максимального x / y. Или у вас есть произвольно ориентированный ограничивающий прямоугольник, который более сложен (en.wikipedia.org/wiki/Minimum_bounding_box_algorithms). Это усложняется, если вам нужно учитывать кривизну земли (что, я надеюсь, вы не учитываете), хотя технически вы все еще рисуете прямоугольник, но на самом деле вместо этого это часть поверхности сферы ( наверное слишком много для того, что вам нужно)   -  person Andras Zoltan    schedule 27.01.2012
comment
Понятно. Мне нужна функция, которая предоставит 4 координаты для коробки. Итак, два значения X и два значения Y. Не могли бы вы предложить лучший способ сделать это - разделить мои координаты, а затем сравнить их все, чтобы найти наименьшее значение X и минимальное значение Y? Если бы я сделал это, я бы получил только значение minX и значение maxY? Можно ли по этим двум цифрам вычислить другие значения X и Y? Извините, если я немного растерялся. Пространство - это совсем не моя область.   -  person CSharpened    schedule 27.01.2012
comment
В настоящее время мне не нужно учитывать кривизну, поскольку я использую сетку британской национальной сетки, но со временем это может стать требованием, но сейчас я просто хочу получить рабочую функцию, а затем могу двигаться дальше.   -  person CSharpened    schedule 27.01.2012

Ответы (3)


arrow_upward
18
arrow_downward

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

person Andras Zoltan    schedule 27.01.2012
comment
Похоже, это именно то, что мне нужно. Спасибо. - person CSharpened; 27.01.2012

arrow_upward
8
arrow_downward

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

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

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

person Julian    schedule 27.01.2012

arrow_upward
0
arrow_downward

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

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

person wackmc    schedule 04.11.2012