|
Действия ...
Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
07.12.2006, 20:53:08
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
Может кто подскажет алгоритм. Имеем многоугольник - неравносторонний, замкнутый - у на сесть только длина каждой из сторон. Ниужно его вписать в круг. Т.е. найти радиус круга и координаты вершин в декартовой системе координат. Условие вписываемости выполняется (длина любой стороны не превышет суммарную длину всех остальных сторон). ИМХО это что-то стандартное должно быть, но мне никогда не встречалось. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
07.12.2006, 21:22:29
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
Вас обманули, Условие вписываемости выполняется (длина любой стороны не превышет суммарную длину всех остальных сторон). есть условие не "вписываемости", а существования замкнутого многоугольника. Успехов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
07.12.2006, 21:55:18
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
Да, по-сути: пусть даны n сторон d1,d2,...dn, R - искомый радиус, a1,a2,...an - углы при вершинах соответствующих секторов. Имеем нелинейную систему из n + 1 уравнения: 2*R*sin(ai/2) = di, i = 1,...n Sum(ai) = 2*pi для n + 1 неизвестного R,ai. Лично мне было бы не влом кракнуть эту системку численно Ньютоном, т.к. моя личная библиотека линейных солверов у меня под рукой. Ну а как Вы будете выкручиваться - дело Ваше, хотя может кто и предложит аналитическое решение... Успехов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
07.12.2006, 22:13:24
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
Алексей Вк.Может кто подскажет алгоритм. Имеем многоугольник - неравносторонний, замкнутый - у на сесть только длина каждой из сторон. Ниужно его вписать в круг. Т.е. найти радиус круга и координаты вершин в декартовой системе координат. Условие вписываемости выполняется (длина любой стороны не превышет суммарную длину всех остальных сторон). ИМХО это что-то стандартное должно быть, но мне никогда не встречалось. Ну.. если это - треугольник - задача тривиальна. Вспоминаем геометрию. Во всех остальных случаях, ваша фигура имеет бесконечное количество положений веришин, а следовательно найти одно решение вписанного многоугольника мне не представляется возможным. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
07.12.2006, 23:37:19
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
Алексей Вк....у нас есть только длина каждой из сторон... ок. Давайте все по порядку. У нас есть длина каждой из сторон, следовательно мы знаем сколько всего сторон у этого многоугольника. Полюбому условие вписываемости - сумма длин всех сторон должна быть меньше длины самого круга. Алексей Вк....Т.е. найти радиус круга... Мне приходит на ум только методом перебора делать. Вычислить начальный радиус круга (длина круга = сумме длин всех сторон, затем из длины выражаем радиус), затем последовательно откладывать каждый из отрезков, концы которых будут на границе окружности. Если конец последнего отрезка не совпадет с началом первого - уменьшать радиус. Но Вы пока это дебажить будете, рак башки схватите . Алексей Вк....и координаты вершин в декартовой системе координат... А тут уж извините, я могу вращать как угодно вписанный многоугольник и при этом координаты будут изменяться, а многоугольник при этом останется вписанным. P.S.: У меня такое предположение, что задача поставлена некорректно. Не хватает исходных данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 00:09:25
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
Задача поставлена корректно. Да, безусловно, существует бесконечное множество выпуклых замкнутых многоугольников, вокруг которых невозможно описать окружность. Это очевидно. Поэтому в общем случае задача НЕ имеет решения. Тем не менее, если для заданного набора длин сторон решение существует, то заданных условий достаточно для однозначного определения радиуса описанной окружности. Всё. Всё остальное определяется с точностью до двух аффинных преобразований: произвольного сдвига начала координат и поворота системы коопдинат на произвольный угол. Мне приходит на ум только методом перебора делать. Вычислить начальный радиус круга (длина круга = сумме длин всех сторон, затем из длины выражаем радиус), затем последовательно откладывать каждый из отрезков, концы которых будут на границе окружности. Если конец последнего отрезка не совпадет с началом первого - уменьшать радиус. Но Вы пока это дебажить будете, рак башки схватите... По моей методике это будет делать метод Ньютона, уверяю Вас, если решение существует, то с точностью до 0.000...01 Ньютоном оно найдется за 5 - 6 итераций. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 01:47:28
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
mikhail_nЗадача поставлена корректно. Не совсем. Думаю, пропущено условие "многоугольник является выпуклым/несамопересекающимся (любое из этих условий сгодится)". При этом условии, а также при условии нахождения всех вершин на окружности - согласен с Вашим решением. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 02:15:26
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
Если только предположить, что все точки лежат на окружности, тогда решение существует. Честно говоря, уже поздно и голова у меня щас не варит, но рискну предположить, что необходима система уравнений, связывающая площади круга, треугольников лежащих на радиусах, секторов и сегментов. (слабеющей рукой рисую общий случай для 4 точек, и пошел спать) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 03:52:46
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
softwarerНе совсем. Думаю, пропущено условие "многоугольник является выпуклым/несамопересекающимся (любое из этих условий сгодится)" Нет, любое не сгодится, только выпуклый, вокруг невыпуклого описать окружность невозможно. Несамопересекающийся может быть невыпуклым. Вообще то ловить меня надо было на этом пассаже: Да, безусловно, существует бесконечное множество выпуклых замкнутых многоугольников, вокруг которых невозможно описать окружность. Это очевидно. Поэтому в общем случае задача НЕ имеет решения. Из одного другого не следует: e.g. квадрат vs ромб. В связи с этим есть у меня чуйство что для любого набора длин сторон решение существует и единственно, под решением понимается выпуклый многоугольник. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 10:37:43
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
Так - похоже я неправильно сформулировал задачу. В общем - многоугольник выпуклый, непересекающийся. Требуется ..... а я теперь и не знаю что требуется :-)) Давайте сначала. У меня есть массив, содержащий стороны многоуольника - их длины. Мне надо найти их координаты, при условии что результат получится в виде выпуклого многоугольника, стремящегося по своей форме к кругу. Самый простой метод, кторый мне пришел в голову - вписать многоугольник в круг. Конечно часть вершин на стороны круга не попадет, но мне это не критично. Кажется есть другой вариант - не вписать многоугольник в круг - а круг в многоугольник. Это точно возможно для любого выпуклого непересекающегося многоугольника. Причем обеспечить максимум радиуса круга. Это наверное будет проще. Итерационные численные методы в моем случае использовать нежелательно. Ищу аналитическое решение. Хотя я вот сейчас думаю..... А может есть более простой вариант - через углы между сторонами? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 10:37:44
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
mikhail_nНет, любое не сгодится, только выпуклый, вокруг невыпуклого описать окружность невозможно. Да ладно Вам :) См. ниже. mikhail_nВ связи с этим есть у меня чуйство что для любого набора длин сторон решение существует и единственно, под решением понимается выпуклый многоугольник. Я же так и сказал: при соблюдении пары дополнительных условий я согласен с Вашим решением. Действительно, должно быть именно так (это следует из логики нарисованной Вами системы и того факта, что функция Sum(ai) монотонна по R. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 10:57:45
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
Пусть такая окружность существует. Тогда верно: Центр окружности = точка пересечения прямых проведеных через середины сторон перпендикулярно оным. Это вытекает из того факта что все стороны описываемого многоугольника - хорды. Следовательно треугольник <центр окружности> - <концы хорды> равнобедренный, а значит биссектриса и высота совпадает. Уравнение прямой y=Ax + B0 (А и В0 определяются по координатам вершин многоугольника) перпендикулярная к ней: y=-(1/A)x + B1 (А берется из предыдущего уравнения, В1 - из условия прохождения через середину) Для примера, есть отрезок X1,Y1 - X2,Y2 Tогда A = (Y2-Y1)/(X2-X1) B0 определяется из условия что при x=X1 -> y=Y1 Середина отрезка точка: x=(X2+X1)/2, y=(Y1+Y2)/2 --------------------- 1 Для любых двух сторон находим уравнения перпендикуляров и решаем систему из этих 2 уравнений. Решение = предполагаемый центр окружности. 2 Проверяем расстояние до всех вершин. Расстояние от центра до всех вершин должно быть одинаковое = радиусу. Если расстояние разное - такой окружности не существует. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 11:11:37
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
Это Для Описывающей окружности ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 11:17:11
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
Алексей Вк.У меня есть массив, содержащий стороны многоуольника - их длины. Мне надо найти их координаты, при условии что результат получится в виде выпуклого многоугольника, стремящегося по своей форме к кругу. ... Ищу аналитическое решение. Философский вопрос: что такое "стремящийся к кругу"? :) Как глядя на два варианта многоугольников определить кто из них больше стремится? Решение будет зависить от "функции" задающей степень "стремления". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 11:20:14
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
Интересно. Надо будет попробовать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 11:21:17
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
NotGonnaGetUs Алексей Вк.У меня есть массив, содержащий стороны многоуольника - их длины. Мне надо найти их координаты, при условии что результат получится в виде выпуклого многоугольника, стремящегося по своей форме к кругу. ... Ищу аналитическое решение. Философский вопрос: что такое "стремящийся к кругу"? :) Как глядя на два варианта многоугольников определить кто из них больше стремится? Решение будет зависить от "функции" задающей степень "стремления". Тот - в который можно вписать круг большего радиуса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 12:19:14
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
golsaПусть такая окружность существует. Тогда верно:...... То, что Вы написали, само по себе верно, но решать эту задачу таким способом Вы немного замучаетесь. golsa1 Для любых двух сторон находим уравнения перпендикуляров и решаем систему из этих 2 уравнений. Не проясните ли следующий момент: как найти уравнения перпендикуляров, зная длины всех сторон и ничего более? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 12:40:59
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
Я вот тут подумал над самым первым вариантом: sin(ai/2)=(li/2)/r ... sum(ai)=2*pi Попробуем так: sum( arcsin(li/(2*r)) )=2*pi Если отсюда вынести r - то все элементарно решается. Но я не могу найти ни одну подходящую формулу - как вынести из arcsin любой аргумент: arcsin(a*b)=??? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 18:50:22
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
Никак. Поздравляю, Вы свели мою систему к одному нелинейному уравнению. Теперь вычислительная сложность реализации метода Ньютона вообще децкая (хотя я бы так делать не стал если требуется алгоритм для произвольного числа сторон). Начальное приближение для R - Sum(di)/(2*pi). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 19:11:06
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
Ну не совсем никак, вот здесь есть формула для суммы: http://www.emis.de/journals/SMZ/2004/05/1022.pdf Но мне нужно умножение. Где бы его взять??? Или действительно взять уравнение Ньютоном? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 19:44:13
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
Алексей Вк.Так - похоже я неправильно сформулировал задачу. В общем - многоугольник выпуклый, непересекающийся. Требуется ..... а я теперь и не знаю что требуется :-)) Давайте сначала. У меня есть массив, содержащий стороны многоуольника - их длины. Мне надо найти их координаты, при условии что результат получится в виде выпуклого многоугольника, стремящегося по своей форме к кругу. Самый простой метод, кторый мне пришел в голову - вписать многоугольник в круг. Конечно часть вершин на стороны круга не попадет, но мне это не критично. Кажется есть другой вариант - не вписать многоугольник в круг - а круг в многоугольник. Это точно возможно для любого выпуклого непересекающегося многоугольника. Причем обеспечить максимум радиуса круга. Это наверное будет проще. Итерационные численные методы в моем случае использовать нежелательно. Ищу аналитическое решение. Хотя я вот сейчас думаю..... А может есть более простой вариант - через углы между сторонами? 1) Как вписать многоугольник в круг - Перебираем все тройки вершин. строим окружность по 3 точкам (описаную вокруг треугольника) Выбираем окружность максимального радиуса - она является минимальной покрывающей окружностью. 2)Мне надо найти их координаты, при условии что результат получится в виде выпуклого многоугольника, стремящегося по своей форме к кругу. Так. Переформулирую: Для всех многоугольников с данными сторонами найти тот наибольшее количество вершин которого расположены на одной окружности(?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 19:48:25
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
Тот - в который можно вписать круг большего радиуса. Эквивалентно - среди многоугольников с задаными сторонами выбрать с наибольшей площадью. Опять же мне кажется - может быть бесконечно неконгруэнтных вариантов ответа. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 19:50:47
|
|||
|---|---|---|---|
Вписывание многоугольника |
|||
|
#18+
Алексей Вк.Мне надо найти их координаты, при условии что результат получится в виде выпуклого многоугольника, стремящегося по своей форме к кругу.Т.е. многоугольник не жесткий, а "шарнирный"? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 19:59:52
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
miksoft Алексей Вк.Мне надо найти их координаты, при условии что результат получится в виде выпуклого многоугольника, стремящегося по своей форме к кругу.Т.е. многоугольник не жесткий, а "шарнирный"? Именно шарнирный - у меня не заданы углы между сторонами. Поэтому и нет их координат. Т.е. если еще раз переформулировать - найти такое расположение сторон, при котором углы между сторонами максимальны, такой многоугольник будет стремиться к кругу (если конечно соблюдать равномерность, а не делать один угол максимальным, а все остальные как получится). Или по-другому - надо найти эти самые углы (собственно их я и ищу - т.к. использовтаь буду именно их, радиус постольку поскольку - он легко находится и нужен скорее для определения сколько площади займет вся эта конструкция :-) и то грубо, точное значение радиуса не требуется). Поэтому любые варианты предполагающие наличие координат у сторон многоугольника не подходят. Я как раз координаты и ищу (будут углы - а координаты из них элементарно и сразу в декартовой, если произвольно задать координаты любой стороны). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
08.12.2006, 20:13:29
|
|||
|---|---|---|---|
|
|||
Вписывание многоугольника |
|||
|
#18+
2Алексей Вк. ещё раз. вот твоя задача: среди многоугольников с задаными сторонами найти с наибольшей площадью. решение не знаю - копать по ключевым словам вариационная задача лагранжа.изопериметрическая задача. задача дидоны. истина где-то там :-) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=16&mobile=1&tid=1343600]: |
0ms |
get settings: |
7ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
87ms |
get topic data: |
27ms |
get forum data: |
2ms |
get page messages: |
64ms |
get tp. blocked users: |
1ms |
| others: | 229ms |
| total: | 438ms |
| 0 / 0 |
