ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / помогите решить задачу
77 сообщений из 77, показаны все 4 страниц
  все  
помогите решить задачу
    #34198830
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
задача: в простой многоугольник вписать круг наибольшего радиуса..
пожалуйсто, если у кого-то есть какие-нибуди идеи помогите!!!!
...
Рейтинг: 0 / 0
14.12.2006, 10:25
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34198833
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
буду очень благодарна любой подсказке.
ICQ: 251743359
...
Рейтинг: 0 / 0
14.12.2006, 10:26
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34198879
LINUXER
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LINUXER
Участник
уточните что такое простой многоугольник
Я всегда думал, что если в многоугольник можно вписать круг, то только 1
...
Рейтинг: 0 / 0
14.12.2006, 10:35
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34199066
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
LINUXERуточните что такое простой многоугольник
Я всегда думал, что если в многоугольник можно вписать круг, то только 1


Простой многоугольник - замкнутая ломаная без самопересечений. Как следствие, в простом многоугольнике нет 'дыр'.
...
Рейтинг: 0 / 0
14.12.2006, 11:15
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34199116
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Не смущает ли Вас тот факт, что для вписывания окружности многоугольник как минимум обязан быть выпуклым?

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

Итого - читайте учебник Погорелова либо уточняйте постановку задачи.
...
Рейтинг: 0 / 0
14.12.2006, 11:25
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34199139
aleks2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
aleks2
Участник
softwarerНе смущает ли Вас тот факт, что для вписывания окружности многоугольник как минимум обязан быть выпуклым ?

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

Итого - читайте учебник Погорелова либо уточняйте постановку задачи.

Не обязан.
...
Рейтинг: 0 / 0
14.12.2006, 11:30
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34199143
Фотография optimizer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
optimizer
Участник
может под словом "вписать" автор понимает, что круг не должен выходить за многоугольник?
...
Рейтинг: 0 / 0
14.12.2006, 11:30
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200159
LINUXER
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LINUXER
Участник
optimizerможет под словом "вписать" автор понимает, что круг не должен выходить за многоугольник?
да наверно это
невыпуклость многоугогольника усложняет задачу
...
Рейтинг: 0 / 0
14.12.2006, 14:40
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200289
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
LINUXER optimizerможет под словом "вписать" автор понимает, что круг не должен выходить за многоугольник?
да наверно это
невыпуклость многоугогольника усложняет задачу
в том то вся и проблема что многоугольник может быть любым, всмысле и в виде стрелки и как подкова.проблема в том как найти центр этого круга. и получается, что этот круг в трех точках соприкасается с многоугольником. как же найти радиус? может сделать какойто обход по вершинам??
...
Рейтинг: 0 / 0
14.12.2006, 15:08
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200308
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
вот оригинал задания: ( на украинском) коло вписане в простий многокутник.
В заданий простий N-кутник вписати коло найбільшого радіусу.
...
Рейтинг: 0 / 0
14.12.2006, 15:10
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200404
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
aleks2Не обязан.
Обязан. Вписанная окружность обязана касаться каждой из сторон многоугольника, для невыпуклого многоугольника это условие невыполнимо.
...
Рейтинг: 0 / 0
14.12.2006, 15:32
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200452
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
softwarer aleks2Не обязан.
Обязан. Вписанная окружность обязана касаться каждой из сторон многоугольника, для невыпуклого многоугольника это условие невыполнимо.

имеется ввиду не вписананя окружность, а окружность наибольшего радиуса, находящяяся внутри многоугольника.
...
Рейтинг: 0 / 0
14.12.2006, 15:42
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200454
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Ктонибудь определение вписанной окружности для произвольного простого многоугольника может дать?
Я нашёл 2 :
1) Касается всех сторон..
2) Касается прямых содержащих стороны и центр находится внутри.

2 вариант для невыпуклого допустим..
...
Рейтинг: 0 / 0
14.12.2006, 15:42
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200458
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
берем 1 угол, да так, что он обязятельно внутри.
и начинаем разростать окружность до тех пор, пока он куда-нибудь не упрется.
потом берем следующий угол.

все углы - внутренние.

аффтопитезь
...
Рейтинг: 0 / 0
14.12.2006, 15:43
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200463
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Aklinимеется ввиду не вписананя окружность, а окружность наибольшего радиуса, находящяяся внутри многоугольника.
Помоему это только гипотеза :-). Если "имеется ввиду" - то почему не написано так как имеется ввиду??
...
Рейтинг: 0 / 0
14.12.2006, 15:44
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200469
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
ПалестинецКтонибудь определение вписанной окружности для произвольного простого многоугольника может дать?
Я нашёл 2 :
1) Касается всех сторон..
2) Касается прямых содержащих стороны и центр находится внутри.

