Диаметр окружности, вписанной в многоугольник

← →
Doom © (2003-05-19 23:43) [0]

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

← →
int64 © (2003-05-20 00:30) [1]

> может быть даже не выпуклым

> Поскажите, с какой стороны заходить.

А вот с не выпуклой стороны и заходи.

← →
nikkie © (2003-05-20 01:09) [2]

не во всякий многоугольник можно вписать окружность. в невыпуклый - точно нельзя.

← →
Думкин © (2003-05-20 05:24) [3]

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

← →
JohnnyJ © (2003-05-20 10:02) [4]

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

← →
Lord Warlock © (2003-05-20 10:18) [5]

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

← →
Doom © (2003-05-20 10:22) [6]

Возражения принимаю.
Уточняю задачу.
Даны координаты замкнутого многоугольника, причем необязательно выпуклого.
Найти окружность МАКСИМАЛЬНОГО диаметра, вписанную в этот многоугольник.

← →
JohnnyJ © (2003-05-20 10:34) [7]

> Найти окружность МАКСИМАЛЬНОГО диаметра, вписанную в этот
> многоугольник.

IMHO, если в многоугольник можно вписать окружность, то она единственна и неповторима для данного многоугольника.

← →
AlexKniga © (2003-05-20 10:38) [8]

Помню такую задачу на олимпиаде решал.

Уточнение
Нужно найти окружность МАКСИМАЛЬНОГО диаметра, НЕ пересекающую стороны этого многоугольника, т.е. касающуюся его сторон и не обязательно всех. (расположенную внутри этого мн-ка)

← →
sosv (2003-05-20 11:52) [9]

Попробуй зайти отсюда
Препарата, Шеймос, "Вычислительная геометрия"

← →
Андрей (2003-05-20 14:30) [10]

Похожую задачу решал на олимпиаде в школе. Нужно использовать векторное произведение векторов (сторон многогранника). Если сильно надо - могу поискать...

← →
Doom © (2003-05-20 17:38) [11]

> AlexKniga © (20.05.03 10:38)

Совершенно верно

> Помню такую задачу на олимпиаде решал.

Если решил, поделись мыслями.

> sosv (20.05.03 11:52)
> Попробуй зайти отсюда
> Препарата, Шеймос, "Вычислительная геометрия"

Что за препарата?

> Андрей (20.05.03 14:30)

Надо сильно, дружище

← →
AlexKniga © (2003-05-20 19:30) [12]

Doom © (20.05.03 17:38)
Это школьна олимпиада году эдак в 91.
Помню что решил (правда не самым оптимальным методом), а как ужо забыл.

Препарата это фамилия одного из авторов книги.

← →
Думкин © (2003-05-21 06:47) [13]

> AlexKniga © (20.05.03 10:38)
Это должен был сделать задатчик вопроса. Зачем игрушку ломаешь? :-)

> Doom © (20.05.03 17:38)
> > AlexKniga © (20.05.03 10:38)
Совершенно верно

Телепатов нет. Я тебя и просил о точности вопроса. А теперь медленно и по-порядку задай его вновь.

Берем f(x,y) - функция от точки, которая показывает расстояние до ближайшей стороны. Ищем максимум внутри многоугольника. Вопросы есть?

> Центр вписанной окружности лежит на пересечении перпендикуляров,
> восстановленных из середин сторон.

Это для описанной. Вписанной - на пересечении биссектрис.

Угу. Кусочно-гладкая. Только если численно решать, то оно пофигу.

Диаметр окружности, вписанной в многоугольник Найти похожие ветки