Всем здрасте!
Подскажите алгоритм.
Нужно найти простую фигуру минимальной площади, охватывающей две другие

Цитата

простую фигуру

поконкретнее надо описать класс подходящих фигур
тогда уже можно что-то думать...

Прстой фигурой можно считать произвольный треугольник, четырехугольник, круг и элипс.

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

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

есть два возможных варианта решения этих задач:
1. аналитический
2. численный

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

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

Есть такая вещь, как рекурсивный алгоритм заливки области. В самом общем виде выглядит таким образом:

Код

DrawPixel(int x, int y) {  while (/* покрыли ли мы всё ) */)  {    DrawPixel (x + 1, y);    DrawPixel (x + 1, y + 1);    DrawPixel (x, y);    DrawPixel (x, y + 1);  } }

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

Это сообщение отредактировал(а) val - 22.11.2004, 10:47

Цитата

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

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

Цитата

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

Согласан. Тогда, скажем так, что центр тяжести будем искать с какой-то дельтой относительно вычисленного. Все случаи, конечно, не покрыть, но для стандартного набора расположений подойдёт...

Это сообщение отредактировал(а) val - 22.11.2004, 14:11

Всем огромное спасибо за предложенные идеи!
А можно ведь те две произвольны фигуры задать так:
Создать файл с набором некоторых точек, считать их произвольно а затем соеденить прямыми линиями (по некоторому правилу). Ведь можно разбить любую фигуру на отрезки?
И еще эти две фигуры не пересекаются.

Joni, но так нет гарантии, что полученная фигура будет правильной...

Что-то я совсем запутался уже.
А что же является ПРАВИЛЬНОЙ фигурой.
По моему любую фигуру можно охватить простой (НЕ описать)
Или я что-то недопонимаю?!

Цитата

Создать файл с набором некоторых точек, считать их произвольно а затем соеденить прямыми линиями

Просто не совсем понятно, по какому закону соединять прямыми линиями?

А я вообще нефига не понял из ваших базаров. Кстати, вопросик у меня. У четырёхугольника один из углов может быть больше 180 градусов? Или нет.

Цитата

А я вообще нефига не понял из ваших базаров. Кстати, вопросик у меня. У четырёхугольника один из углов может быть больше 180 градусов? Или нет.

Да, например 30 градусов может соответвовать 360 + 30 = 390 градусам...

А чтобы решить данную задачу, может для начала нужен алгоритм задания исходных фигур.

Цитата(val @ 25.11.2004, 16:34)

Да, например 30 градусов может соответвовать 360 + 30 = 390 градусам...

А может 330 градусам?

Описываем эллипс и треугольник

Цитата(maxim1000 @ 21.11.2004, 19:56)

2. минимальный четырехугольник

Берем минимальные значения x и y (y отчет сверху) у этих двух фигур за левую верхнюю точку прямоугольника и
максимальные значения x и y (y отчет сверху) у этих двух фигур за правую нижнюю точку прямоугольника. Этот прямоугольник и есть самый маленький по площади.

Цитата(maxim1000 @ 21.11.2004, 19:56)

1. минимальный треугольник

Находим треугольники которые зажимают (как розовый треугольник на картинке) обе фигуры, так, чтобы нельзя было ее повернуть. Их будет четыре, как я понял. Один из них я сконструировал подвинув диагональ до окружности круга, а потом повернув ее вокруг окружности пока линия не коснулась второй фигуры. Также можно сконструировать и другие три треугольника. Самый маленький по площади и будет думаю ответом... но не уверен.
Вот мои соображения по этому поводу

Присоединённый файл ( Кол-во скачиваний: 2 )
 zad_alg.jpg

val, четырёхугольник может быть не выпуклым? (не знаю как правильно сказать)

Цитата

val, четырёхугольник может быть не выпуклым? (не знаю как правильно сказать)

Да. Вот пример невыпуклого четырёхугольника...

Код

/\                                       /  \                                      /    \                                     /      \                                    /   /\   \                                   /  /    \  \                                  / /        \ \                                 //            \\                                /                \

Добавлено @ 10:29
Пришлось воспользоваться тегом для кода, чтобы картинка не испортилась...

Это сообщение отредактировал(а) val - 26.11.2004, 10:28

val Может ты не понял. Это перефразировка моего вопроса об угле больше 180 градусов.

А полученный прямоугольник не бедет ведь наименьшим четырехугольником?
Тогда нужно искать четырк точки: верх-низ и лево-право.

Кстати, Cardinal, на чем вы реализовали данный алгоритм?

Цитата(Guest @ 26.11.2004, 22:35)

полученный прямоугольник не бедет ведь наименьшим четырехугольником?