2 вариант для невыпуклого допустим..
как найти центр круга?
...
Рейтинг: 0 / 0
14.12.2006, 15:46
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200508
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
Aklinберем 1 угол, да так, что он обязятельно внутри.
и начинаем разростать окружность до тех пор, пока он куда-нибудь не упрется.
потом берем следующий угол.

все углы - внутренние.

аффтопитезь
да, но теперь другой вопрос, как это запрограмировать?
...
Рейтинг: 0 / 0
14.12.2006, 15:52
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200554
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
Neeka[quot Aklin]берем 1 угол, да так, что он обязятельно внутри.
и начинаем разростать окружность до тех пор, пока он куда-нибудь не упрется.
потом берем следующий угол.

все углы - внутренние.

аффтопитезь
как мне алгоритм такой в прогу загнать? может еще что-то есть?
...
Рейтинг: 0 / 0
14.12.2006, 16:01
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200734
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
я сразу скажу, что вам нужен будет ну очень неплохой компьютер. т.к. съедать алгоритм будет много премного.

далее.
возьмем расстояние А = максимально удаленные две точки многоуголника.

Для каждой прямой знаем (xa, ya )-(xb, yb)

далее.
для каждой точки многоулгольника (зная обе линии, коими эта вершина образована, позаботится заранее) берем нашу R = A/2 и D = A. Центр - на биссектриссе. расстояние от вершины до центра можно ввести программно (формулу вывести и ввести). Смотрим для каждой прямой, не пересекает ли прямая окружность. это решается. я думая стоит решать в общем виде, а не перебирать точки. (например задать программное уравнение, или условие, пока не решал как именно ) (кстати, по-моему самый толстый момент). Если пересекает хоть одну, то R = R/2. Если нет, то D = D/2, R = R + D. до определенно малого D.

Теперь прикидываем.
[кол-во вершин]*[log( точности D )]

В принципе не так уж и сложно. а вот программить замудохаца.

аффтопитезь
...
Рейтинг: 0 / 0
14.12.2006, 16:45
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34200916
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
2Aklin .
Если решать ту задачу которую ты решаешь(а не автор). то можно вот так:

максимальная окружность содержащаяся в многоугольнике обязана

1) лежать на 3 вершинах с внутренним углом > 90
OR
2) касаться 1 стороны и содержать 2 вершины с внутренним углом > 90
OR
3) касаться 2 сторон и содержать 1 вершину с внутренним углом > 90
OR
4) касаться 3 сторон

итого перебор всех этих случаев по всем вершинам и сторонам многоугольника - O(N^3) операций. но c оч большим простором для оптимизаций и отсеивания заведомо неподходящих случаев..
...
Рейтинг: 0 / 0
14.12.2006, 17:30
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34201003
ну нафига???
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ну нафига???
Гость
Не мучайся!
Учите матчасть.
http://]www.bymath.net/studyguide/geo/sec/geo11.htm
...
Рейтинг: 0 / 0
14.12.2006, 17:50
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34201268
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
Палестинец2Aklin .
Если решать ту задачу которую ты решаешь(а не автор). то можно вот так:

максимальная окружность содержащаяся в многоугольнике обязана

1) лежать на 3 вершинах с внутренним углом > 90
OR
2) касаться 1 стороны и содержать 2 вершины с внутренним углом > 90
OR
3) касаться 2 сторон и содержать 1 вершину с внутренним углом > 90
OR
4) касаться 3 сторон

итого перебор всех этих случаев по всем вершинам и сторонам многоугольника - O(N^3) операций. но c оч большим простором для оптимизаций и отсеивания заведомо неподходящих случаев..

я еще забыл действительно.
если окружность будет на 3 вершинах только, например.
N - колдичество вершин? так это немного. я бы сказал от N^3*log( точность ) до N^3*log( точность )^4
...
Рейтинг: 0 / 0
14.12.2006, 20:08
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34201274
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
ну нафига???Не мучайся!
Учите матчасть.
http://]www.bymath.net/studyguide/geo/sec/geo11.htm

там только про 4х угольники да правильные многоугольники
...
Рейтинг: 0 / 0
14.12.2006, 20:11
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34201328
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
2 Neeka

