минимальная площадь прямоугольника

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

0

не совсем понятно: угол наклона прямоугольника относительно оси абсцисс изначально задан или его определить надо?

0

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

Миниатюры

 

0

быстрый поиск по сети дал следующие результаты:
1) задача эта называется поиском "минимального ограничивающего прямоугольника" (МОП)
2) существует некоторое число уже разработанных алгоритмов для этого поиска
3) простейшим, на мой взгляд, является следующий алгоритм:
-- существующее множество (облако) точек ограничиваем по крайним точкам по горизонтали и вертикали, вычисляем получившуюся площадь и запоминаем её
-- далее выбираем любую крайнюю точку облака (лежащую на выпуклом многоугольнике, описывающем облако) и начинаем относительно неё вращать облако точек на, например, пол-градуса по часовой стрелке и на каждом шаге вращения вновь ограничиваем облако по вертикали и горизонтали и снова вычисляем и запоминаем площадь (и угол поворота)
-- в итоге, повернув на 90 градусов, находим минимальную среди площадей и соответствующий ей угол
(больше 90 градусов поворачивать не надо, ибо прямоугольник - штука симметричная по осям, проходящим через середины сторон)
---------

могу попробовать реализовать, но для этого надо получить от вас формат ввода данных (точек) и формат вывода данных
на мой взгляд, наиболее привлекательным будет следующее:
-- ввод точек кликами по ограниченному полю: где кликнули - там и точка
-- после окончания ввода точек нажимается кнопка "Найти МОП"
-- на экране в реале это облако точек ограничивается прямоугольником, ориентированным по вертикали/горизонтали и на "табло" высвечивается угол "0 градусов" и соответствующая ей площадь в квадратных пикселях + надпись "Текущая минимальная площадь = найденной для 0 градусов"
-- затем по таймеру облако поворачивается и снова высвечивается величина угла и площадь + меняется запись для "Текущей минимальной"
-- по завершению поворота на 90 градусов облако восстанавливается в исходное состояние и рисуется найденный минимальный прямоугольник с соответствующим ему углом наклона

как-то так

1

kalabuni, предложенный вами способ реализации, был выбран мною изначально, но столкнулся с такой проблемой, когда с помощью canvas в цикле поворачивал изображение, и проверял пиксели, ответом всегда было исходное изображение, и вся проблема в том, что метод drawImage() в canvas является асинхронным, и на момент проверки он просто оказывался пуст...и я предположил что возможно есть какая нибудь формула что бы сделать это без поворота....так же искал методы на подобии .ready() но ничего не нашел, возможно вы знаете как дождаться рисунка, а потом проверять, но без интервалов и таймаутов, так как с ними это займет очень много времени.

0

это я как-то не подумал
90 градусов по пол-градуса - это 180 шагов, даже если по паре секунд на шаг - это 5 минут... долго...

если без визуальных эффектов (на этапе вычислений), то после ввода точек кликами (на этом варианте настаиваю, ибо вводить точки координатами - это вообще бред, который займёт десятки минут) можно положение каждой точки при очередном повороте просто вычислить, тем более нас интересуют не все точки, а только габаритные и, соответственно, безо всякой канвы получить минимальную площадь и соответствующий угол
и только в конце вычислений, зная угол и номера точек (по которым проводились стороны прямоугольника) можно с помощью канвы сразу нарисовать искомый прямоугольник

0

исходное изображение и есть canvas....а насчет вычислить положение точек при повороте, это не совсем понял как можно сделать...

Добавлено через 1 час 18 минут
на всякий случай еще сделал рисовалку точек на фидлере
рисовалка

0

начну сначала
-- имеем контейнер <div style="position: relative; width: 888px; height: 777px; border: 1px solid #000"></div> - это поле для размещения точек с заданными шириной и высотой

-- клиент кликает внутри этого контейнера и на месте каждого клика появляется новая точка,
которую мы создаём скриптом программно, добавляя всякий раз внутрь контейнера новый
<div id="p0" style="position: absolute; overflow: hidden; width: 1px; height: 1px; background: red; left: 123px; top: 234px"></div>,
где 0 в id - порядковый номер точки (считать начинаем с нуля, как обычно),
а 123 и 234 - координаты первого клика пользователя

