Скачать: CL | DM;

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

← →
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)
Совершенно верно

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

---

← →
Иван Шихалев ©   (2003-05-21 08:28) [14]

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

---

← →
Иван Шихалев ©   (2003-05-21 08:31) [15]

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


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

---

← →
Думкин ©   (2003-05-21 10:23) [16]

> Иван Шихалев © (21.05.03 08:28)

Хорошо б так. Вопросов нет - реализуй.

---

← →
Иван Шихалев ©   (2003-05-21 10:31) [17]

> Думкин © (21.05.03 10:23)


Не люблю рутинный кодинг. Разве что за деньги.

---

← →
Думкин ©   (2003-05-21 11:09) [18]

> Иван Шихалев © (21.05.03 10:31)

Вот и я про тоже - рутины там будет. Она же веселой будет функция твоя.

---

← →
Иван Шихалев ©   (2003-05-21 11:32) [19]

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.49 MB
Время: 0.014 c