Скажите пожалуйста, а Вам в этом семестре на лекциях по этому предмету такие слова как "триангуляция Делонэ", "диаграмма Вороного" слышать не приходилось? Есть у меня такое чуЙство, что центр окружности будет лежать либо на одной из граней диаграммы Вороного или в одной из её вершин...
...
Рейтинг: 0 / 0
14.12.2006, 21:03
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34202465
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Палестинец1) лежать на 3 вершинах с внутренним углом > 90
кстати заметил : 180 естественно
...
Рейтинг: 0 / 0
15.12.2006, 11:59
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34204134
Пользователь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пользователь
Участник
Палестинец2Aklin .
Если решать ту задачу которую ты решаешь(а не автор). то можно вот так:

максимальная окружность содержащаяся в многоугольнике обязана

1) лежать на 3 вершинах с внутренним углом > 90
OR
2) касаться 1 стороны и содержать 2 вершины с внутренним углом > 90
OR
3) касаться 2 сторон и содержать 1 вершину с внутренним углом > 90
OR
4) касаться 3 сторон

итого перебор всех этих случаев по всем вершинам и сторонам многоугольника - O(N^3) операций. но c оч большим простором для оптимизаций и отсеивания заведомо неподходящих случаев..
Как определить - точка (внутри/или снаружи) многоугольника?
(без этого вроде не решить задачу)
...
Рейтинг: 0 / 0
15.12.2006, 17:40
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34204262
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Как определить - точка (внутри/или снаружи) многоугольника?

Произвольный луч (например вдоль X) пущенный из точки пересекает стороны нечётное кол-во раз.
...
Рейтинг: 0 / 0
15.12.2006, 18:20
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34204393
aleks2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
aleks2
Участник
softwarer aleks2Не обязан.
Обязан. Вписанная окружность обязана касаться каждой из сторон многоугольника , для невыпуклого многоугольника это условие невыполнимо.

Это кто сказал?
...
Рейтинг: 0 / 0
15.12.2006, 19:38
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34204474
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
aleks2 softwarer aleks2Не обязан.
Обязан. Вписанная окружность обязана касаться каждой из сторон многоугольника , для невыпуклого многоугольника это условие невыполнимо.

Это кто сказал?

определение вписанной окружности

но в данном случае надо только разместить окружность наибольшего радиуса внутри многоугольника
...
Рейтинг: 0 / 0
15.12.2006, 20:42
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34206057
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
Aklinя сразу скажу, что вам нужен будет ну очень неплохой компьютер. т.к. съедать алгоритм будет много премного.

далее.
возьмем расстояние А = максимально удаленные две точки многоуголника.

Для каждой прямой знаем (xa, ya )-(xb, yb)

далее.
для каждой точки многоулгольника (зная обе линии, коими эта вершина образована, позаботится заранее) берем нашу R = A/2 и D = A. Центр - на биссектриссе. расстояние от вершины до центра можно ввести программно (формулу вывести и ввести). Смотрим для каждой прямой, не пересекает ли прямая окружность. это решается. я думая стоит решать в общем виде, а не перебирать точки. (например задать программное уравнение, или условие, пока не решал как именно ) (кстати, по-моему самый толстый момент). Если пересекает хоть одну, то R = R/2. Если нет, то D = D/2, R = R + D. до определенно малого D.

Теперь прикидываем.
[кол-во вершин]*[log( точности D )]

В принципе не так уж и сложно. а вот программить замудохаца.

аффтопитезь

да, по поводу програмирования - замудохаца. Смысл мне ясен.Как теперь реализовать это? Не подскажете алгоритм, если можно по-подробней... я не знаю как запрограмировать вышеуказанное. Может есть какой-то вариант по-проще... ПЛЗ!!
...
Рейтинг: 0 / 0
17.12.2006, 22:25
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34206102
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
aleks2 softwarer
Обязан. Вписанная окружность обязана касаться каждой из сторон многоугольника , для невыпуклого многоугольника это условие невыполнимо.

Это кто сказал? http://gimn177.ekburg.ru/view.php?ID=30&slink=ref&main=2
...
Рейтинг: 0 / 0
17.12.2006, 23:35
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34206219
aleks2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
aleks2
Участник
S.G. aleks2 softwarer
Обязан. Вписанная окружность обязана касаться каждой из сторон многоугольника , для невыпуклого многоугольника это условие невыполнимо.

Это кто сказал? http://gimn177.ekburg.ru/view.php?ID=30&slink=ref&main=2

Гимназии нынче уже не те...

исходная постановка>> задача: в простой многоугольник вписать круг наибольшего радиуса..