Кстати о птичках... Ты прав... Что делать... Наверно нумерически решать придется, то есть касательные к крайним точкам вертеть и смотреть на результат.

Цитата(Guest @ 26.11.2004, 22:35)

Кстати, Cardinal, на чем вы реализовали данный алгоритм?

Начем? Не знаю... Сидел, сидел и придумал Но эту фишку с треугольниками еще доказать надо...

Вот засада!
Мысль насчет четырех крайних точках не в счет. Ведь можно получить случаи
отсечения заданных фигур.

Cardinal, рисунок вы в графичем редакторе нарисовали?

Цитата(Joni @ 27.11.2004, 18:15)

Ведь можно получить случаи отсечения заданных фигур.

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

Цитата(Joni @ 27.11.2004, 18:15)

Cardinal, рисунок вы в графичем редакторе нарисовали?

Можно на ты Да, зашел в paint и нарисовал Так попонятней просто должно быть, что я имел в виду...

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

Цитата(Joni @ 27.11.2004, 18:47)

четырехугольников

А вообще четырехугольник с прямыми углами или нет?

Необязательно.
Можно рассматривать любой четырехугольник.

Val вы говорили:
Есть такая вещь, как рекурсивный алгоритм заливки области
Итак зальем данные фигуры, но ведь они не будут простыми

Joni, то что предложил val не прокатит... Зальется офигенная площадь, а не минимальная Таким образом нельзя задать нормально условия, чтобы рекурсия правильно закончилась... Тем более что у val ошибки в том, что он написал.
Надо было по крайней мере так написать:

Код

DrawPixel(int x, int y) { while (/* покрыли ли мы всё ) */) {   DrawPixel (x + 1, y);   DrawPixel (x, y + 1);   DrawPixel (x - 1, y);   DrawPixel (x, y - 1); } }

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

Ладно... Смотрим на картинку и не пугаемся

У нас два объекта, в этом примере это будет треугольник и "почтикруг"
Залиты они или нет разницы не имеет (если я ошибаюсь, то поправьте меня ) Поэтому мы их заливаем. Как? Без разницы, тут пока не в эффективности дело. Берем и заливаем рекурсивно, как до этого было описано начиная с любой внутренней точки объекта (например центр круга).
Теперь есть две формулы, по которым мы получим x и y координату точки равновесия (центр тяжести). На картинке попытался объяснить кто такие xi и yi. Это координаты каждой точки Pi, которая пренадлежит той или иной фигуре (какой без разницы). Gi эта сила, которая давит на каждую точку. Здесь все силу равны поэтому все Gi = 1, то есть сумма Gi просто равна кол-ву точек. Ну короче я сейчас подумал, что все вообще просто становится Сверху в стоит просто сумма xi (или yi), т.к. все Gi = 1. Ну и остается поделить сумму всех координат точек по оси x на кол-во точек и получить xs. Точно также: сумма всех координат точек по оси y поделенная на кол-во точек обоих фигур (уже посчитали раньше) даст ys. Точка S(xs|ys) и будет центром тяжести...

О... Идея
Половина того, что написано выше делать не надо То есть делаем все также, но фигуры не заливаем. Меньше точек - быстрее посчитается, а результат будет тем же.

Действуй.

Присоединённый файл ( Кол-во скачиваний: 1 )
 schwerp.jpg

А не овал ли будет с наименьшей площадью?

Пока думаю что нет
А потом Joni это все реализует и нам расскажет

А если сопряжение по двум противоположным сторонам элипса не одинвакове?

~FoX~, пока не понял о чем ты... Нарисуй картинку как я и попробуй объяснить

Пока все еще думаю, что круг будет

По поводу простых фигур (треугольник, четырех угольник, эллипс)
Если мы описали минимальный треугольник, вокруг двух фигур может быть случай, когда углы треугольника полностью совпадают с одной из фигур. Правда это очень крайний случай. На столько невероятный, как и крайний случай четырех угольника, у которого одна из строн имеет длину 0.
В остальных случаях, мы можем провести касательную, к одной из вписанных фигур, которая отделит свободный угол треугольника. В результате мы получим четырехугольник меньшей площади, чем треугольник, который описывает те же фигуры.
ВЫВОД: Площадь минимального четырехугольника не меньше, чем площадь минимального треугольника, описывающих две другие фигуры.

PS В общем виде задача настолько сложна, что её еще не решили академики. Поэтому нужно все таки начать с нормальной постановки задачи

Всем огромное спасибо за предложенные идеи.
Я уже пытаюсь только вникать. :-)
Вот и пытаюсь на Pascal построить окружность.


Да задачу вроде еще не решили. Но ведь пытаться надо.