Развернуть прямоугольник в области на плоскости X, Y со списком точек, представляющих область

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

Я работаю на С# с кинектом и пикселями глубины.

Это изображение — просто лучшее представление того, о чем я говорю, которое я смог найти.

введите здесь описание изображения

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

У меня уже есть твердая фигура, представленная в виде списка точек на плоскости x, y. Итак, у меня есть форма на 2D-плоскости. Вроде этого:

введите здесь описание изображения

Чтобы упростить задачу, я просто создам прямоугольник с ребрами, параллельными линиям x и y. Я не ищу код. Мне просто нужно какое-то направление или алгоритм, который я могу прочитать и попытаться реализовать.

Если необходимы какие-либо разъяснения, пожалуйста, дайте мне знать.


c# area kinect maximization calculus
person Cheddar    schedule 21.04.2013    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Если вам просто нужен ограничивающий прямоугольник, вы можете пройти по списку точек. Сохраните минимум и максимум X и Y (например, minX, minY, maxX, maxY). Пройдитесь по всему списку и сделайте 4, если проверьте каждый из пунктов, например:

if(point.X < minX) minX = point.X
if(point.Y < minY) minY = point.Y
if(point.X > maxX) maxX = point.X
if(point.Y > maxY) maxY = point.Y

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

person iamsed    schedule 21.04.2013

arrow_upward
0
arrow_downward

Взгляните на задачу о самом большом пустом прямоугольнике. Вот одна статья с алгоритмом вычисления ее решений.

Точнее, это задача, заключающаяся в поиске наибольшей области, не содержащей ни одной точки, по заданному набору точек. В вашем случае вы можете применить его к некоторым точкам, которые будут описывать край вашей 2D-формы, а также к некоторым точкам снаружи. Тогда процедура статьи вычислит самый большой прямоугольник в желтой области. Я применил такую ​​процедуру, чтобы найти большую часть изображения, не содержащую прозрачных пикселей. Это работало хорошо, но было немного медленно.

Решение применимо к набору точек (т. е. без сегментов), но вы можете легко вычислить приближенное решение с аппроксимацией вашей формы.

person Julien    schedule 17.06.2013