Не требует касания всех сторон.
...
Рейтинг: 0 / 0
18.12.2006, 06:42
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34206952
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
maXmo
Участник
это уже не вписанная окружность, а впихнутая.
...
Рейтинг: 0 / 0
18.12.2006, 12:22
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34207353
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
можно алгоритм пожалуйсто... плз!!!!!
...
Рейтинг: 0 / 0
18.12.2006, 13:51
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34208742
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Если я правильно понял автора Aklin, он утверждает что центр искомой окружности будет лежать на биссектрисе угла при одной из вершин многоугольника. Если моё понимание того что предложено правильно, то предлагаю проделать следующее:

1.Берем квадрат.
2.Вписываем в него окружность.
3.Отрезаем у квадрата вершины так, чтобы линии отреза не пeресекали и не касались вписанной окружности.
4.Проверяем гипотезу о том, что центр окружности лежит на бессиктрисе.
...
Рейтинг: 0 / 0
18.12.2006, 19:58
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34209489
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
mikhail_nЕсли я правильно понял автора Aklin, он утверждает что центр искомой окружности будет лежать на биссектрисе угла при одной из вершин многоугольника. Если моё понимание того что предложено правильно, то предлагаю проделать следующее:

1.Берем квадрат.
2.Вписываем в него окружность.
3.Отрезаем у квадрата вершины так, чтобы линии отреза не пeресекали и не касались вписанной окружности.
4.Проверяем гипотезу о том, что центр окружности лежит на бессиктрисе.
причем здесь квадрат?? мне круг надо в простой многоугольник вписать..
...
Рейтинг: 0 / 0
19.12.2006, 10:10
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34209821
mikolas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikolas
Участник
А с какой точностью необходимо дать ответ задачи? Мне кажется что без методов оптимизации здесь не обойтись, но тогда возникает угроза попасть в локальный минимум, нужно будет придумать условие где начать поиск.
...
Рейтинг: 0 / 0
19.12.2006, 11:30
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34209878
mikolas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikolas
Участник
Что-то в ICQ-у к тебе не могу достучаться, Neeka.
...
Рейтинг: 0 / 0
19.12.2006, 11:43
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211431
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
2 Neeka

Ну видите ли, Aklin предложил некий метод решения Вашей проблемы основанный (если я правильно его понял) на предположении о том, что центр искомой окружности будет лежать на биссектрисе угла при одной из вершин многоугольника. Вы сказали:

Смысл мне ясен.

Очевидно, что данное утверждение не верно в случае невыпуклого многоугольника. Мой простой пример с квадратом демонстрирует что данное утверждение неверно и в случае выпуклого многоугольника, т.е. оно не верно вообще. Вот и всё.
...
Рейтинг: 0 / 0
19.12.2006, 19:11
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211450
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
mikhail_n
3.Отрезаем у квадрата вершины так, чтобы линии отреза не пeресекали и не касались вписанной окружности.
4.Проверяем гипотезу о том, что центр окружности лежит на бессиктрисе.
Вы что не договорили про отрезание вершин.
Я повернул квадрат на 45 градусов и новым квадратом отрезал 4 вершины.
Центр продолжает лежать на биссектрисах.
...
Рейтинг: 0 / 0
19.12.2006, 19:21
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211464
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
сорри, новые линии будут касаться
...
Рейтинг: 0 / 0
19.12.2006, 19:28
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211477
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
повернуть квадрат на 45 градусов и увеличить сторону след. квадрата, так чтобы она оставалась меньше диагонали предыдущего квадрата. Взять пересечение квадратов. В полученный восьмиугольник нельзя вписать больший круг, а на биссектрисах центр окружности не лежит.
...
Рейтинг: 0 / 0
19.12.2006, 19:34
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211586
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Вообщем, думаю, чисто алгоритм поднять дня за два реально, я так посидел, посмотрел на эту задачу в течении часа - вообщем, по-моему, предётся лазить по всем сторонам и искать окружность макс. радиуса, касающуяся рассматриваемой в данный момент стороны и невыходящую за пределы многоугольника. В случае выпуклого многоугольника особых проблем не вижу, для невыпуклого у меня ещё есть ряд неясных моментов чисто с точки зрения численной реализации (ну там кусочно-линейная граница на противоположной стороне в общем случае будет разрывной - не физически конечно, но с точки зрения алгоритма). Думаю, реально построить алгоритм трудоёмкостью O(N*lnN), ну в худшем случае О(N^2). Однако это всё слова, слова, слова. Реально по соотношению (личный безкорыстный творческий интерес)/(трудоёмкость) с моей скромной точки зрения эта задача за пределами тех на которые стоит безвозместно тратить время и силы. Хотя, конечно, можно какую-нибудь наукообразную эвристику слепить по-быстрому, эта да, но это не так интересно.
...
Рейтинг: 0 / 0
19.12.2006, 21:03
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211611
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
тема намбер два:

