Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
5.5. Решение задач о близости методом локусов
265
CH(Si),
CrKSz")
Найдя луч цепи ст, мы последовательно строим ребра цепи до тех пор, пока не достигнем второго луча. Для лучшего понимания полезно обратиться к примеру на рис. 5.28, на котором для простоты каждая точка р, представлена своим номером j. В приведенном примере верхний луч цепи а перпендикулярен отрезку, соединяющему точки 7 и 14, и делит его пополам. Представим точку г, двигающуюся по верхнему лучу из бесконечности сверху вниз.
Первоначально точка z на- J
ходится в некоторых многоугольниках диаграмм Vor(Si) и Vor(52). Точка z будет двигаться по лучу до тех пор, пока не пересечет ребро одного из этих многоугольников. С этого момента точка начнет двигаться в другом направлении. В нашем примере точка z первой пересечет ребро диаграммы Vor(S2). Это значит, что теперь z стала ближе к точке 11, чем к точке 14, и поэтому она должна двигаться вдоль прямой, перпендикулярной отрезку, соединяющему точки 7 и 11, и делящей его пополам.
Это продолжается до тех пор, пока не будет достигнута прямая, перпендикулярная отрезку, соединяющему точки 6 и 7, делящая его пополам. Теперь точка z двигается по прямой, перпендикулярной отрезку, соединяющему точки 6 и 11, и делящей его пополам. В конце концов она пересечет прямую, перпендикулярную отрезку 10—11, делящую его пополам, и движение продолжится по прямой, перпендикулярной отрезку 6—10 и делящей его пополам. Такое зигзагообразное движение по ломаной будет продолжаться до тех пор, пока не будет достигнут нижний луч цепи а.
Предположим, что продвижение по о осуществляется в направлении уменьшения «/-координаты. Механизм продвижения по а обеспечивает переход от текущего ребра е и текущей вершины v (являющейся верхним концом ребра е) к следующим ребру е' и вершине г/. Если ребро е разделяет многоугольники V(i) и V(j), где pi^Si и р;е52, то вершина v' является либо точкой пересечения е с границей V(i) в Vor(Si), либо точкой пересечения е с границей V(j) в Vor(S2) в зави-
Рис. 5.27. Определе
лучей цепи ст.
Гл. 5. Близость: основные алгоритмы
симости от того, какая из них ближе к v. Таким образом, просмотрев границы многоугольников V(i) в Vor (Si) и V(j) в Vor(S2), можно легко определить вершину v'. К. сожалению, цепь о может, оставаясь внутри некоторого многоугольника V(i), многократно менять свое направление, прежде чем она пересечет какое-либо ребро многоугольника V(i). И если каждый раз приходится просматривать все многоугольники V(i),
Рис. 5.28. Зигзагообразный путь, проходимый при построении о.
то может потребоваться проверить слишком много ребер, и в общем случае необходимое для этого время может оказаться квадратичным. Однако использование особенностей структуры диаграммы Вороного позволяет разработать более эффективную стратегию просмотра.
Действительно, предположим, что последовательность ребер еи е2, ек цепи о содержится в V(i), где для конкретности p»eSi (см. пример на рис. 5.29, где k = 3). Продолжим каждое ребро вн за его конечную точку Vh, получая луч гн, и рассмотрим точку пересечения qn луча г,, с границей многоугольника V{i) в Vor(Si). Рассмотрим подцепь С\=еь ...
ек цепи а и часть границы многоугольника V(i) в Vor(Si), расположенную справа от а, которую обозначим С2. Подцепь С2 — это часть границы (возможно, неограниченного) выпуклого многоугольника V(i) в Vor (Si); Ci также является выпуклой и целиком содержится в V(i). Так как все углы между отрезками vhqh и vhqh+u где h = 1, 2, ..., k — 1 (с учетом на-
/ /
/
/
\
\
5.5. Решение задач о близости методом локусов
267
правления от vhqh к vhqn+i), имеют один и тот же знак, то точки пересечения q\, q2, qu оказываются упорядоченными на С2. Отсюда следует, что при определении точек пересечения q\, q2, ••• цепь С2, т. е. границу многоугольника V(i) в Vor(Si), необходимо просматривать без возвратов в порядке обхода по часовой стрелке. Аналогичные рассуждения показывают, что границу любого многоугольника V(j) в Vor(S2) следует просматривать без возвратов в порядке обхода против часовой стрелки.
Граница V(i) ч Vor(S,)
Рис. 5.29. Точки пересечения q\, q2, <7з упорядочены на С2.
В частности, будем считать, что как Vor(Si), так и Vor(S2) представлены в виде РСДС (см. разд. 1.2.3.2), при этом циклы граней ориентированы по часовой стрелке в Vor(Si) и против часовой стрелки в Vor(S2). Для представления РСДС диаграммы Vor(Si) используется массив указателей СЛЕДУЮЩИЙ! [ ], используемый для обхода границы грани по часовой стрелке. Аналогичный массив СЛЕДУЮЩИЙ2[ ] используется для представления Vor(S2). В работе алгоритма используются три ребра: два ребра еь и е«, принадлежащие соответственно Vor(Si) и Vor(S2), и «текущее ребро» е цепи а (в действительности не само ребро, а прямая, содержащая это ребро). Кроме ребра е используется также его начальная точка v (для первого ребра е* цепи а, являющегося лучом, в качестве v* берется точка, лежащая на е* и имеющая достаточно большую ординату). И наконец, используются две точки множества S, Pl^Si и j?« е S2, образующие отрезок PlPr, перпендикулярный текущему ребру е, которое делит его пополам. Пусть / (е, е') обозначает пересечение отрезков е и е', а запись
