Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Точки в прямоугольнике

Автор: NiJazz 25.4.2004, 12:08

Такая еще задача:

Цитата

Даны N точек на плоскости. Найти наименьший прямоугольник, содержащий все эти точки внутри себя (или на границе).

Жду хотя бы подсказки.
Спасибо.

Автор: p0s0l 25.4.2004, 12:53

Ищешь минимальные и максимальные x и y координаты точек - это и будет твой прямоугольник...

Автор: NiJazz 25.4.2004, 17:45

p0s0l
Уже сделал сегодня.

Но всё равно спасибо.

Автор: podval 25.4.2004, 17:51

NiJazz
Так выложи решение. Мало ли кому понадобится еще.

Автор: maxim1000 25.4.2004, 17:53

Цитата

Ищешь минимальные и максимальные x и y координаты точек - это и будет твой прямоугольник...

рискну предположить, что все не так просто
это будет решением только в том случае, если есть условие параллельности сторон прямоугольника осям координат
если же прямоугольник может быть ориентирован как угодно, то как минимум придется определиться со словом "наименьший", а то мне кажется, что для разных критериев будут разные результаты
(в случае со сторонами, параллельными осям координат, похоже, результат получается для всех более-менее разумных критериев: площадь, периметр, диагональ, ...)
в общем случае можно предложить что-нибудь в таком роде:
1. зафиксировать направление, которому будут параллельны/перпендикулярны стороны прямоугольника
2. решить задачу для фиксированных направлений (как было предложено)
таким образом перебрать всевозможные направления и выбрать наилучшее

Автор: NiJazz 25.4.2004, 17:53

Среда: Turbo C++ 3

Код

#include <iostream.h>
#include <stdlib.h>
#include <conio.h>

void main()
{
   clrscr();
   randomize();
   unsigned short pcount = 0;
   cout << "Введите количество точек на плоскости: ";
   cin >> pcount;
   cout << endl;
   struct point
   {
      int x;
      int y;
   };
   point* points = new point[pcount];
   for (int i=0;i<pcount;i++)
   {
      points[i].x = rand()%50+5;
      points[i].y = rand()%50+5;
   }
   int maxx = 0;
   int maxy = 0;
   int minx = 32767;
   int miny = 32767;
   for (i=0;i<pcount;i++)
   {
      if (maxx<points[i].x) maxx = points[i].x;
      if (maxy<points[i].y) maxy = points[i].y;
      if (minx>points[i].x) minx = points[i].x;
      if (miny>points[i].y) miny = points[i].y;
   }
   cout << "Вершины минимального прямоугольника: ";
   cout <<'('<<minx<<','<<miny<<"), ("<<minx<<','<<maxy<<"), ";
   cout <<'('<<maxx<<','<<miny<<"), ("<<maxx<<','<<maxy<<")";
   cin.get();
   cin.get();
}

Автор: maxim1000 25.4.2004, 17:54

припоздал маленько...

Автор: NiJazz 25.4.2004, 17:55

Не хватает такого кода:

Код

for (i=0;i<pcount;i++)
{
   delete &points[i];
}

Но тогда выдаёт ошибку "NULL poiter assignment".
Возиться долго не стал, поэтому оставил всё как есть. Если подскажите, как грамотно сделать освобождение памяти, буду благодарен.
Добавлено @ 17:57
maxim1000
Мысли очень правильные. Придётся это делать, если препод потребует.

Автор: Chingachguk 25.4.2004, 18:03

Мне кажется, что maxim1000 прав: решение не так очевидно.

Например, следующие 4-е точки:

(0,0),(4,6),(6,4),(10,10). Твое решение даст: (0,0) и (10,10) (еще две вершины: (10,0) и (0,10)). Но решением будет прямоугольник под углом 45 градусов к осям - примерно это (-1,1), (1,-1), (9,11) и (11,9).

Автор: p0s0l 25.4.2004, 20:05

Ну если не паралельно осям, тогда можно модернизировать так:
1) ищем центр всех точек (это середина между min и max)
2) ищем точку, которая находится всех дальше от центра
так мы выяснили угол поворота прямоугольника (alpha)
3) поворачиваем ось координат на угол alpha
(вернее тут будет создан второй массив точек с измененными координатами)
4) теперь применяем первоначальный алгоритм (через min и max) на второй массив
5) результат поворачиваем на угол -alpha

