Создание алгоритма эквидистанты с применением методов контекстной среды

А.И. Разумовский,

с.н.с., к.т.н.,

ИПУ РАН, г. Москва

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

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

Технические аспекты построения алгоритма

Эквидистантой на расстояние D контура называется реальный или вырожденный контур, состоящий из ребер, каждое из которых отстоит от соответствующего ему ребра исходного контура на заданное расстояние D (рис. 1).

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

 

рис. 1. Внешняя и внутренняя эквидистанта

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

Такой алгоритм представляет собой последовательный в цикле перебор отрезков исходного контура, для каждого из которых рассчитывается параллельная линия и, затем, осуществляется поиск точки пересечения данной линии и прямой, аналогично построенной для смежного предшествующего отрезка.  В завершении цикла осуществляется поиск точки пересечения последней и «нулевой» эквидистантных линий. Результирующий эквидистантный контур будет, таким образом, состоять из ребер, определяемых последовательно полученными точками пересечения соответствующих эквидистантных линий (рис.2 ).

рис. 2. Метод последовательного пересечения эквидистантных линий

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

рис. 3. Вырожденность пересечения смежных эквидистантных линий

Точка Т31, являющаяся пересечением эквидистантных линий (ЭЛ) отрезка 3 и 1, лежит на прямой ЭЛ3 прежде, чем ожидается точка Т32 – пересечение двух смежных ЭЛ3 и ЭЛ2. В подобном случае, ЭЛ2  2-го отрезка оказывается невостребованной для построения результирующей эквидистанты. Еще более сложным для осознания своего алгоритмического описания представляется на рисунке 3 случай ЭЛ5, соответствующий  отрезку 5 контура. Наглядно видно, что ЭЛ5 невозможно будет использовать в результирующем контуре, так как она полностью лежит в области уже «перекрытой» ЭЛ1 и частично ЭЛ2. Очевидно также, что блокировка оказывается взаимной: нельзя использовать ЭЛ1 и ЭЛ2 из-за ЭЛ5, но и использование ЭЛ5 запрещено ЭЛ1 и ЭЛ2. Подобные ситуации именуются вырожденными. Однако, предполагая, что такая вырожденность может коснуться любого контура, стоит лишь задать расстояние эквидистанты D достаточно большим, следует отыскать, во-первых, способ сортировки точек пересечения ЭЛ, а, во-вторых, последовательность их пересечения. Ведь, очевидно, невозможно допустить степенную сложность алгоритма, время выполнения которого росло бы экспоненциально с ростом числа ребер в контуре. Следовательно, необходимо изыскать решение такого алгоритмического рисунка, при котором построение очередного эквидистантного ребра будет независимо от общего числа ребер в исходном контуре.

Из геометрии известно, что параллельные прямые отсекают на секущих пропорциональные отрезки (теорема Фалеса). Следовательно, множество точек пересечения ЭЛ двух ребер, будет лежать на биссектрисе угла между ними (рис. 4).

рис. 4. Множество точек пересечения ЭЛ лежит на соответствующих биссектрисах

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

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

Этапы алгоритма иллюстрируются рисунками 5, 6, 7, 8 и 9. В первую очередь (рис. 5 и 6), показаны результаты 1-го полного обхода контура. Видно, что осуществляется расчет биссектрис для двух последовательных пар смежных ребер контура, после чего более поздняя биссектриса обрезает предшествующую ей. Пересечение биссектрис следующей пары смежных ребер, более ранняя из которых является более поздней из предыдущей расчетной пары, дают точку обрезания лежащую на большем расстоянии от начала луча биссектрисы, чем точка пересечения предыдущей пары. При обнаружении данного случая правильной точкой считается ближайшая от начала луча биссектрисы. Поэтому в качестве найденного отрезка биссектрисы фиксируется отрезок минимальной длины (рис. 5в). Также обнаруживается первая замкнутая фигура, назовем ее фигура , ограниченная ребрами исходного контура и отрезками биссектрис. Именно к нахождению таких замкнутых многоугольников и устремляется действие алгоритма. Именно такие замкнутые фигуры , опирающиеся на ребра исходного контура, и будут фактически определять множество точек ЭЛ для этого ребра. На рисунках 5а 5в также присутствуют свободные отрезки. Каковые, по завершению полного обхода контура, аннулируются (рис. 6в). Также можно встретить случай расходящихся биссектрис (рис. 6а), точка пересечения которых лежит в мнимой к данному контуру области. При обнаружении подобного варианта, соответствующая биссектриса игнорируется.

 

рис. 5 а, б, в

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

(рис. 6в)

рис. 6 а, б, в

Следующий этап алгоритма, соответствует предыдущему за исключением того, что ребра, для которых найдены замкнутые фигуры, исключаются из дальнейших расчетов. Указанное действие можно назвать эффектом «схлопывания» отрезков контура. Смежными в этом случае становятся ребра, соседствующие в контуре через те, для которых искомые замкнутые фигуры найдены. Для них и осуществляется аналогично предыдущему последовательный в цикле поиск биссектрис, точек их взаимопересечения и замкнутых фигур.

 

рис. 7 а, б, в

 

рис. 8 а, б

 

рис. 9 а, б, в

Необходимость выполнения очередного цикла зависит от наличия в контуре «несхлопнутых» отрезков (рис. 7,8,9). Когда таких ребер не осталось, следует завершение главного этапа алгоритма. Рисунок 10 иллюстрирует результат этого этапа.

 

рис. 10. Области определения точек ЭЛ находятся внутри многоугольников,                                                               ограниченных отрезками, лежащими на соответствующих биссектрисах

Обсуждение

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

Заключение

В отыскании технического решения реализации алгоритма решающую роль сыграл факт необходимости соединения воедино исходных данных и результатов расчетов на их основе. Таким непреложным фактом соединения оказалась комплексная пара, состоящая из биссектрисы угла между расчетными ребрами  и отрезка, образующего одно из ребер фигуры  и лежащего на биссектрисе предыдущего этапа расчета. Таким образом, удается соединить недетерминированный результат и исходные данные. Главная ценность такого соединения заключается в том, что именно использование промежуточных результатов наравне с исходными характеристиками элементов контура позволяет нам осуществлять планомерное последовательное «схлопывание» контура, вследствие того, что место элементов этого контура будут последовательно занимать результаты , полученные в процессе расчета биссектрис с их использованием. Тем самым достигается сходимость алгоритма. Однако важен сам факт использования неявных результатов, готовность поставить предполагаемый промежуточный элемент расчета на место исходных. Важно также уточнить, промежуточные результаты в виде фигур  могут быть заменены, только если в процессе расчетного цикла они окажутся разрушенными очередной биссектрисой.  Но при этом образуется иная фигура, и, тем самым, как минимум множество расчетных элементов контура не увеличится.

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

Литература

1.     Разумовский А.И Решение проблемы дополнения и масштабирования программной системы посредством создания контекста проектирования. Материалы международной конференции CAD/CAM/PDM-2007, ISBN 978-5-91450-003-7.