-- кликает клиент второй раз, мы создаём вторую точку на месте клика
<div id="p1" style="position: absolute; overflow: hidden; width: 1px; height: 1px; background: red; left: 98px; top: 543px"></div>,

-- после того, как клиент закончил ввод точек и нажал кнопку "Найти МОП", сохраняем в двух массивах все left'ы и top'ы всех точек облака, вот так:
var LEFTs = [123, 98, ...];
var TOPs = [234, 543, ...];

-- затем находим в обоих массивах минимальные и максимальные значения и их разницу
это и будут величины сторон описывающего прямоугольника в пикселях
произведение их и даст нам площадь ОП'а при угле в 0 градусов -- (maxLEFTs - minLEFTs) * (maxTOPs - minTOPs)
также запоминаем номера точек с минимальными и максимальными координатами

-- выбираем одну из точек облака центром вращения
пусть это будет точка номер 25 -- <div id="p25"></div> для которой в массивах LEFTs и TOPs также сохранены её координаты (как и для всех точек)

-- зная координаты центра вращения, можно легко определить радиусы вращения для всех остальных точек
формула вычисления отрезка по координатам его конца известна - из теоремы Пифагора - корень квадратный из суммы квадратов разниц координат
т.е. для точки p13 радиус вращения относительно выбранной центром точки p25 будет равен
var R13 = Math.sqrt ((TOPs [13] - TOPs [25]) * (TOPs [13] - TOPs [25]) + (LEFTs [13] - LEFTs [25]) * (LEFTs [13] - LEFTs [25]));

-- зная угол поворота alfa (который мы сами будем задавать в радианах на каждом шаге), легко вычислить новые координаты для точки номер 13 через параметрическое уравнение
newLEFTs [13] = LEFTs [25] + R13 * Math.cos (alfa);
newTOPs [13] = TOPs [25] + R13 * Math.sin (alfa);

-- таким образом получаем два массива с координатами всех точек при повороте на угол alfa -- newLEFTs и newTOPs

-- также, как и в исходном случае, находим в обоих массивах минимум и максимум и вычисляем величину площади; если величина площади меньше предыдущей вычисленной, запоминаем номера точек, у которых были минимальные и максимальные координаты и текущий угол поворота

-- и далее увеличиваем угол alfa, вплоть до того, покуда он не достигнет PI / 2,
не забывая при этом, что угол отсчитывается от полуоси 0х против часовой стрелки

-- в итоге имеем два исходных массива с координатами точек, значение угла, при котором получилась минимальная площадь и номера точек, через которые надо провести 4 стороны прямоугольника

-------------
аналогичные вычисления по вышеуказанным формулам я делал недавно в теме Строка, бегущая по окружности

1

kalabuni, ты ГЕНИЙ....спасибо тебе огромное !!!! истолковал все просто отлично !!! сегодня - завтра попробую это однозначно лучший ответ потом отпишу здесь получилось ли

Добавлено через 14 часов 55 минут
kalabuni, вот сегодня с утра сел делать и появился такой еще вопросик а если при повороте в одну из сторон, полученная нами площадь больше чем предыдущая. Можем ли мы считать что при дальнейшем повороте в эту же сторону мы никогда не получим меньшую площадь, при условии что поворачиваем мы от -45 до 45 градусов. ?

0

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

полагаю, что в общем случае мы так считать не можем

и потом... я не вижу смысла "поворачивать" от -45 до +45 градусов
чисто программно легче "поворачивать" на 90 градусов от исходного положения в какую-то одну любую сторону
параметрическое уравнение окружности, как я указывал выше, исходит из отсчёта угла от полуоси 0х против часовой стрелки, так что для простоты программной записи надо менять угол от 0 радиан до Math.PI / 2 с каким-то выбранным вами шагом, например .01

сделать вам рабочий код или сами справитесь?

0

Сообщение от kalabuni полагаю, что в общем случае мы так считать не можем

