Графо-теоретический подход.
Одномерное сжатие на основе графа ограничений состоит из шагов, показанных на Рис. 5.
Рис. 5 Алгоритм одномерного сжатия на основе графа ограничений.
Граф ограничений для задачи сжатия - это направленный, взвешенный граф G=(V, E) , где V= {Vi}- множество вершин; E= {Ej} - множество ребер.
Каждая вершина Vi графа представляет некоторый объект топологии Ri и характеризуется его координатой Ci, которая равна X или Y координате объекта в зависимости от направления графа. Граф также содержит две дополнительные вершины Source и Sink. Source - это вершина, которая не имеет входящих ребер, а Sink - выходящих. Source и Sink представляют воображаемые границы топологии.
Ребро описывает множество ограничений между парой объектов и имеет длину Lj, равную величине максимального ограничения. Существует два типа ограничений: минимального расстояния и связности. Первое используется для выполнения минимального расстояния между объектами топологии, а второе для обеспечения связности. Если от объекта А к объекту В есть ограничение на минимальное расстояние длиной LAB в направлении X (Рис. 6а) ), то
(1)
Связность накладывает ограничение на расстояние между объектами и бывает двух видов:
провод-терминал (Рис. 6б)): ограничивает максимальное расстояние между центрами объектов. Если провод W не должен смещаться от терминала T дальше, чем на LWT, то это описывается неравенствами:
(2)
терминал-терминал (Рис. 6в)): фиксируется расстояние между парой терминалов. Например, если терминалы S и D должны быть на расстоянии LSD, то это описывается неравенствами:
(3)
Рис. 6 Виды ограничений: а) мин. расстояния; б) связность провод-терминал; в) связность терминал-терминал (прибор)
Построение графа ограничений.
Построение графа ограничений можно разделить на два этапа: первый - построение вершин и второй - ребер.
При построении вершин для заданного направления рассматриваются только элементы топологии, имеющие фиксированный размер в этом направлении. Каждому такому объекту соответствует вершина в графе. Координата вершины равна координате точки привязки объекта.
При построении ребер сначала создаются ограничения связности. Для каждой связи в топологии строятся ребра в соответствии с формулами (2) или (3). Далее строятся ограничения минимального расстояния в соответствии с (1). Создание ребер вносит основной вклад во время работы алгоритма одномерного сжатия. Его сложность равна O(n2), где n - количество объектов топологии. В худшем случае строятся ребра между каждой парой объектов, в то время как используется только их малое подмножество. Существует несколько эффективных методов построения графа ограничений: «Теневой Алгоритм (Shadow-Propagation Algorithm)» [1], средняя сложность которого O(n1.5) и «Алгоритм Сканирующей Линии (Scanline 19Algorithm)» [1] сложность которого в худшем случае O(n2), но реальное время O(n), не считая сортировки.
Теневой алгоритм широко используется при построении графа ограничений. Каждый объект отбрасывает тень в направлении сжатия (Рис. 7). Обычно тень расширяют с двух сторон на величину ограничения. Если тень упирается в другой объект топологии, то добавляется ребро в граф ограничений и из фронта тени удаляется фрагмент, соответствующий препятствию. Процесс продолжается до тех пор, пока не удалится вся тень. Данный алгоритм выполняется для каждого объекта топологии.
Рис. 7 Пример распространения тени.
Алгоритм Сканирующей Линии также широко применим. В данном методе воображаемая горизонтальная (для X-сжатия) линия сканирует топологию снизу вверх, перемещаясь по нижним и верхним границам элементов (Рис. 8). Сканирующая линия содержит множество элементов, пересекаемых линией и отсортированных по не убыванию X координаты. Добавление элемента в линию происходит, как только линия доходит до нижней его границы. После добавления элемента строятся ограничения со всеми элементами линии. При этом учитывается порядок элементов линии. Когда линия доходит до верхней границы элемента он удаляется из нее. Для удобства сканирования используются два списка элементов топологии. Первый отсортирован по не убыванию нижних границ, а второй - верхних.
Рис. 8 Пример сканирующей линии.
Алгоритм сканирующей линии создает много избыточных ребер, которые не влияют на длиннейшие пути от Source до каждой вершины графа. Удаление таких ребер не изменит эти пути в графе ограничений. Рассмотрим пример на Рис. 9. Если , то ребро Е1i - избыточное и может быть удалено.
Рис. 9 Пример избыточного ребра
В общем случае ребро называется избыточным, если между двумя вершинами ребра существует путь, не содержащий данного ребра и его длина больше веса ребра. В теории графов такие ребра называют транзитивными. Удаление избыточных ребер значительно сокращает время работы последующих алгоритмов.
|
