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

[Portnov]

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

Нетрудно видеть, что если отрезков меньше трёх, то у задачи вообще нет решения, а если больше - то решений бесконечное множество. Т.е. в общем случае такая задача некорректно поставлена.

Женя Подсыпальников
Извините, вы явно не в теме. Если вы не понимаете, что нужно топикстартеру, помочь вы ему не сможете.

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

Если за основу системы брать модель построений с циркулем и линейкой, то уравнения окажутся либо линейные, либо квадратные. И те, и другие можно решать 'аналитически' (в смысле, по готовым формулам). Я покажу идею на примере одного уравнения, надеюсь вы сможете написать что-то аналогичное для систем.

Пусть у нас есть уравнение a0+a1*x+a2*x^2 + ... + an*x^n = 0. Представим его в виде списка пар (i,ai) - степень x и коэффициент при этой степени. Если максимальная степень больше, чем 2 - выдаём ошибку (в вашей системе этого, по идее, не должно получаться). Если максимальная степень 2 - вычисляем решения по формуле для квадратных уравнений (дискриминант итп). Если 1 - уравнение линейное, для получения ответа достаточно a1 поделить на (-a0). Если максимальная степень 0 - то а) если a0=0, решений бесконечное множество (x любое), б) если a0!=0, решений нет. Собсна, всё.

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

[Tem]

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

В параметрических САПР для данной задачи обычно задаются дополнительные ограничения (возможно, распорки или заданные углы), которые позволят вывести однозначное решение. Во всяком случае, в моей системе начертить такой цикла без дополнительных условий будет нельзя.

За статью спасибо - почитаю.

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

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

Я хочу сделать систему двухмерного черчения аналогичную T-Flex 2D, т.е. на основе вспомогательных линий (прямых, окружностей, сплайнов). Затем по размеченному листу будет сделана "обводка" контура фигуры с помощью отрезков прямых и дуг нужной толщины. В принципе, данные отрезки будут опираться на пересечения вспомогательных линий (где будут автоматически созданы узлы). Т.е. можно считать эти узлы своего рода "магнитиками", если так хочется.

[kamre]

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

Нетрудно видеть, что если отрезков меньше трёх, то у задачи вообще нет решения, а если больше - то решений бесконечное множество. Т.е. в общем случае такая задача некорректно поставлена.

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

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

Если за основу системы брать модель построений с циркулем и линейкой, то уравнения окажутся либо линейные, либо квадратные. И те, и другие можно решать 'аналитически' (в смысле, по готовым формулам). Я покажу идею на примере одного уравнения, надеюсь вы сможете написать что-то аналогичное для систем.
...
Для систем уравнений, конечно, будет побольше вариантов (первое линейное, второе квадратное, итп), но не так уж много, можно заранее расписать все случаи и выписать формулы для решений.

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

[Portnov]

Самое хорошое решение среди всех решений - это то, которое ближе всего к текущему положению объектов на чертеже.

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

(все-таки возможности циркуля и линейки ограничены)

В задачи входит трисекция угла?

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

[Tem]

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

Хорошо, предположим, что нам надо построить в САПР вот такой болт:

Размеры естественно заданы параметрически. Параметры резьбы на рисунке не указаны, пусть будет глубина резьбы h, угол фаски - 45 градусов.

[Portnov]

Так. Что дано, и что нужно найти? Я так понимаю, что дана серия ограничений типа 'эта прямая параллельна вот этой, а эта перпендикулярна'. Ограничения про 45* оставим на потом. Из ограничений про перпендикулярность и параллельность можно составить граф, типа такого

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

AB <- perp -> CD <- paral -> ...
 ^                  ^
 |                    |
paral             ....
 |
 v
EF <- perp -> ...

(AB,CD итп - это отрезки, стрелки изображают взаимосвязи). Берём первый попавшийся отрезок за основу. Один конец помещаем в начало координат, и направляем отрезок вдоль оси X. Например, пусть нам попался отрезок BC. Точку C примем за начало координат. Тогда точка B будет иметь координаты (x,0). Икс надо найти из имеющихся ограничений на длинны - это, в данном случае, СЛАУ, решение находится методом Гаусса. Т.о., один отрезок построили. Дальше начинаем поиск в глубину или в ширину по упомянутому графу. Каждый раз, когда мы переходим к следующему отрезку, мы знаем координаты одного конца, а координаты другого надо найти. В данной задаче уравнения все линейные, причём очень простые. Исходя из того, должен быть следующий отрезок параллелен или перпендикулярен предыдущему, выясняем, какую координату надо находить - это будет то абсцисса, то ордината.

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

В несколько более общей задаче, очевидно, будет получаться бесконечное множество решений при нахождении каких-то координат. Эти решения надо сохранять в символьном виде (типа 'x=2*a-3*b'), и в символьном же виде проводить действия с ними. Когда доберёмся до отрезка, у которого координаты обоих концов выражены в символьном виде - опять же, 'выписываем' все ограничения для этого отрезка, подставляем в них эти координаты - получаются новые уравнения, из которых можно будет найти что-то из промежуточных неизвестных.

Вот как-то так, вроде.

[kamre]

Самое хорошое решение среди всех решений - это то, которое ближе всего к текущему положению объектов на чертеже.

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

Нет, там все гораздо сложнее получается. Система уравнений нелинейная (полиномиальная). Решение - некоторое алгебраическое многообразие получается. В общем случае оно может быть пустым (задача несовместна), состоящим из конечного числа точек (конечное множество решений) и многообразие совершенно причудливой формы (типа k-мерной поверхности в R^n). Так что найти самую ближайшую точку вообще практически не реально.

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

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


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

[Tem]

В T-Flex это чертилось бы так.

Создаём вертикальную и горизонтальную вспомогательные прямые в точке 0, 0. Это будет на осевой линии и левой части головки болта. Делаем вертикальную прямую на расстоянии l влево от первой вертикальной, а затем на расстояние m вправо. Также для головки делается прямая с отступом a. От осевой линии делаем сверху и снизу горизонтальные прямые на расстояниях b/2 и d/2, а затем прямых для резьбы. От пересечений последних с прямой 'l' под углом 45 проводим прямые фаски. Ну и, наконец, проводим прямую ребра фаски.
Теперь, когда чертёж размечен вспомогательными линиями (невидимыми при печати), обводим необходимый контур болта толстой линией (при этом на пересечениях создаются необходимые узловые точки), а линии резьбы - тонкой сплошной.

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

Хотелось бы сделать свою САПР в таком же духе. Видимо, надо при построении линий сразу записывать их в список порядка пересчёта. Тут надо бы ещё подумать об объектной реализации примитивов, чтобы можно было сохранять / загружать их в файл в правильном порядке.

[Tem]

Похоже, что алгоритм построения можно записать в таком виде:

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

point0 = Point x: 0 y: 0;
 line0 = VertLine through: point0;
 line1 = HorLine through: point0;
 line2 = VertLine from: line0 dist: -l;
 line3 = VertLine from: line2 dist: m;
 ...

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

[Portnov]

Вобщем, пока вы тут рассуждали, я уже кое-что написал
git clone git://iportnov.ru/cad/
Эта штука понимает задание точек в виде "A(2,5)", а также условия вида "AB || CD", "AB _|_ CD", "AB = 5", "AB = CD", "C in AB". При вводе условия выводит соответствующее уравнение (всякие Dx,Dy - это соответственно x- и y-координаты неизвестных точек). Осталось только решалку этих уравнений дописать Благо, уравнения получаются только квадратные и линейные. Запускать - python syntax.py

Копирайт мой, лицензия GPLv3.