радиус = максимально удаленные две точки/4
дельта = максимально удаленные две точки/2

первоначально надо найти центр *
* например ввести сетку и найти максиамальный удаление точки от краев (хотя бы по 8 углам, лучше больше)

смотрим, пересекает ли хто-нибудь (им отрезков)** данную окружность. далее если пересекает, то если перескает сверху, то пробуем пройти на дельта (для каждого направления рукурсия отдельно) вниз, влево, вверх. и вправо.
если все же пересекает,то уменьшаем радиус на дельта.
если не пересекает, то увеличиваем.
дельта = дельта/2.
если точность дельта достингута, екзит.

** - сложнуй случай - хорда

приложение - реально сложный случай

аффтопитезь
...
Рейтинг: 0 / 0
19.12.2006, 21:29
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211612
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
аффтопитезь
...
Рейтинг: 0 / 0
19.12.2006, 21:29
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211614
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
конечно же

Aklin
радиус = максимально удаленные две точки/2
дельта = максимально удаленные две точки/4


как вывод: максиальный радиус - почти две максимально удаленный точки.
вот только центр надо бы найти верно.

аффтопитезь
...
Рейтинг: 0 / 0
19.12.2006, 21:31
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211617
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
по поводу пересекает ли отрезок окружность: товарищи, так это математика:

аффтопитезь
...
Рейтинг: 0 / 0
19.12.2006, 21:35
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34211993
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
mikhail_nВообщем, думаю, чисто алгоритм поднять дня за два реально, я так посидел, посмотрел на эту задачу в течении часа - вообщем, по-моему, предётся лазить по всем сторонам и искать окружность макс. радиуса, касающуяся рассматриваемой в данный момент стороны и невыходящую за пределы многоугольника.
Ещё раз намекну что эт тоже самое что рассматривать все тройки из вершин и сторон и пытатся вписать в них окружность. проверяя каждую окружность на нахождение внутри многоугольника.
алгоритм без лишних оптимизаций - элементарнейший.
...
Рейтинг: 0 / 0
20.12.2006, 08:57
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34212812
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
Палестинец mikhail_nВообщем, думаю, чисто алгоритм поднять дня за два реально, я так посидел, посмотрел на эту задачу в течении часа - вообщем, по-моему, предётся лазить по всем сторонам и искать окружность макс. радиуса, касающуяся рассматриваемой в данный момент стороны и невыходящую за пределы многоугольника.
Ещё раз намекну что эт тоже самое что рассматривать все тройки из вершин и сторон и пытатся вписать в них окружность. проверяя каждую окружность на нахождение внутри многоугольника.
алгоритм без лишних оптимизаций - элементарнейший.

это действительно при условии, что конеецчная окружность касается именно 3х сторон.
но выше было опровергнуто, ибо окружность может лежать на трех вершинах, например.
...
Рейтинг: 0 / 0
20.12.2006, 12:44
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34212843
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Aklinэто действительно при условии, что конеецчная окружность касается именно 3х сторон.
но выше было опровергнуто, ибо окружность может лежать на трех вершинах, например.

рассматривать все тройки из вершин и сторон
...
Рейтинг: 0 / 0
20.12.2006, 12:50
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34212887
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
Палестинец рассматривать все тройки из вершин и сторон

поправка: рассматривать все комбинации
Код: plaintext
1.
2.
3.
{f1, f2, .... fk }
 3 <=k<= 2 *n 
fi - {вершина || ребро}
считая при этом фигуру, образованную данными элеметами (хотя бы) выпуклым многоугольником.
...
Рейтинг: 0 / 0
20.12.2006, 12:58
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34213286
Пользователь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пользователь
Участник
Aklin Палестинец рассматривать все тройки из вершин и сторон

поправка: рассматривать все комбинации
Код: plaintext
1.
2.
3.
{f1, f2, .... fk }
 3 <=k<= 2 *n 
fi - {вершина || ребро}
считая при этом фигуру, образованную данными элеметами (хотя бы) выпуклым многоугольником.
вроде любая тройка уже задаст окружность,
другое дело - как определить, что окружность не вывалилась за многоугольник?
...
Рейтинг: 0 / 0
20.12.2006, 14:17
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34213322
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
Пользователь Aklin Палестинец рассматривать все тройки из вершин и сторон

