[Павлов Д.С.] <Математический алгоритм построения геологических разрезов> [оглавление]

4.3.2.2. Пересечение двух полилиний

Если спуститься на уровень ниже, то задача будет заключаться в нахождении точки (точек) пересечения двух кривых линий. В нашем алгоритме такие линии аппроксимированы полилиниями, каждая из которых представляет собой ломаную линию, состоящую из набора отрезков. В координатной форме это массив пар (X, Y). Все линейные элементы, изображаемые на геологической карте, являются произвольными кривыми линиями, для которых не существует описывающих их функций вида Y = f (X), где X и Y - географические координаты. Поэтому, чтобы найти пересечение двух кривых линий аналитическим способом, необходимо аппроксимировать каждую кривую конечным числом точек, через которые она проходит. При незначительном расстоянии между точками, результирующая ломаная линия будет соответствовать исходной кривой в достаточно полной мере (рисунок 3.3).

Постановка задачи: необходимо найти все точки пересечения двух полилиний. Для этого можно использовать несколько способов. Рассмотрим, по мнению автора, самый очевидный и простой из них.

Разобьем задачу на ряд однотипных подзадач. Решение такой подзадачи схематично изображено на рисунке 4.12 и сводится к следующему.

Рисунок 4.12. Схема процедуры нахождения точек пересечения двух полилиний.

Берем первый отрезок из полилинии А и первый отрезок из В и с помощью алгоритма для нахождения точки пересечения двух отрезков¹ проверяем, пересекаются они или нет. В случае успешной проверки, то есть отрезки пересекаются, сохраняем координаты точки пересечения в упомянутом выше хранилище данных. Если отрезки не пересекаются, берем первый отрезок из полилинии А и второй из В и повторяем процедуру. Когда подобным образом мы <пробежим> по всем отрезкам полилинии В, возьмем второй отрезок из полилинии А и повторим цикл для него и всех отрезков из В. В результате в хранилище данных окажутся координаты всех точек пересечения двух полилиний.

[назад] [оглавление] [далее]