ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вписывание многоугольника
25 сообщений из 111, страница 2 из 5
  2  все
Вписывание многоугольника
    #34187365
Алексей Вк.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Вк.
Гость
Эх знал бы я так математику.....
Если не найдется аналитическое решение, придется делать численное. Никуда не денешься.
Или методом перебора с заданным шагом :-)))))
...
Рейтинг: 0 / 0
08.12.2006, 20:16:48
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34187381
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Алексей Вк.углы между сторонами максимальныМожет, сумма углов?
если нет, то квадрат будет более приоритетен, чем ромб при равной сумме углов?
...
Рейтинг: 0 / 0
08.12.2006, 20:30:43
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34187388
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Алексей Вк.Эх знал бы я так математику.....
Если не найдется аналитическое решение, придется делать численное. Никуда не денешься.
Или методом перебора с заданным шагом :-)))))

Ну численный то я тебе сразу предложу..
строишь окружность радиуса R0 - откладываешь ломанную по окружности из сторон многоугольника (это всегда можно сделать).
вычисляешь из расстояния между конечными точками - на сколько необходимо уменьшить радиус (или увеличить)..
Например :
R1 = R0 - D / 2PI. ( надо подумать ещё!)

Метод должен сходится стопудов!


зы. между прочим отсюда похоже следует что для любого значения сторон существует и единственен с точностью до поворота вписаный в окружность многоугольник. и площадь его максимальна
...
Рейтинг: 0 / 0
08.12.2006, 20:38:32
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34187408
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Мне все таки кажется, что можно это решить без перебора.

В итоговом многоугольнике, каждая из сторон многоугольника является хордой к описывающей окружности. Значит окружность можно разбить на кучу секторов с одинаковым радиусом и задаными длинами хорд. А дальше, зная что длина хорды относится к углу 2*R*sin(a/2) получаем систему с одним уравнением для каждого из исходных отрезков:
Код: plaintext
1.
2.
3.
4.
L1 = 2*R*sin(A1/2)
L2 = 2*R*sin(A2/2)
L3 = 2*R*sin(A3/2)
....
Ln = 2*R*sin(An/2)
Где Li это длины исходных отрезков, Ai это углы секторов а R - радиус общий для всех секторов. Получаем систему из i уравнений с i+1 неизвестными. Но если теперь вспомнить что сумма всех углов должна дать в итоге 360 градусов и добавить это уравнение в систему - получим вполне простую систему которую уже можно решить традиционными методами. Причем полностью решать необязательно, достаточно вычислить R.
Потом (для определенности) кладем один из отрезков на координатную ось и зная радиус (и возможно углы) посторить окружность и вписаный в нее многоугольник плевое дело.
...
Рейтинг: 0 / 0
08.12.2006, 21:01:07
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34187414
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Ну численный то я тебе сразу предложу..
строишь окружность радиуса R0 - откладываешь ломанную по окружности из сторон многоугольника (это всегда можно сделать).
вычисляешь из расстояния между конечными точками - на сколько необходимо уменьшить радиус (или увеличить)..
Например :
R1 = R0 - D / 2PI. ( надо подумать ещё!)

Метод должен сходится стопудов!

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

Эх знал бы я так математику.....
Если не найдется аналитическое решение, придется делать численное. Никуда не денешься.
Или методом перебора с заданным шагом :-)))))

В свете Ваших последних признаний, то что Вы запостили вначале не совсем эквивалентно тому, что Вы на самом деле ищите (может и эквивалентно, но это не очевидно и, вообще говоря, надо доказывать). Если хотите, я могу сбросить систему уравнений к которым приведет вариационная постановка задачи, но предупреждаю, она будет также нелинейной и будет выглядеть ещё пострашнее, чем в случае с окружностью, так что от итерационных методов решения систем нелинейных алгебраических уравнений Вам, похоже, никуда не деться. Xотя, чёрт его знает, например до открытия дифференциального/интегрального исчисления был такой оригинал (кажется Гюйгенс), так он некоторые задачи, кот. теперь решаются при помощи диффуров умудрялся решать без этих прибамбасов. Так что never say never!
...
Рейтинг: 0 / 0
08.12.2006, 21:14:40
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34187416
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Мне все таки кажется, что можно это решить без перебора.

Но если теперь вспомнить что сумма всех углов должна дать в итоге 360 градусов и добавить это уравнение в систему - получим вполне простую систему которую уже можно решить традиционными методами.

