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

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