13 / 18
Расчет областей пересечения поверхностей захватных устройств манипуляторов…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
109
поддеревьями. Если расстояние между вершиной и опорной точкой меньше
R
,
то она принадлежит внутреннему поддереву, иначе — внешнему. В каждом из
получившихся подмножеств выбирается следующая опорная точка и рассчиты-
вается новый радиус. Операция построения дерева продолжается до тех пор,
пока размеры подмножеств не достигнут заданного предела — максимального
размера листа [13].
Затем путем поиска по VP-деревьям для каждого элемента множеств
P
и
Q
определяется ближайший сосед среди элементов множеств
Q
и .
P
Поиск
по VP-дереву осуществляется следующим образом — начиная с корневого узла
дерева определяется расстояние между вершиной, для которой осуществляется
поиск, и центром узла VP-дерева. Если расстояние меньше радиуса области узла,
то поиск продолжается во внутреннем поддереве, иначе — во внешнем. По до-
стижении листа дерева выполняется линейный поиск среди точек листа [13].
Далее, опираясь на индексы полученных пар ближайших соседей из множеств
P
и
,
Q
восстанавливаются индексы для соответствующих точек из
P
и
Q
и
в итоге для
P
и
Q
. На этом этапе проводится дополнительная фильтрация — если
угол между векторами
i j
p q
и
v
— тупой, то очевидно, что точка
i
p
тела
A
не нахо-
дится в контакте с телом
B
, и ее можно исключить из дальнейшего рассмотрения
(вершины
1
p
и
1
q
на рис. 5).
Для конфигурации ЗУМ, изображенной на рис. 7,
а
, представлен результат
поиска ближайшего соседа по VP-дереву для вершин полигональных моделей,
попавших в ОПВ. На рис. 7,
а
зелеными линиями изображен ОПВ для ОП ОМ,
красными — ОПВ для ОП звена ЗУМ. На рис. 7,
б
синими точками обозначены
вершины ОМ, находящиеся внутри ОПВ, соответствующей OBB ОМ, розовыми —
вершины звена ЗУМ, расположенные в ОПВ OBB звена ЗУ, синими и розовыми
линиями показаны соответственно ближайшие соседи для вершин ОМ и звена ЗУ
после фильтрации.
Рис. 7.
Этапы узкой фазы определения пересечения ОМ и звена ЗУ