Осталась мелочь - найти традиционный НЕИТЕРАЦИОННЫЙ метод решения нелинейных алгебраических уравнений.
...
Рейтинг: 0 / 0
08.12.2006, 21:20:30
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34187417
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Не должен. В основе лежит неверная посылка что длина хорды зависит от радиуса окружности линейно, что справедливо для длины дуги окружности. Если бы это было бы так, то задача решалась бы аналитически в три действия.

Блин, имел ввиду от угла сектора конечно. От радиуса то как раз линейно.
...
Рейтинг: 0 / 0
08.12.2006, 21:23:49
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34187437
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Так, чтобы застолбить приоритет - задача с окружностью кажется действительно решается аналитически в три действия...

Продолжение следует...
...
Рейтинг: 0 / 0
08.12.2006, 21:47:17
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34187443
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
Э..., нет. Май бед.
...
Рейтинг: 0 / 0
08.12.2006, 21:51:40
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34189062
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Продолжу численную идею в таком варианте..
(см. рисунок1)

P - сторона.
Считаем углы при вершине -> P^2 = R^2 - 2R^2 COS(A)
A = arccos((R^2 - P^2)/(2 R^2))

Далее.. сумма углов для вписанного многоугольника на рисунке должна быть равна 2PI (когда начальные и конечные точки совпадут)

F(R) = SUM(arccos((R^2 - P^2)/(2 R^2)))

Решаем
F(R) = 2 * PI методом ньютона или его модификациями (в принципе даже знаем функцию производную в точке)

Найденный R и есть искомый. (Площадь элементарно из радиуса описаной окружности считается)

Проблема N1: Существует много решений. (см. рис 2) => для ньютона R0 надо попасть в локальную область вокруг искомого R.

Проблема N2:
Если центр описаной лежит вне многоугольника - надо решать уравнение
F(R) - 2 * Amax = 0 (Amax - угол напротив большей стороны)

воть. строго алгоритма разрешающего эти 2 проблемы предложить пока не могу.

(рис.1):
...
Рейтинг: 0 / 0
11.12.2006, 09:20:08
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34189066
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
рис.2 :
...
Рейтинг: 0 / 0
11.12.2006, 09:21:10
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34189070
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
рис.3
...
Рейтинг: 0 / 0
11.12.2006, 09:21:53
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34189075
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
сори. пропали индексы из за тега [ i ] :-)

F(R) = SUM(arccos((R^2 - P(i)^2)/(2 R^2))) - где P(i) длина i-той стороны. сумма по всем сторонам.
...
Рейтинг: 0 / 0
11.12.2006, 09:23:41
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34189161
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Кстати
mikhail_n Начальное приближение для R - Sum(di)/(2*pi).
Совсем не факт, что попадём в окрестность сходимости метода Ньютона к искомому решению..
...
Рейтинг: 0 / 0
11.12.2006, 09:57:22
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190083
Алексей Вк.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Вк.
Гость
У меня родилась новая формулировка задачи :-)

Т.к. действительно может быть немало случаев когда многоугольник и не впишешь, и не опишешь. То можно переформулировать. Мне нужно чтобы все стороны многоугольника описали фигуру, максимально близкую к кругу. ИМХО это условие выполняется когда каждая сторона является касательной к окружности, причем радиус окружности для каждой стороны может быть свой.
Вот рисунок:
...
Рейтинг: 0 / 0
11.12.2006, 13:32:49
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190108
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Алексей Вк.У меня родилась новая формулировка задачи :-)А можно поинтересоваться практическим смыслом этой задачи? Алексей Вк.может быть немало случаев когда многоугольник и не впишешьПримерчик можно? что-то не могу такого представить...
...
Рейтинг: 0 / 0
11.12.2006, 13:37:55
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190111
Алексей Вк.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Вк.
Гость
А вот теперь вопрос - как будет выглядеть сиcтема уравнений для такого случая?
И реально ли ее решить вообще?
...
Рейтинг: 0 / 0
11.12.2006, 13:38:05
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190144
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Алексей Вк.У меня родилась новая формулировка задачи :-)Кстати, эта формулировка ничем не отличается от вписывания многоугольника в окружность и, соответственно, имеет то же решение.
...
Рейтинг: 0 / 0
11.12.2006, 13:46:00
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190153
Алексей Вк.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Вк.
Гость
miksoft Алексей Вк.У меня родилась новая формулировка задачи :-)А можно поинтересоваться практическим смыслом этой задачи? Алексей Вк.может быть немало случаев когда многоугольник и не впишешьПримерчик можно? что-то не могу такого представить...
Поинтересоваться можно - мне нужно описать проекцию траектории движения тела в трехмерном пространстве по оси Z :-)

