Геометрическая проблема

[Amed]

Дано:
На плоскости есть 8 отрезков, соединенных последовательно, так что конец предыдущего является началом следующего. Их вершины обозначим A, B, C, D, E, F, G, H, I.
Заданы величины AB, BC, ..., HI - длины отрезков и расстояние AI. AI < AB+BC+...+HI, то есть задача принципиально не неразрешимая. Для простоты можно положить, что координаты точки A (0;0).
Задача:
Необходимо узнать все возможные варианты взаимного расположения отрезков, причем расстояние между любыми двумя вершинами отрезков не может быть меньше некоторой величины X.

Как посоветуете действовать?
Простой перебор (вложенные циклы по углу поворота i-го отрезка с проверкой поставленных условий) крайне нецелесообразен.

[Amed]

Поправка. Необходимо узнать хотя бы некоторые варианты взаимного расположения отрезков.

[alibek]

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

[Amed]

Предположим, этот рисунок - решение задачи.
Изначально были заданы только точка A, расстояния AI и AB..HI. Расстояния между точками не меньше некоторого X.



Сформулирую по-другому. Мне надо разложить последовательно 8 палочек заданной длины, чтобы начало первой было в точке A, а конец последней - в точке I, которая расположена в произвольной точке на заданном расстоянии от точки A (на окружности радиусом AI). Пересекаться палочки могут, но расстояние между вершинами не меньше X.

[alibek]

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

[alibek]

Ответ: число вариантов = бесконечность.

[alibek]

А, остальные отрезки имеют заданную длину?
Все-равно, у тебя имеется семизвенный механизм, число степеней свободы большое.

Нужно аналитическое решение?

[Amed]

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

У меня есть практическая задача, я свел ее к теоретической. Из полученных, скажем, 100 вариантов решения я выберу более подходящее.

[alibek]

Думать не хочется
Но давай попробую.

Итак, есть восемь отрезков определенной длины, и заданы координаты первой и последней точки.

Координаты точки A -- (0;0).
Координаты точки B определяются уравнением Xb^2 + Yb^2 = Lab^2 (частный случай, т.к. точка A лежит в начале координат), т.е. лежат на окружности радиусом AB с центром в точке A.
Координаты точки C определяются уравнением (Xc-Xb)^2 + (Yc-Yb)^2 = Lbc^2, причем Xb и Yb это не скалярные значение, а множество из прошлого решения.
Координаты точки D определяются уравнением (Xd-Xc)^2 + (Yd-Yc)^2 = Lcd^2, причем координаты Xc и Yc опять таки являются всей областью предыдущего решения.
...
Координаты точки H определяются уравнением (Xh-Xg)^2 + (Yh-Yg)^2 = Lgh^2, опять таки, Xg и Yg берется как область предыдущего решения.
Координаты точки I определяются уравнением Xi^2 + Yi^2 = Lai^2, т.к. расстояние Lai определено условием.
Т.е. надо найти общую область решений (Xi;Yi) и (Xh;Yh).
Завтра, когда будет нормальный инет, попробую поискать уравнения таких "окружностей на окружности", помню даже, что у них название специальное есть.

[alibek]

Yb = ±SQR(Lab^2 - Xb^2), где Xb = -Lab...+Lab
Yc = ±SQR(Lbc^2 - (Xc-Xb)^2) + Yb, где Xc = Xb-Lbc...Xb+Lbc, Xb = -Lab...+Lab, а Yb подставляется из прежнего уравнения.
Yd = ±SQL(Lcd^2 - (Xd-Xc)^2) + Yc; Xd = Xc-Lcd...Xc+Lcd, Xc = Xb-Lbc...Xb+Lbc, Xb = -Lab...+Lab
...
Ну и так далее, до Yh
Потом в Yh и Xh подставляешь выражения по цепочке вверх и решаешь систему из двух уравнений (второе будет для точки I, точка на окружности вокруг A радиусом Lai).

[Amed]

alibek, твои рассуждения я прекрасно понимаю, иначе уравнения взаимоположений и не составить.

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