Это я объяснил чтобы понятнее было, но в деле лучше вместо 3-4-5 не создавать второй массив, а на ходу поворачивать каждую точку и проверять на min/max...

Попробовал на простых примерах - вроде действует правильно...

Автор: dwr_budr 25.4.2004, 21:58

2NiJazz

А зачем каждую точку удаляешь то? Ты ж блок выделял! Блок и удаляй!

Автор: Crait 26.4.2004, 16:30

Цитата

Но тогда выдаёт ошибку "NULL poiter assignment".

delete[] points;

Автор: Akina 26.4.2004, 16:45

Для начала надо сузить поиск, построив окружающий многоугольник (получаемый попарным соединением точек аки вершин многоугольника) и отбросив лишние (внутренние) точки - кстати он будет заведомо выпуклым. После чего в принципе можно доказать, что при любом понимании слова "наименьший прямоугольник" (площадь, периметр, минимакс стороны и т.п.) одна из сторон описывающего многоугольника будет лежать на стороне у итогового прямоугольника. Остальное в принципе просто...

Автор: maxim1000 26.4.2004, 18:15

Цитата

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

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

Автор: Unregistered 27.4.2004, 00:36

Цитата(maxim1000 @ 26.4.2004, 18:15)

Цитата

А я вот попробовал проделать то же самое и получил противоположный результат

Нарисовал равностононний треугольник со стороной a, зафиксировал его
Совместил одну из вершин объемлющего прямоугольника с вершиной треугольника

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

Площадь я считал 2 часа

и в результате получил, что она равна
(sqrt(3)/4 + 1/2*cos(gamma))*a^2, где -pi/6<=gamma<=pi/6

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

, но вроде бы хорошо все проверял...

Автор: Unregistered 27.4.2004, 00:45

Цитата(Unregistered @ 27.4.2004, 00:36)

Остальные вершины прямоугольника стал двигать вокруг треугольника
так, чтобы они касались его сторон

Имеется в виду, что вершины треугольника касались сторон объемлющего прямоугольника
или совпадали с его вершинами

Сорри, криво написал

Автор: Akina 27.4.2004, 08:18

На самом деле для доказательства достаточно рассмотреть следующее - дана сторона многоугольника (для доказательства достаточно - отрезок на полскости) и дальняя вершина (точка не на прямой, на коей этот отрезок). По ним строим прямоугольник - одна сторона полностью включает отрезок, противоположная - содержит точку. Легко доказать что при вращении прямоугольника вокруг любого из концов отрезка критерий увеличивается - т.е. егопроизводная по углу поворота положительна.
А руками вращать и считать имхо неправильно...

Автор: maxim1000 27.4.2004, 11:04

Цитата

Площадь я считал 2 часа и в результате получил, что она равна
(sqrt(3)/4 + 1/2*cos(gamma))*a^2, где -pi/6<=gamma<=pi/6

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

ну и я немного посчитал:
рисунки вставлять не умею, потому придется поработать с буквами (только надо все это читать с листочком бумаги, на котором это все рисовать)

есть треугольник ABC - равносторонний
есть прямоугольник ADEF (как видно, одна вершина совпадает с вершиной треугольника)
точка B лежит на стороне DE
точка C лежит на стороне EF
наша задача - подобрать угол CAF для наименьшей площади прямоугольника
S - площадь прямоугольника
a - сторона треугольника
S=DA*AF=a*cos(DAB)*a*cos(CAF)=a*a*cos(90-60-CAF)*cos(CAF)=
=a*a*cos(30-CAF)*cos(CAF)=1/2*a*a*(cos(30)+cos(30-2*CAF))->max
максимум выражения достигается при 30-2*CAF=0 => CAF=15
(все углы - в градусах)
Добавлено @ 11:07
у всех прошу прощения, почему-то на каком-то этапе решил, что площадь надо максимизировать

все замечания принимаются...

Автор: NiJazz 27.4.2004, 15:27

Народ, по условию задачи нужно именно прямоугольник искать. Зчем так всё усложнять?

Автор: Akina 27.4.2004, 17:08

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