поправка: рассматривать все комбинации
Код: plaintext
1.
2.
3.
{f1, f2, .... fk }
 3 <=k<= 2 *n 
fi - {вершина || ребро}
считая при этом фигуру, образованную данными элеметами (хотя бы) выпуклым многоугольником.
вроде любая тройка уже задаст окружность,
другое дело - как определить, что окружность не вывалилась за многоугольник?

не любая тройка однозначно задаст окружность. (см. пример выше, тройка без вершины не дает результат)
в принципе хватит и троек + итерационный метод.
итого - 2*N*log( точности )
...
Рейтинг: 0 / 0
20.12.2006, 14:22
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34213417
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
maXmo
Участник
Aklin(см. пример выше, тройка без вершины не дает результат)угу вот у меня тоже ученики так: нарисуют равнобедренный треугольник, а потом говорят: «Из рисунка видно, что треугольник равнобедренный» -_-
...
Рейтинг: 0 / 0
20.12.2006, 14:43
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34213669
Пользователь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пользователь
Участник
Aklinне любая тройка однозначно задаст окружность
А пример привести ("см. выше" - непонятно - куда смотреть)
...
Рейтинг: 0 / 0
20.12.2006, 15:33
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34214097
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Aklin
не любая тройка однозначно задаст окружность. (см. пример выше, тройка без вершины не дает результат)
В примере вроде видно что даёт :-).
По трём сторонам однозначно строится окружность которая их касается -
если толька все три не параллельны. случай 3 парралельных нам и не нужен.

другое дело - как определить, что окружность не вывалилась за многоугольник?
см. выше в постах.
центр окружности в многоугольнике и не одна сторона не пересекает окружность..
(касаться может > 3 сторон естественно).
...
Рейтинг: 0 / 0
20.12.2006, 17:20
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34214386
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Согласен с Палестинцем.

в принципе хватит и троек + итерационный метод.
итого - 2*N*log( точности )

Не согласен. Во-первых, метод просто точный, т.е. положение и радиус окружности находятся точно при переборе, о каких итерациях идёт речь? Во-вторых, уже для выпуклого многоугольника трудоёмкость при таком подходе O(N*(N^2 + O(1)*N)), т.е. O(N^3), откуда возьмётся N*log(точности??) непонятно.
...
Рейтинг: 0 / 0
20.12.2006, 19:04
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34214401
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
mikhail_nположение и радиус окружности находятся точно при перебореа как быть, когда количество решений бесконечно? например - прямоугольник
...
Рейтинг: 0 / 0
20.12.2006, 19:09
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34214413
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
А в этом случае алгоритм найдёт конечное число решений (в случае прямоугольника два по концам), вот и всё, могу легко продемонстрировать. Вам как пользователю останется лишь выбрать то, которое Вам больше нравится.
...
Рейтинг: 0 / 0
20.12.2006, 19:16
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34214579
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
mikolasЧто-то в ICQ-у к тебе не могу достучаться, Neeka.
незнаю. попробуй еще раз 251743359
...
Рейтинг: 0 / 0
20.12.2006, 20:54
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34215025
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
mikhail_nА в этом случае алгоритм найдёт конечное число решений (в случае прямоугольника два по концам), вот и всё, могу легко продемонстрировать. Вам как пользователю останется лишь выбрать то, которое Вам больше нравится.
Я думаю должна нравиться окружность с максимальным радиусом :-)

Во-вторых, уже для выпуклого многоугольника трудоёмкость при таком подходе O(N*(N^2 + O(1)*N)), т.е. O(N^3),

N^2 + O(1)*N .. - умножить наверно надо..

Все тройки это O(N^3). проверка для каждой тройки на расположение окружности в многоугольнике - O(N). Итого : O(N^4).

Всё остальное похоже - нетривиальная оптимизация.(одну из идей оптимизации могу предложить такую, что в основном скажем уже по 2 сторонам (+ направление нормалей сторон) можно отсеять большинство неподходящих случаев (по расположению там или максимально возможному радиусу окружности для этих 2 сторон) и не подбирать к этим 2 - третий элемент)
...
Рейтинг: 0 / 0
21.12.2006, 09:11
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34215036
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Палестинец mikhail_nА в этом случае алгоритм найдёт конечное число решений (в случае прямоугольника два по концам), вот и всё, могу легко продемонстрировать. Вам как пользователю останется лишь выбрать то, которое Вам больше нравится.
Я думаю должна нравиться окружность с максимальным радиусом :-)