Попросту говоря - есть траектория движения тела по оси Z на разных участках, у нас етсь проекция этого движения на плоскости под ним. Траектория состоит из прямолинейных участков. Причем траектория движения в области x-y не представляет из себя интереса. Нужно произвести визуализацию этого процесса. Для упрощения траектория движения замыкается и сворачивается в круг - проблема именно в этом моменте. Можно было бы траекторию описывать вдоль прямой, но это не то. Ведь процесс повторяющийся. Задача в общем-то научная, так что здесь свои особенности. И поэтому у меня есть проекции - длины прямолинейных участков на плоскости x-y. Теперь требуется их расположить в требуемом порядке и по возможности наиболее близко к круговой фрме для наилучшего обзора процесса. По полученным углам я уже без проблем построю траекторию в пространстве.

А насчет примера невозможности - так я же его и нарисовал - в данном случае одна из сторон (наименьшая) не будет касаться окружности, если предположить, что радиус у нее жестко задан. Причем ни описывающей окружности (или же пострадают другие стороны), ни вписанной.
...
Рейтинг: 0 / 0
11.12.2006, 13:47:17
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190174
Алексей Вк.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Вк.
Гость
Жуть получается:


sin(ai/2)=(li/2)/ri
...
sum(ai)=2*pi

Или

sum( arcsin(li/(2*ri)) )=2*pi

Зато хорошо подходит почти для любого многоугольника.
...
Рейтинг: 0 / 0
11.12.2006, 13:51:47
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190242
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
miksoft Алексей Вк.У меня родилась новая формулировка задачи :-)Кстати, эта формулировка ничем не отличается от вписывания многоугольника в окружность и, соответственно, имеет то же решение.Это я не совсем прав. Формулировка будет идентичной, только если радиусы на рисунке делят стороны на две равные части.
...
Рейтинг: 0 / 0
11.12.2006, 14:09:24
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190307
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Алексей Вк.Нужно произвести визуализацию этого процесса.Так для визуализации не нужно особой точности. Все равно точнее, чем плюс-минус полпискселя не нарисуешь на экране. А приблизительно (3-4 значащих знака) можно и итерационно решить за вполне приемлемое время, имхо.
...
Рейтинг: 0 / 0
11.12.2006, 14:23:33
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190893
LINUXER
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LINUXER
Участник
Алексей Вк.У меня родилась новая формулировка задачи :-)

Можно поинтересоваться откуда они берутся=))
и предполагают ли они разумное обоснование
зачем каждой стороне свою окружность?
Кажется это самый неправдоподобный критерий, к тому же есть целые множества фигур, удовлетворяющих начальным условиям
например все равносторонние четырёхугольники

Первая часть задачи как раз определить правдоподобный критерий "стремления к окружности"
...
Рейтинг: 0 / 0
11.12.2006, 16:37:08
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34190916
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
maXmo
Участник
Алексей Вк.Для упрощения траектория движения замыкается и сворачивается в круга окружность обязательно до полного замыкания доводить?
...
Рейтинг: 0 / 0
11.12.2006, 16:41:43
| Ответить | Цитировать | Написать  
Вписывание многоугольника
    #34191106
Алексей Вк.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Вк.
Гость
Я вот думаю - в процессе решения задачи последний отрезок можно конечно принудительно приводить к заданному значению. Но это тогда потребует тщательного подбора исходных данных для решения задачи - а это уже не совсем научный подход, во всяком случе не для целей визуализации.

Насчет каждой стороны - а ИМХО будут проблемы со сторонами, котореы ну никак не захотят вписываться. Поэтому данный подход наверное наиболее корректный. Но - n+1 уравнений и 2n неизвестных. Где-то еще должны быть уравнения описывающие последний вариант. Вот только не могу понять что именно они должны связывать?
...
Рейтинг: 0 / 0
11.12.2006, 17:24:34
| Ответить | Цитировать | Написать  
25 сообщений из 111, страница 2 из 5
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вписывание многоугольника
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=34187443&tid=1343600]:
 0ms
get settings:
 8ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 1477ms
get topic data:
 14ms
get forum data:
 3ms
get page messages:
 87ms
get tp. blocked users:
 2ms
others: 210ms
total:  1823ms
созд. / загр.: 1823ms
x
x
Закрыть


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