Привет .
Условие : Дан набор точек на плоскости (координаты х и у) необходимо построить прямоугольник наименьшей площади, который содержал бы в себе все эти точки. Прямоугольник может быть произвольо ориентированным (наклонным).
Помогите придумать какое — нибудь дельное решение с нормальными затратами по времени.
Может быть также другая интерпретация этой задачи : Дан все тот же набор точек и линейные размеры прямоугольника, надо его оптимальным образом (каким- нибудь) разместить в плоскости. Заранее спасибо
Здравствуйте, tinytjan, Вы писали:
T>Привет . T>Условие : Дан набор точек на плоскости (координаты х и у) необходимо построить прямоугольник наименьшей площади, который содержал бы в себе все эти точки. Прямоугольник может быть произвольо ориентированным (наклонным). T>Помогите придумать какое — нибудь дельное решение с нормальными затратами по времени.
Утверждение 1. Все стороны икомого прямоугольника будут на точках.
Утверждение 2. Найдется сторона, содержащая две точки.
Из-за утверждения 2 можно перебрать все пары точек, которые будут задавать ориентацию. Полученная сложность O(N^3). Устраивает? В принципе, сложность можно уменьшить.
T>Может быть также другая интерпретация этой задачи : Дан все тот же набор точек и линейные размеры прямоугольника, надо его оптимальным образом (каким- нибудь) разместить в плоскости. Заранее спасибо
Каким "каким-нибудь"?
---
С уважением,
Лазарев Андрей
Re[2]: Описанный прямоугольник минимальной площади
Здравствуйте, Tan4ik, Вы писали:
T>Здравствуйте, tinytjan, Вы писали:
T>>Привет . T>>Условие : Дан набор точек на плоскости (координаты х и у) необходимо построить прямоугольник наименьшей площади, который содержал бы в себе все эти точки. Прямоугольник может быть произвольо ориентированным (наклонным). T>>Помогите придумать какое — нибудь дельное решение с нормальными затратами по времени.
T>Утверждение 1. Все стороны икомого прямоугольника будут на точках. T>Утверждение 2. Найдется сторона, содержащая две точки.
T>Из-за утверждения 2 можно перебрать все пары точек, которые будут задавать ориентацию. Полученная сложность O(N^3). Устраивает? В принципе, сложность можно уменьшить.
O(N^2):
Сперва стоим выпуклую оболочку, а потом для каждой из её сторон (N) ищем параметры прямоугольника (за N перебираем все точки, проектируя на прямую + считая расстояние до прямой).
... << RSDN@Work 1.1.3 stable >>
Re[2]: Описанный прямоугольник минимальной площади
Здравствуйте, Tan4ik, Вы писали:
T>Здравствуйте, tinytjan, Вы писали:
T>>Привет . T>>Условие : Дан набор точек на плоскости (координаты х и у) необходимо построить прямоугольник наименьшей площади, который содержал бы в себе все эти точки. Прямоугольник может быть произвольо ориентированным (наклонным). T>>Помогите придумать какое — нибудь дельное решение с нормальными затратами по времени.
T>Утверждение 1. Все стороны икомого прямоугольника будут на точках. T>Утверждение 2. Найдется сторона, содержащая две точки.
T>Из-за утверждения 2 можно перебрать все пары точек, которые будут задавать ориентацию. Полученная сложность O(N^3). Устраивает? В принципе, сложность можно уменьшить.
Спасибо за совет, вроде на первый взгляд вполнее ничего.
T>>Может быть также другая интерпретация этой задачи : Дан все тот же набор точек и линейные размеры прямоугольника, надо его оптимальным образом (каким- нибудь) разместить в плоскости. Заранее спасибо T>Каким "каким-нибудь"?
Например методом МНК, но я не знаю как его сюда припаять
Re[3]: Описанный прямоугольник минимальной площади
Здравствуйте, DK3981, Вы писали:
T>>Из-за утверждения 2 можно перебрать все пары точек, которые будут задавать ориентацию. Полученная сложность O(N^3). Устраивает? В принципе, сложность можно уменьшить. DK>O(N^2): DK>Сперва стоим выпуклую оболочку, а потом для каждой из её сторон (N) ищем параметры прямоугольника (за N перебираем все точки, проектируя на прямую + считая расстояние до прямой).
Верно, это было заложено под "можно уменьшить". На самом деле можно еще сильнее уменьшить
Здравствуйте, DK3981, Вы писали: T>>Из-за утверждения 2 можно перебрать все пары точек, которые будут задавать ориентацию. Полученная сложность O(N^3). Устраивает? В принципе, сложность можно уменьшить. DK>O(N^2): DK>Сперва стоим выпуклую оболочку, а потом для каждой из её сторон (N) ищем параметры прямоугольника (за N перебираем все точки, проектируя на прямую + считая расстояние до прямой).
Это пессимистическая оценка, для случая, когда точки представляют собой вершины выпуклого многоугольника. При более случайном расположении можно ожидать размер выпуклой оболочки пропорциональным N^(1/2). Поэтому общая производительность будет примерно O(N).
... << RSDN@Home 1.1.4 beta 4 rev. 303>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[4]: Описанный прямоугольник минимальной площади
DK>>Сперва стоим выпуклую оболочку, а потом для каждой из её сторон (N) ищем параметры прямоугольника (за N перебираем все точки, проектируя на прямую + считая расстояние до прямой). S>Это пессимистическая оценка, для случая, когда точки представляют собой вершины выпуклого многоугольника. При более случайном расположении можно ожидать размер выпуклой оболочки пропорциональным N^(1/2). Поэтому общая производительность будет примерно O(N).
Выпуклую оболочку всё-таки надо построить, так что O(N log(N)).
P.S. А потом окажется, что в исходной задаче N ~= 20 и этот спор ну совсем непринципиален
... << RSDN@Work 1.1.3 stable >>
Re[5]: Описанный прямоугольник минимальной площади
Здравствуйте, DK3981, Вы писали:
DK>>>Сперва стоим выпуклую оболочку, а потом для каждой из её сторон (N) ищем параметры прямоугольника (за N перебираем все точки, проектируя на прямую + считая расстояние до прямой). S>>Это пессимистическая оценка, для случая, когда точки представляют собой вершины выпуклого многоугольника. При более случайном расположении можно ожидать размер выпуклой оболочки пропорциональным N^(1/2). Поэтому общая производительность будет примерно O(N).
DK>Выпуклую оболочку всё-таки надо построить, так что O(N log(N)). DK>P.S. А потом окажется, что в исходной задаче N ~= 20 и этот спор ну совсем непринципиален
Можете поспорить количество точек может быть десяток тысяч и больше. А заодно может подскажете как нормально быстро и эффективно найти эту выпуклую оболочку?
Re[6]: Описанный прямоугольник минимальной площади
DK>>Выпуклую оболочку всё-таки надо построить, так что O(N log(N)). T>Можете поспорить количество точек может быть десяток тысяч и больше. А заодно может подскажете как нормально быстро и эффективно найти эту выпуклую оболочку?
Один из способов — считаем центр масс, сортируем вокруг него точки по углу (N log N), выбираем такую, которая точно входит в выпуклую оболочку (например, с min координатой X, при нескольки таких — с min Y), и следующую за ней. Далее у нас всегда есть 2 точки и мы пробуем добавить третюю (в порядке сортировки). Если она лежит "выпукло" относительно предыдущих двух — добавляем её к выпуклой оболочке, если нет — выкидываем последнюю точку из списка оболочки, пока не останется 1 точка или пока не выполнится условие выше. В любом случае добавляем к списку новую точку.
И так пока не дойдём до той точки, с которой начали.
Так как каждая точка максимум 1 раз добавляется и 1 раз выкидывается — здесь время ещё O(N).
... << RSDN@Work 1.1.3 stable >>
Re[7]: Описанный прямоугольник минимальной площади
DK>>>Выпуклую оболочку всё-таки надо построить, так что O(N log(N)). T>>Можете поспорить количество точек может быть десяток тысяч и больше. А заодно может подскажете как нормально быстро и эффективно найти эту выпуклую оболочку?
DK>Один из способов — считаем центр масс, сортируем вокруг него точки по углу (N log N), выбираем такую, которая точно входит в выпуклую оболочку (например, с min координатой X, при нескольки таких — с min Y), и следующую за ней. Далее у нас всегда есть 2 точки и мы пробуем добавить третюю (в порядке сортировки). Если она лежит "выпукло" относительно предыдущих двух — добавляем её к выпуклой оболочке, если нет — выкидываем последнюю точку из списка оболочки, пока не останется 1 точка или пока не выполнится условие выше. В любом случае добавляем к списку новую точку. DK>И так пока не дойдём до той точки, с которой начали. DK>Так как каждая точка максимум 1 раз добавляется и 1 раз выкидывается — здесь время ещё O(N).
Долго думал над алгоритмом и пришел к выводу, что он не всегда строит выпуклый многоугольник. Чтобы построить выпуклый надо проверять поочередно все предыдущие точки, включенные в границу. Если интересно, могу привести пример, когда построится невыпуклый.
Re[8]: Описанный прямоугольник минимальной площади
Здравствуйте, tinytjan, Вы писали:
DK>>Один из способов — считаем центр масс, сортируем вокруг него точки по углу (N log N), выбираем такую, которая точно входит в выпуклую оболочку (например, с min координатой X, при нескольки таких — с min Y), и следующую за ней. Далее у нас всегда есть 2 точки и мы пробуем добавить третюю (в порядке сортировки). Если она лежит "выпукло" относительно предыдущих двух — добавляем её к выпуклой оболочке, если нет — выкидываем последнюю точку из списка оболочки, пока не останется 1 точка или пока не выполнится условие выше. В любом случае добавляем к списку новую точку. DK>>И так пока не дойдём до той точки, с которой начали. DK>>Так как каждая точка максимум 1 раз добавляется и 1 раз выкидывается — здесь время ещё O(N).
T>Долго думал над алгоритмом и пришел к выводу, что он не всегда строит выпуклый многоугольник. Чтобы построить выпуклый надо проверять поочередно все предыдущие точки, включенные в границу. Если интересно, могу привести пример, когда построится невыпуклый.
Здравствуйте, DK3981, Вы писали:
DK>O(N^2): DK>Сперва стоим выпуклую оболочку, а потом для каждой из её сторон (N) ищем параметры прямоугольника (за N перебираем все точки, проектируя на прямую + считая расстояние до прямой).
Отнюдь! Если выпуклая оболочка содержит K точек, то время полного обхода составляет O(K), а не O(K^2).
Для построения прямоугольника нам нужны 4 точки, правильно?
1.1) Берём произвольную точку оболочки и мысленно поворачиваем систему координат так, что эта точка вместе с ещё одной смежной (против часовой стрелки) лежит на нижней горизонтали.
1.2) Начиная обход оболочки по часовой стрелке, находим самую нижнюю (это наша произвольная), самую левую, самую верхнюю, самую правую. В худшем случае, мы обошли K-1 точку Кстати, пусть нас не смущает, что одна точка может выступить более чем в одной роли (например, в треугольнике всего три вершины, а ролей 4).
2.1) Рассчитываем габариты и площадь прямоугольника, запоминаем лучший результат.
3.1) Переходим по часовой стрелке к точке, следующей от старта. Поворачиваем систему координат.
3.2) Ищем левую, верхнюю, правую, начиная с предыдущих (а не с начала).
3.3) Переходим к 2.1
Теперь заметим, что итераторы "нижняя", "левая", "верхняя", "правая" обошли всю оболочку, побывав в каждой точке по разу. То есть это O(4K) == O(K), а не O(K^2).
Кстати, выпуклая оболочка строится за O(N log N), где N — число всех точек множества.
Ну и поскольку K<=N, то итоговая оценка — O(N log N) + O(K) == O(N log N).
Перекуём баги на фичи!
Re[4]: Описанный прямоугольник минимальной площади
Здравствуйте, FreshMeat, Вы писали:
FM>Если не трудно, приведи. Будет лучше, если с картинкой.
Вот вам картинка.
Синяя линия должна получиться, красная если я все правильо понял в алгоритме, получается на самом деле.
Порядок точек слева направо.Если я не прав, поправляйте, не обижусь
Re[10]: Описанный прямоугольник минимальной площади
Здравствуйте, tinytjan, Вы писали:
T>Вот вам картинка.
Спасибо. T>Синяя линия должна получиться, красная если я все правильо понял в алгоритме, получается на самом деле. T>Порядок точек слева направо.Если я не прав, поправляйте, не обижусь
^^^^^ Точки сортируются не по координате x, а по углу относительно центра масс точек (например) и любой другой точки это плоскости. DK3981 достаточно хорошо объяснил
алгоритм. Если информации не хватает, можно глянуть более подробное описание работы алгоритма Грэхема, в книге
Препарата, Шеймос. Вычислительная геометрия.
гл. 3 Выпуклые оболочки: Основные алгоритмы. стр. 129-133
Скачать главы 3 и 4 можно здесь
Если останутся вопросы, пишите, будем разбираться
Хорошо там, где мы есть! :)
Re[11]: Описанный прямоугольник минимальной площади
Здравствуйте, FreshMeat, Вы писали:
FM>Здравствуйте, tinytjan, Вы писали:
T>>Вот вам картинка. FM>Спасибо. T>>Синяя линия должна получиться, красная если я все правильо понял в алгоритме, получается на самом деле. T>>Порядок точек слева направо.Если я не прав, поправляйте, не обижусь FM> ^^^^^ Точки сортируются не по координате x, а по углу относительно центра масс точек (например) и любой другой точки это плоскости.
Так как пример произвольный, то точки могут располагаться произвольно. Если точку, относительно которой происходит упорядочивание, поместить снизу на достаточном удалении от рассмотренных точек, то получится, что показанные точки упорядочены нормально(так как и надо).Получается, проблема остается.
Вообще я уже реализовал алгоритм.Правда чу-чу в лоб. Время у меня получилось О(n^2).Работает вроде ничего.
Но в принципе можно попробовать и улучшить.
Всем спасибо за ответы. Если возникнут новые предложения и пожелания, пишите.
Re[4]: Описанный прямоугольник минимальной площади
Перекуём баги на фичи!
