Нахождение пересекающихся сегментов

Мы получили квадрантные деревья пересекающихся поверхностей и список соперников. Теперь можно приступить к поиску пересекающихся сегментов, начиная с одной из пар в списке соперников. Сначала мы можем взять любую из пар в списке соперников и вычислить сегмент их пересечения (или, точнее, две конечные точки). Для вычисления этих конечных точек мы используем пересечение двух плоскостей, поскольку все лоскуты в списке соперников уже прошли тест на плоскостность. Обозначим эти точки как А1 и А2. Вспомните, что мы всегда находим точные координаты соответствующих точек, когда получаем конечные точки по пересечению двух плоскостей. Конечная точка используется как первоначальное грубое приближение для точного нахождения соответствующей точки путем решения уравнения (7.50).

Теперь необходимо найти следующую пару лоскутов, которые дадут сегмент пересечения, соединенный с одним из концов текущего сегмента пересечения. Допустим, что мы ищем точки пересечения от А1 к А2. Соответственно, нам нужно найти пару, которая даст сегмент пересечения с точкой А2. Процедура нахождения следующей пары показана на рис. К.4. Следующая пара, X1-Y2, находится после получения текущей точки пересечения А2 из текущей пары, X1-Y1. следующим образом.

Нахождение пересекающихся сегментов
 
  • Определяется местоположение текущей точки пересечения, в данном случае А2, по отношению к лоскутам текущей пары. Таким образом, А2 находится на границе лоскута Y1 и внутри лоскута X1.
  • Лоскут, полностью содержащий в себе текущую точку пересечения, то есть лоскут X1, используется снова для следующей пары. После этого мы выбираем один из лоскутов, соседствующих с Y1, в качестве второго лоскута для следующей пары. Выбор определяется местоположением текущей точки пересечения относительно Y1. В данном случае мы выбираем правый соседний лоскут, поскольку текущая точка пересечения А2 находится на правой границе лоскута Y1. Затем мы вычисляем точки пересечения для этой новой пары, и для поиска следующей пары роль текущей точки пересечения возьмет на себя другая точка, отличная от А2.
Эта процедура завершается, когда точка пересечения достигает границы одной из пересекающихся поверхностей (рис. К.5). После этого точки пересечения проходятся в обратном порядке, начиная с исходного сегмента пересечения. Можно считать, что текущая кривая пересечение получена полностью, если она превращается в замкнутый контур или пересекается с одной из поверхностей по двум граничным кривым. Мы можем также найти остальные кривые пересечения, выполнив поиск точек пересечения от одной из пар в списке соперников, которая не участвовала в вычислении уже полученных кривых пересечения. Так, если мы не оставим в списке соперников ни одной пары, которая бы не участвовала в вычислении какой-либо кривой, то мы тем самым найдем все кривые пересечения.
 

Нахождение пересекающихся сегментов

 

 

Смотрите также