Расчет параметризованных геометрических примитивов (Проектирую геометрический решатель)

[Tem]

По причине отсутствия в Linux открытой параметрической CAD-системы, принял решение попытаться её реализовать.

Главной задачей сразу же стало создание ядра подобной САПР - геометрического решателя.

Параметрические САПР отличаются тем, что геометрия строится в них по заданным ограничениям. Так, например, прямая может быть описана как проходящая через центр отрезка AB и касательно некоторой окружности. Т.е. такая система в некотором смысле аналогична системе интерактивной геометрии Kig из kde-edu. Кроме того, отдельные параметры примитивов могут быть описаны во внешних переменных, при изменении которых геометрия объекта должна быть пересчитана.

Пока не лезу в 3D и хочу создать хотя бы двухмерную параметрическую САПР.

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

[eddy]

А сниппеты не смотрели (snippets.org)?

[Portnov]

Чо-то не понятно, где, собственно, проблема. Надо курс аналитической геометрии вспомнить, что ли?

[Tem]

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

[Portnov]

Не понятно, что такое 'расчет примитивов'? Общая-то идея, надеюсь, ясна - по заданным ограничениям строить уравнение линии, а потом изображать сами линии.

[Женя Подсыпальников]

Пусть каждый объект имеет магнитные точки,
кои можно тянуть мышкой, кои тянуться к самим себе,

например, совмещаются раньше на 5 пикселей
и остаются совмещёнными с запаздыванием на 5 пикселей

Пусть на объекте существуют как стандартные,
например, позиционно-угловые магниты,

так и возможность присобачить
определённые пользователем магниты

[Tem]

Не понятно, что такое 'расчет примитивов'? Общая-то идея, надеюсь, ясна - по заданным ограничениям строить уравнение линии, а потом изображать сами линии.

Вот нахождение уравнения я и имел в виду под расчётом.

[sarutobi]

Уважаемый Portnov правильно сказал - нужно вспомнить курс аналитической геометрии - уравнения прямой и окружности для начала (ax+by=c, (x-a)^2+(y-b)^2=R^2) и выяснить какие параметры за что отвечают. Потом вспомнить как находится пересечение двух прямых (решение системы линейных уравнений), и пересечение прямой и окружности, попытаться все это реализовать. Ну а потом - написать визуализацию.

[Tem]

Уважаемый Portnov правильно сказал - нужно вспомнить курс аналитической геометрии - уравнения прямой и окружности для начала (ax+by=c, (x-a)^2+(y-b)^2=R^2) и выяснить какие параметры за что отвечают. Потом вспомнить как находится пересечение двух прямых (решение системы линейных уравнений), и пересечение прямой и окружности, попытаться все это реализовать. Ну а потом - написать визуализацию.

Аналитическую геометрию я помню. Собственно и в начале треда я упоминал о решении уравнений. Кстати говоря, например, расчёт коэффициентов прямой, проходящей через точку и касательной некоторой окружности потребует решения системы квадратных уравнений с двумя неизвестными. В связи с этим возник вопрос: нужно ли делать аналитические решения систем уравнений "вручную" и занести их в программу в таком виде, или же пусть программа в процессе черчения будет собирать необходимые системы уравнений "на лету" и численно их решать?

Пусть каждый объект имеет магнитные точки

Я не планирую делать САПР, похожую на AutoCAD, поскольку его примитивность меня не устраивает. Во всяком случае, "магнитность" точек относится более к интерфейсу программы, нежели к его ядру.

[Tem]

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

Задаю такой вопрос, потому что даже в случае прямой, проходящей через точку (x_A, y_A) и касательной к некоторой окружности с центром (x_C, y_C) и радиусом R, получается следующее аналитическое решение (Maxima):

Код: Выделить всё

(%i12) solve([R^2=(x_C + B*y_C + C)^2 / (1 + B^2), x_A + B*x_A + C = 0], [B, C]);
                         2                  2                    2    2                                   2
               R sqrt(y_C  - 2 x_A y_C + x_C  - 2 x_A x_C + 2 x_A  - R ) + (x_C - x_A) y_C - x_A x_C + x_A
(%o12) [[B = - --------------------------------------------------------------------------------------------,
                                                  2                  2    2
                                               y_C  - 2 x_A y_C + x_A  - R
                  2                  2                    2    2           2                 2           2        2
    R x_A sqrt(y_C  - 2 x_A y_C + x_C  - 2 x_A x_C + 2 x_A  - R ) - x_A y_C  + (x_A x_C + x_A ) y_C - x_A  x_C + R  x_A
C = -------------------------------------------------------------------------------------------------------------------],
                                                  2                  2    2
                                               y_C  - 2 x_A y_C + x_A  - R
               2                  2                    2    2                                   2
     R sqrt(y_C  - 2 x_A y_C + x_C  - 2 x_A x_C + 2 x_A  - R ) + (x_A - x_C) y_C + x_A x_C - x_A
[B = --------------------------------------------------------------------------------------------,
                                        2                  2    2
                                     y_C  - 2 x_A y_C + x_A  - R
                    2                  2                    2    2           2                   2           2        2
      R x_A sqrt(y_C  - 2 x_A y_C + x_C  - 2 x_A x_C + 2 x_A  - R ) + x_A y_C  + (- x_A x_C - x_A ) y_C + x_A  x_C - R  x_A
C = - ---------------------------------------------------------------------------------------------------------------------]]
                                                     2                  2    2
                                                  y_C  - 2 x_A y_C + x_A  - R

