Изменения

Теперь, когда отсортированные точки хранятся в структуре, поддерживающей эффективный поиск, мы можем воспользоватся идеями бинарного поиска для нахождения моста. Для этого необходим критерий спуска, по которому мы будем определять подотрезок, до которого нужно сузить задачу, имея точки <tex>p</tex> и <tex>q</tex>, определяющие секущую к выпуклым оболочкам множеств <tex>A</tex> и <tex>C</tex> . В  Рассмотрим дополнительно 4 точки: <tex>p^{+}</tex> - следующая за <tex>p</tex> точка выпуклой оболочки множества <tex>A</tex> в отсортированном порядке, то есть <tex>p_{y}^{+} > p_{y}</tex> и ордината <tex>p_{y}</tex> - наименьшая. <tex>p^{-}</tex> - предыдущая <tex>p</tex> точка выпуклой оболочки множества <tex>A</tex> в отсортированном порядке, то есть <tex>p_{y}^{-} < p_{y}</tex> и ордината <tex>p_{y}</tex> - наибольшая. <tex>q^{+}</tex> - следующая за <tex>q</tex> точка выпуклой оболочки множества <tex>C</tex> в отсортированном порядке, то есть <tex>q_{y}^{+} > q_{y}</tex> и ордината <tex>q_{y}</tex> - наименьшая. <tex>q^{-}</tex> - предыдущая <tex>q</tex> точка выпуклой оболочки множества <tex>C</tex> в отсортированном порядке, то есть <tex>q_{y}^{-} < q_{y}</tex> и ордината <tex>q_{y}</tex> - наибольшая. Тогда в зависимости от взаимного расположения выпуклых оболочек вектора <tex>\overrightarrow{qp}</tex> и секущей имеем точек <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex>, <tex>q^{-}</tex> можно определить, какой из 9 случаев рассматривать, а именно: a) Все точки <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex>, <tex>q^{-}</tex> расположены справа от вектора <tex>\overrightarrow{qp}</tex> (aт.е. образуют с ним правый поворот) - найден мост. b) <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex> - справа, <tex>q^{-}</tex> - слева от <tex>\overrightarrow{qp}</tex> c) <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{-}</tex> - справа, <tex>q^{+}</tex> - слева от <tex>\overrightarrow{qp}</tex> d) Как в случае b, только слева от <tex>\overrightarrow{qp}</tex> находится точка <tex>p^{+}</tex> e) Как в случае c, только слева от <tex>\overrightarrow{qp}</tex> находится точка <tex>p^{-}</tex> f) <tex>p^{-}</tex>, <tex>q^{+}</tex> - справа, <tex>p^{+}</tex>, <tex>q^{-}</tex> - слева от <tex>\overrightarrow{qp}</tex> g) <tex>p^{+}</tex>, <tex>q^{+}</tex> - справа, <tex>p^{-}</tex>, <tex>q^{-}</tex> - слева от <tex>\overrightarrow{qp}</tex> h) <tex>p^{-}</tex>, <tex>q^{-}</tex> - справа, <tex>p^{+}</tex>, <tex>q^{+}</tex> -слева от <tex>\overrightarrow{qp}</tex> i). <tex>p^{+}</tex>, <tex>q^{-}</tex> - справа, <tex>p^{-}</tex>, <tex>q^{+}</tex> - слева от <tex>\overrightarrow{qp}</tex> Для случаев (a-h) на картинках красным показано, какие части выпуклых оболочек могут быть отброшены. Случай же i немного сложнее.