Ведь если тупо вращать первый отрезок в цикле на 360° по 1°, затем во втором цикле второй на 360° по 1° и так далее, проверяя в седьмом цикле, совпал ли конец последнего отрезка с точкой I, будет проходов. Величины такие, что точности в 1° наверняка не хватит, хорошо бы вдвое меньше, но тогда совершенно космические .

Проблема в том, что расстояния у меня такие, что ломаная может быть с углами между соседними сторонами >180°, поэтому сократить сектор в 360° не получается.

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

[alibek]

А зачем тебе семь вложенных циклов?
Вначале приведенное уравнение на бумаге составь, а потом уже будет видно, на чем можно упростить.

[Amed]

*/me визжит как резаный*

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

[alibek]

Вот что я подразумевал под "упростить".
В данном примере использовано 5 точек (вместо 9), областью решения являются цвета, соответственно, синий, циановый, зеленый, желтый, красный.
Синий (окружность в центре) -- это область решений точки B. Циановый -- (круг побольше) -- это область решений точки C. Если бы расстояние BC было меньше AB более чем в два раза, то в середине цианового круга была бы "дырка", т.е. это был бы не круг, а "бублик". Но это расстояние не меньше, поэтому циановый круг заполняет полностью.
Зеленый круг -- это область решений точки D, желтый -- область решений точки E. Как видишь, область решений точки E представляет собой круг (не окружность) радиусом Lab+Lbc+Lcd+Lde. Чаще всего так и будет, тебе достаточно лишь проверять исходные данные на этот частный случай (т.е. чтобы первый отрезок был не больше, чем двойная длинна всех остальных отрезков).
Красная окружность -- область решений точки F. Т.к. она полностью входит в желтый круг, то это означает, что таких решений бесконечное множество.

[alibek]

P.S. Впрочем, есть еще один вариант решить эту задачу
Ну-ка, дети, хором: Ап-про-кси-ма-тор!

[Amed]

Ничего не понял.
На рисунке круги волнистые )))))
Оно и понятно, в час ночи и круги волнистые.

А идея хороша. Предлагаю новый флеш-моб.
Ап-про-кси-ма-тор!

[Amed]

На всякий случай донесу до масс свою исходную задачу.

У меня есть зубчатая передача из 8 пар колес (тут на рисунке четыре пары, но суть та же). Светлый круг - колесо, темный - шестерня. Точка - ось. (вид сверху). Следующее колесо зацепляется с предыдущей шестерней.

У меня есть отверстие в некой поверхности, в него вставляется первая ось

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

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

При этом то, как именно будут располагаться линии, соединяющие остальные 8-2=6 осей, мне не так важно.

[alibek]

Я тут подумал, и решил, что задачу можно упростить
Геометрическим местом точки N (N=1...8 для точек B...H) будет круг радиусом R=SUM(Li;i=1...n) с центром в точке A, за исключеним круга радиусом (L1-SUM(Li;i=2...n-1)-Ln) с центром в точке A. Если радиус второго круга получится меньше нуля (т.е. SUM(Li;i=2...n-1)<L1+Ln), то значит его игнорируем.
Уравнения тогда не такими громоздкими будут и их можно будет решить.

[Ennor]

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

У меня есть подозрение, что данное условие раньше не принималось в расчет. Ибо рисунок, приведенный тобой по ссылке в этом же посте, оказывается неправильным - колесо 2 задевает ось 3. Я понимаю, что это зависит от конкретных радиусов, и что в данном случае иначе просто не сделать, но - как тогда? Видимо, условие придется как-то переформулировать.

Соответственно, могу предложить алгоритм получения гарантированно рабочей комбинации. Она может быть крайне неоптимальна с точки зрения размеров агрегата в целом, но зато будет работать. Суть его в том, что мы выстраиваем соединения на прямой линии до тех пор, пока расстояние от оси 1 до очередной оси не превышает максимально допустимое расстояние. Когда это происходит, мы прокатываем неуместившееся колесо (пусть это будет ось k) по оси k - 1 до тех пор, пока расстояние от О1 до Оk не будет равно заданному в условию расстоянию между первой и последней осями (AI в твоем изначальном посте).
После этого все остальные оси от k + 1 до n включительно мы располагаем на окружности, описанной вокруг оси 1 с радиусом AI. Та самая, на которой уже лежит ось k.