Как можно видеть, здесь даже сделано допущение A=1 в уравнении прямой, ибо Maxima всё равно не может его вычислить. Тем не менее, реально возможен случай, когда A=0 - в этом случае прямая должна быть параллельна оси Ox.

[kamre]

По причине отсутствия в Linux открытой параметрической CAD-системы, принял решение попытаться её реализовать.

Главной задачей сразу же стало создание ядра подобной САПР - геометрического решателя.

Параметрические САПР отличаются тем, что геометрия строится в них по заданным ограничениям. Так, например, прямая может быть описана как проходящая через центр отрезка AB и касательно некоторой окружности. Т.е. такая система в некотором смысле аналогична системе интерактивной геометрии Kig из kde-edu. Кроме того, отдельные параметры примитивов могут быть описаны во внешних переменных, при изменении которых геометрия объекта должна быть пересчитана.

Пока не лезу в 3D и хочу создать хотя бы двухмерную параметрическую САПР.

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

Мне также интересна эта тематика, и я тоже подумываю что-то подобное реализовать (параметрический 2D скетчер, не 3D т.к. там слишком сложно все). Пока у меня все еще на уровне идей, но некоторый опыт имеется. Можно попробовать подумать вместе на эту тему.

Вообще схема для решения задач с ограничениями выглядит примерно так: для всех примитивных объектов (точек, прямых, окружностей) заводятся переменные для описания их координат, а ограничения тогда описываются уравнениями на эти переменные. Открытых библиотек для решения таких задач с геометрическими ограничениями я не нашел. Хотя наверняка можно будет что-то использовать для решения нелинейных систем уравнений, которые нужно будет генерировать по описанию из объектов и ограничений.

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

[kamre]

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

Можно решать все численно, но лучше разбивать задачу на подзадачи и некоторые из них решать аналитически.

Задаю такой вопрос, потому что даже в случае прямой, проходящей через точку (x_A, y_A) и касательной к некоторой окружности с центром (x_C, y_C) и радиусом R, получается следующее аналитическое решение (Maxima):
...
Как можно видеть, здесь даже сделано допущение A=1 в уравнении прямой, ибо Maxima всё равно не может его вычислить. Тем не менее, реально возможен случай, когда A=0 - в этом случае прямая должна быть параллельна оси Ox.

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

[Женя Подсыпальников]

Я не планирую делать САПР, похожую на AutoCAD, поскольку его примитивность меня не устраивает. Во всяком случае, "магнитность" точек относится более к интерфейсу программы, нежели к его ядру.