а. ну да - про прямоугольник же речь.. тогда да - выбирай себе любой :-)
...
Рейтинг: 0 / 0
21.12.2006, 09:18
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34215071
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
а если решать с помощью диаграмы Вороного? может кто подскажет алгоритм?
...
Рейтинг: 0 / 0
21.12.2006, 09:39
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34215109
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Neekaа если решать с помощью диаграмы Вороного? может кто подскажет алгоритм?
Я могу подсказать алгоритм..
Забиваешь на этот курс. это похоже не для тебя ..
и идёшь в колледж на эконом..
через пару лет становишься уважаемым и богатым специалистом.
и нахрен не надо будет никаких диаграмм..
...
Рейтинг: 0 / 0
21.12.2006, 09:54
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34216817
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
пример где по трем не построишь.
итерации: см. пример. без итераций не добится того, что окружность попадет на вершину.

про количество решений: действительно для прямоугольника только 2. а этого и хватит.
а вот для идиото-гольника (это как N звезда с квадратами на концах) и то будет конечное количество. (вершин и ребер - то ограничено)

проверка всех троек - это N*(N-1)*(N-2)
а точность все равно будет, тогода еще *log( точность ), а также для каждой точности надо проверить остальные (N-3) вершин, итого

log(точности) - количество итераций
__
O(N*(N-1)*(N-2)*log(точности)*(N-3)) =
__
O(A 4 N*log(точности)) ~ (имхо) 32N 4


аффтопитезь
...
Рейтинг: 0 / 0
21.12.2006, 17:19
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34217159
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
ПалестинецN^2 + O(1)*N .. - умножить наверно надо..

Не, умножать не надо. Имелось ввиду что в выпуклом многоугольнике окружность может касаться только по сторонам. Поэтому для каждой отдельно взятой стороны строим N - 1 биссектрис углов, образованных данной стороной и остальными N - 1 сторонами, если какая-либо сторона параллельна данной, то в качестве биссектрисы берем прямую параллельную
обоим и находящуюся от них на равных расстояниях. В общем случае эти N - 1 биссектрис пересекутся в (N - 1)*(N - 2)/2 точках. Для каждой из этих точек пресечения проверим что 3 перпендикуляра из данной точки пересечения двух биссектрис на три стороны, которыми образованы два рассматриваемых угла, попадают внутрь этих трёх сторон. Это O(N^2) операций. После этого отсева у нас останется O(1) точек которые удовлетворают данному условию. Эти оставшиеся точки проверяем на условие не выхода за пределы многоугольника, итого ещё O(1)*O(N) операций. В результате для N шагов имеем N*(O(N^2) + O(1)*O(N)) или O(N^3).

Neekaа если решать с помощью диаграмы Вороного? может кто подскажет алгоритм?

Да забудьте Вы Вороного, внимательно читайте этот пост, здесь уже для Вас эту задачу решили, если Вы этого не понимаете, то всё дальнейшее бесполезно... На всякий случай скажу вот это:

1.Для ЛЮБЫХ трёх непересекающихся отрезков на плоскости можно определить существует или нет окружность которая будет касаться всех трёх. Для этого существуют точные аналитические формулы. Далее, если такая окружность существует, то она единственна и положение её центра и её радиус можно точно определить. Для этого существуют точные аналитические формулы.

2.Для ЛЮБЫХ двух непересекающихся отрезков и точки на плоскости можно определить существует или нет окружность которая будет касаться двух отрезков и проходить через точку. Для этого существуют точные аналитические формулы. Далее, если такая окружность существует, то она единственна и положение её центра и её радиус можно точно определить. Для этого существуют точные аналитические формулы.

3.Для ЛЮБОГО отрезка и двух точек на плоскости можно определить существует или нет окружность которая будет касаться отрезка и проходить через обе точки. Для этого существуют точные аналитические формулы. Далее, если такая окружность существует, то она единственна и положение её центра и её радиус можно точно определить. Для этого существуют точные аналитические формулы.

4.Для ЛЮБЫХ трёх точек на плоскости... ну это знают все дети.

Aklinпример где по трем не построишь.

А Вы, я смотрю, продолжаете упорствовать. Тогда обратите внимание на пункт 2 выше.
...
Рейтинг: 0 / 0
21.12.2006, 19:26
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34219913
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
mikhail_n
А Вы, я смотрю, продолжаете упорствовать. Тогда обратите внимание на пункт 2 выше.


