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

Цитата

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

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

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

тогда это уже пять задач:
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