Магниты будут ответственны за ограничения,
а их планированием (расставление) займётся пользователь (:

Ведь порисовать опромеж двух точек
или в регионе большего их числа -
будет не трудно ядру некоторой граф-библиотеки ? (:

Мне бы, как пользователю твоей программы ,
хотелось бы иметь следующие виды магнитов:

- межобъектный простой
- межобъектный запертый (со знаком замочка на квадратике захвата, пожалуйста) - сомкнуто, пока не отперто
- якорный (со значком якорька на квадратике захвата, пожалуйста) - закреплён к плоскости планирования в растяжках и верчениях

, а не задачу ограничений в полях ввода параметров (:

Допустим, когда-то, ты захочешь дать мне два магнита,
один - на конце линии, а другой - на окружности,

но не сможешь рассчитать положение последнего -
тогда я дам тебе уравнение окружности (:

Или - мы не будем его рассчитывать,
а просто попросим систему вернуть координаты указателя мыши (:

Хотя, пользователи бывают разные,
некоторые рисуют и строками бэйсика,
у тебя они - какие ? (:

[kamre]

Я не планирую делать САПР, похожую на AutoCAD, поскольку его примитивность меня не устраивает. Во всяком случае, "магнитность" точек относится более к интерфейсу программы, нежели к его ядру.

Хотя, пользователи бывают разные,
некоторые рисуют и строками бэйсика,
у тебя они - какие ? (:

Для AutoCAD есть плагин, который дает возможность для параметризации модели:

Вот Tem и хочет что-то в этом духе делать, насколько я понимаю. А магнитики здесь дело десятое, они к интерфейсу имеют отношение, а не к модели напрямую. Хотя их наверняка можно через ограничения будет сделать.

Кстати из open source есть "Open CASCADE" (хотя в нем внутри нет решателя ограничений):

[Женя Подсыпальников]

Дак, а в автакаде -
тожа ш мышкой рисуют-тянут ?

Поля - то, наверна, для точной рихтовки лишь ?

Но, изменив, допустим, радиус окружности-
линия - перестанет касаться её, не так ли ?

Вот почему я вижу магнитики -
не тока как рычаги, но и точки законов связей,

просто необходимых, как я понял с условия ограничений

[Tem]

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

Вот выше приведено аналитическое решение этой задачи. И оно довольно нетривиально, хотя ничего не мешает "зашить" его в программу.

Можно решать все численно, но лучше разбивать задачу на подзадачи и некоторые из них решать аналитически.

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

Женя Подсыпальников
ты когда-нибудь работал с параметрическими САПР?

[Женя Подсыпальников]

Женя Подсыпальников
ты когда-нибудь работал с параметрическими САПР?

На кой ?

Было, растягивал как либо трансформированные 2D объекты
и помогал им стыковаться меж собой,

наблюдая изменение координат, радиусов, углов в полях...
И наоборот

[Tem]

Женя Подсыпальников
ты когда-нибудь работал с параметрическими САПР?

На кой ?

Было, растягивал как либо трансформированные 2D объекты
и помогал им стыковаться меж собой,

наблюдая изменение координат, радиусов, углов в полях...
И наоборот

Извини конечно, но чем ты мне тогда можешь помочь?

[Женя Подсыпальников]

Можа, предложением не решать уравнений,
а двигать желания мышкой ?

[Tem]

Можа, предложением не решать уравнений,
а двигать желания мышкой ?

И зачем тогда нужна эта тупая чертилка? Pro/ENGINEER, CATIA, T-Flex, SolidWorks и прочие профессиональные САПР основаны на параметризации. Зачем делать простую векторную рисовалку? С таким же успехом можно предложить чертить в OpenOffice.org Draw или в Inkscape.

[Женя Подсыпальников]

Можа, предложением не решать уравнений,
а двигать желания мышкой ?

И зачем тогда нужна эта тупая чертилка?

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

А какие цели потенциально не учтены ?

[kamre]

Можа, предложением не решать уравнений,
а двигать желания мышкой ?

И зачем тогда нужна эта тупая чертилка? Pro/ENGINEER, CATIA, T-Flex, SolidWorks и прочие профессиональные САПР основаны на параметризации. Зачем делать простую векторную рисовалку? С таким же успехом можно предложить чертить в OpenOffice.org Draw или в Inkscape.

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


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

[Женя Подсыпальников]

Вот, интересно сделать что-то подобное:

Т.е. новая прорисовка,
например, по смене значения Х в поле координаты центра окружности ?

Это есть:
мы просто вызаваем OnMouseDelta(CHandel* pcHandel, int iDX, int iDY) ,

как если б мы двинули этот центр мышкой...

Это два конца одной палки, я думаю ?

[kamre]

Т.е. новая прорисовка,
например, по смене значения Х в поле координаты центра окружности ?

Это есть:
мы просто вызаваем OnMouseDelta(CHandel* pcHandel, int iDX, int iDY) ,

как если б мы двинули этот центр мышкой...

Это два конца одной палки, я думаю ?

Нет, это просто изменение параметра для вертикального расстояния 10 -> 12 -> 14 -> 16, а затем для горизонтального 25 -> 30 -> 35 -> 40. При этом радиус окружности и положения других объектов пересчитываются полностью автоматически. Т.е. нифига не тоже самое, "как если б мы двинули этот центр мышкой"

[Женя Подсыпальников]

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

Это задача магнитиков,
которые работают и в случае текстового(числового),
и в случае мышьего сдвига, не так ли ?

[Tem]

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

В принципе, я решил делать систему с аналитически предрассчитанными формулами отношений. Надеюсь, получится удачно.

[Женя Подсыпальников]

А в автакаде (? , от kamre) - крестиком-ноликом - разве не магнитики ?

Чем же они не удобны ???

(по-моему, именно они имеют логику "следования" внешним изменениям)

[kamre]

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

Я про эти "магнитики" его все равно не понимаю, чем же они у него от ограничений отличаться должны...

В принципе, я решил делать систему с аналитически предрассчитанными формулами отношений. Надеюсь, получится удачно.

Аналитически довольно много задач не получится решить... Вот, например, как предполагается решать аналитически цикл из ограничений расстояния:

???

[Женя Подсыпальников]

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

Согласен,
иногда легче и приятнее протянуть рулетку

(кстати, многие из рулеток
имеют магнитик в виде крюка-зацеки на конце ленты... )

[kamre]

Вот достаточно интересная статья по теме: http://www.cs.purdue.edu/cgvlab/papers/cmh...constraints.pdf