пожалуй я с вами не соглашусь, сейчас попробую обьяснить свою логику.
прямоугольник, с минимальной площадью, описывающий все наши точки существует всегда.
допустим что наш прямоугольник, с наименьшей площадью, уже лежит паралельно оси ох.
что тогда будет происходить при повороте его например вправо, площадь прямоугольника, описанного вокруг нашего прямоугольника, будет пропорционально увеличиваться, до тех пор, пока пока его высота, не станет равна его ширине (квадрат), что произойдет при повороте на 45 градусов, далее же, площадь описываемого прямоугольника, вокруг нашего прямоугольника, будет пропорционально уменьшаться, пока они не сольются, что произойдет при повороте на 90 градусов.
отсюда следует, что если поворачивая фигуру от 0 до 45, площадь описываемого прямоугольника, больше чем площадь предыдущего прямоугольника, значит верный угол будет предыдущий, при условии что это не первый этап поворота, если же он первый, значит следует вращать точки в противоположную сторону, до тех пор, пока площадь не начнет увеличиваться..
зачем это мне спросите вы?? а затем что бы уменьшить количество операций.

0

будем надеяться, что вы правы, пробуйте

1

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

newLEFTs [13] = LEFTs [25] + R13 * Math.cos (alfa);
newTOPs [13] = TOPs [25] + R13 * Math.sin (alfa);

при повороте точек на 0 градусов у нас получается вот такая интересная штука

newLEFTs [13] = LEFTs [25] + R13 * 1 ; так как косинус 0 равняется 1
newTOPs [13] = TOPs [25] + R13 * 0 ; а тут все норм...

и получается при повороте на 0 у нас левые координаты точек сдвигаются...

0

либо плохо учились в школе
либо перезанимались
отдохните

Сообщение от Galphimbl получается при повороте на 0 у нас левые координаты точек сдвигаются

не получается
никто никуда не сдвигается

точка 13 всегда находится на расстоянии R13 от точки 25, при любом угле

в случае 0 градусов/радиан точка 13 смещена по горизонтали на R13, а по вертикали на 0, в итоге расстояние между точками равно R13
newLEFTs [13] = LEFTs [25] + R13 * Math.cos (0) = LEFTs [25] + R13
newTOPs [13] = TOPs [25] + R13 * Math.sin (0) = TOPs [25] + 0

сделайте угол 90 градусов и получите смещение по вертикали равное R13, а по горизонту будет 0, и опять расстояние между точками равно R13
newLEFTs [13] = LEFTs [25] + R13 * Math.cos (Math.PI / 2) = LEFTs [25] + 0
newTOPs [13] = TOPs [25] + R13 * Math.sin (Math.PI / 2) = TOPs [25] + R13

Миниатюры

 

1

добавлю:
угол 0 - это не исходная позиция точки 13, а положение, когда точка 13 находится на горизонтальной прямой вместе с точкой 25 (центром вращения)
я же дважды вам писал: в параметрическом уравнении окружности угол отсчитывается от полуоси 0х против часовой стрелки

1

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

Добавлено через 2 минуты
kalabuni, спасибо вам еще раз огромное за то что не покидаете тему, а всячески пытаетесь помочь

0

Galphimbl, в описании алгоритма здесь я упустил один момент
правда, я вам дал ссылку на "попа с собакой",
и если бы вы попытались разобраться с тем кодом, вы бы увидели раздел скрипта под названием // **** расчёт угловых смещений букв текста

всякая точка N облака находится:
а) на каком-то постоянном расстоянии от центра вращения, это - радиус RN, который мы вычисляли
б) и под каким-то постоянным углом относительно горизонтальной линии, проходящей через точку вращения

вот про эти самые углы я вам забыл написать, а вы мою ссылку про "попа с собакой" не изучили

чтобы повернуть все точки на .01 радиана против часовой, надо прибавить эти .01 радиана к собственному углу каждой точки

угол определяется из того же параметрического уравнения - получайте арксинусы и арккосинусы из параметрического уравнения
где, например, для точки номер 13
R - это наш с вами R13
x₀ - LEFTs [25]
у₀ - TOPs [25]
x - LEFTs [13]
y - TOPs [13]

Миниатюры

 

1

kalabuni, не обратил внимания что это была ссылка завтра с утра все прочитаю, и попробую разобраться.

Добавлено через 15 часов 24 минуты
kalabuni, огромное спасибо все заработало

0

поздравляю!
покажете?

1

ну раз не показываете, покажу свой вариант - не пропадать же ему, раз сделал

безо всякой оптимизации "кручу-верчу" на все 360 градусов

"заточено" под Мозиллу и Хром, в других работать не будет... мей би в Опере, не проверял

http://codecenter.awardspace.com/mop.html

1