2.Для ЛЮБЫХ двух непересекающихся отрезков и точки на плоскости можно определить существует или нет окружность которая будет касаться двух отрезков и проходить через точку. Для этого существуют точные аналитические формулы. Далее, если такая окружность существует, то она единственна и положение её центра и её радиус можно точно определить. Для этого существуют точные аналитические формулы.

обоснуйте
...
Рейтинг: 0 / 0
22.12.2006, 19:24
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34219926
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
и вот это пожалуйста то же. (пример)

окружность - три степени свободы. в 2д пространстве.

точка - 2, точка - 2, прямая - 1 -> 5 похоже две точно можно
точка - 2, прямая - 1, прямая - 1 -> 4 две точно можно
прямая - 1, прямая - 1, прямая - 1 -> 3 !!!

это могу прокоментирвать:точка - 2, точка - 2, точка - 2 = 6
так: степеней свободы надо бы кратно трем чтобы было.


аффтопитезь
...
Рейтинг: 0 / 0
22.12.2006, 19:30
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34219932
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
ну да, точка, точка, точка - 3 !!!

аффтопитезь
...
Рейтинг: 0 / 0
22.12.2006, 19:32
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34220055
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Что ж, Вы правы, для случая одной точки и двух отрезков и двух точек и отрезка замените:

Далее, если такая окружность существует, то она единственна и положение её центра и её радиус можно точно определить...

на

Далее, если такая окружность существует, то их может быть не более 2х и положение их центров и радиусы можно точно определить...

С точки зрения алгоритма это мало что меняет, на одну проверку для каждого шага больше, только и всего.
...
Рейтинг: 0 / 0
22.12.2006, 21:10
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34223745
Дементьев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дементьев
Гость
Шеймас, Препарата с.362 или ч-з Диаграмму Воронного
Помогите теперь и Вы мне. В заданный звездный N-угольник вписать прямоугольник максимальной площади.
Что-то эта задача не сводится к ЗЛП.
...
Рейтинг: 0 / 0
25.12.2006, 21:27
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34223747
Дементьев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дементьев
Гость
2 moderator: Прошу прощения, переместите часть последнего сообщения в новую тему или удалите.
...
Рейтинг: 0 / 0
25.12.2006, 21:29
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34226450
Neeka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Neeka
Гость
где ее взять? книгу эту?? у тебя есть?? принеси на пары...
...
Рейтинг: 0 / 0
26.12.2006, 23:00
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34962547
Антонина
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Антонина
Участник
Помогите составить уравнение! В двузначном числе цифра единиц втрое меньше цифры десятков. Если это число разделить на три и к результату прибавить 8, то получится двузначное число, записанное теми же цифрами, взятыми в обратном порядке. Найдите заданное двузначное число.
...
Рейтинг: 0 / 0
23.11.2007, 21:58
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34962913
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
(3*x*10 +x)/3+8 = (x*10+3*x)
...
Рейтинг: 0 / 0
24.11.2007, 13:27
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34963235
teras
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
teras
Гость
Антонина wrote:
> Помогите составить уравнение! В двузначном числе цифра единиц втрое
> меньше цифры десятков. Если это число разделить на три и к результату
> прибавить 8, то получится двузначное число, записанное теми же цифрами,
> взятыми в обратном порядке. Найдите заданное двузначное число.

Зачем уравнение? "В двузначном числе цифра единиц втрое меньше цифры
десятков" -> есть три варианта: 31, 62, 93.
После деления на при и сложения получается двузначное число -> исходное
число делится на три нацело. Значит - 93.
Проверяем - 93/3+8=39.

Уравнение: число x = 10a+b; y = 10b+b; a=3b; здесь a - цифра десятков, b
- цифра единиц. Из условия задачи имеем x/3+8 = y;

Имеем систему уравнений относительно двух неизвестных:
|(10a+b)/3+8 = 10b+a
|a=3b

Разберемся с первым:
10a+b = 30b+3a-24
10a-3a=30b-24-b
7a=29b-24

подставим второе:
21b=29b-24
8b=24
b=3

Из второго уравнения имеем a=9
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
24.11.2007, 19:09
| Ответить | Цитировать | Написать  
помогите решить задачу
    #34963379
friend
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
friend
Участник
господи. по сабжу. неужели в 2006 году было плохо с инетом? поиск в гугле сразу
дает решение .
...
Рейтинг: 0 / 0
24.11.2007, 23:54
| Ответить | Цитировать | Написать  
77 сообщений из 77, показаны все 4 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / помогите решить задачу
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1345684]:
 0ms
get settings:
 9ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 167ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 60ms
get tp. blocked users:
 1ms
others: 243ms
total:  510ms
созд. / загр.: 510ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]