Не самый пристойный вариант, не спорю: в общем случае количество осей может оказаться таким, что при откладывании отрезков k+ 1, ... n будет сделано более одного полного круга вокруг оси 1. В этом случае придется использовать максимально общий вариант расстановки, который я в данный момент пытаюсь вербализовать. Покамест безуспешно...

[Amed]

Ennor, ты не совсем прав, данное условие о незадевании шестернями осей мной не было озвучено, потому что в первой, оторванной от практики, постановке вопроса расплылось бы на абзац. Я предполагал отфильтровать из полученных 100 (1000, 10000) решений ложные двумя циклами и ифом. Наверняка осталось бы 10 (100, 1000) верных решений, из которых я бы выбрал наивернейшее для моей ситуации.

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

[Ramzes]

alibek
Amed
В геометрии не силен, но помочь могу
Ап-про-кси-ма-тор!

[Ennor]

Я вот только не понял - тебе нужно аналитическое решение в общем виде или заточка под конкретные условия (8 осей, диаметры небось заданы...)?

[Approximator]

Если серьёзно я вообще не очень понял, что именно нужно узнать автору топика.

Если говорить про первоначальную постановку, то Alibek не совсем прав, в плоскости точки не лежащие на одной прямой ВСЕГДА на окружности будут лежать только три точки.

Насколько я понимаю, необходимо расположить центры (симметрии) шестерней в трёхмерном пространстве. У нас восемь шестерней. Известно, что ЛЮБЫЕ четыре точки не лежащие в одной плоскости ВСЕГДА лежат на сфере. Таким образом уравнение местоположения центров симметрии восьми шестерней в общем случае это уравнения двух сфер и одной окружности - на окружности должны лежать центры сфер и одно из точек их пересечения.

(конечно можно взять ещё более общий случай - любые девять точек в трёхмерном пространстве будут лежать на поверхности, образованной вращением кривой второго порядка , правда сомневаюсь, что Amed'у захочется решать эту задачу через это место )

В принципе для решения задачи должно хватить этой инфы.

На большую помощь не расчитывайте - временем не располагаю.

Вместо P.S.

Если же задачу всё-таки нужно (зачем?) было решить именно в плоскости через произвольный девятиугольник, то, естестевенно, решением будет система из четырёх уравнений окружностей: по окружности на каждые три точки произвольного девятиугольника и одна окружность, на которой будут лежать центры трёх остальных окружностей.

То есть если решаем через уравнения двух сфер и одной окружности "балуемся" радиусом окружности (центр этой окружности помещяем в центр системы координат) и дальше по желанию изменяем положения сфер и точки их пересечения на окружности.

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

Главное при этих "играх" не забыть исключить симметричных решения - это сократит время перебора вариантов.

[GAGArin]

Если рассматривать двумерный случай. Какая разница где лежит последняя точка? Построить решения для одной точки I и повернуть их вокруг первой точки (только зачем?) будут совсем все решения. Значит у нас заданы уже две точки.

Вращением где-нибудь по 5 градусов распологаем еще две окружности. Когда доходим до последних двух отрезков считаем (тут уже почти никакой математики) всего два возможных варианта их расположения. Достаточно схематично, но получится. Иначе все равно выбирать придется из тысяч вариантов.


(красным - расстояние оставшееся на два последних отрезка)

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

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

[alibek]

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

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

[GAGArin]

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

Грубая рекурсия на 6 элементов, и просчет вариантов на два последних.

Ну с инверсной кинематикой конечно тоже можно. Вот только нужно ли?

[Amed]

Ого, я смотрю, заинтересовался народ

Про инверсную кинематику я подумал в первый же момент, потихоньку пишу проект, как время появляется.
8 bone'ов, 9 вершин. Первая и последняя фиксированы, за остальные можно таскать. Можно фиксировать любую из остальных по желанию, подбирая расположение. Но это лишь даст какое-то крайне "левое" решение.

[Amed]

Плюнул на расчет идеальной конфигурации, времени пока нет
Расположил первые семь осей на окружности, последнюю девятую вертикально над первой.
Зацепляющиеся пары обозначены цифрами 1-9.