Нахождение точек пересечения ребер

Перпендикуляры, проведенные на предыдущем шаге все еще никак между собой не связны, поэтому необходимо найти точки их пересечения. Заранее не известно, какие именно ребра пересекаются; для каждого ребра проверяются все остальные, еще не проверенные ребра, на предмет их пересечения. В этой проверке можно выделить четыре случая: ребра параллельны / находятся на одной прямой / скрещиваются (лежат в параллельных плоскостях) / пересекаются. Проверку нужно провести только на нахождение ребер на одной прямой и на пересечение.

Определение нахождения ребер на одной прямой

Уравнение прямой, проходящей через две точки, в трехмерном пространстве выглядит следующим образом:

где — координаты первой точки,.

— координаты второй точки.

Так как проверяемые ребра (восстановленные перпендикуляры) параллельны хотя бы одной оси координат, в этой формуле будет происходить деление на ноль, во избежание этого нужно воспользоваться правилом пропорции:

(2).

Допустим, сравнивается ребро AB и ребро CD, если подставить в (2) вместо координаты вершины A, вместо координаты вершины B, а вместо поочередно координаты вершин C и D, и оба выражения будут выполняться, то ребра лежат на одной прямой.

В этом случае ребра могут не пересекаются. Если же ребра ab и cd пересекаются могут возникнуть пять ситуаций:

· ребра пересекаются в одной из существующих вершин (рис. 4);

Рисунок 4.

• · ребра совпадают, в этом случае второе ребро удаляется из ;
• · одна из вершин одного ребра находится на другом ребре, к примеру вершины ребер ab и cd расположены в следующем порядке: a c b d, в этом случае ребра ab и cd удаляются из, а новые ребра ac, cb и bd добавляются в матрицу (рис. 5);

Рисунок 5

· одно ребро находится внутри другого, но вершины не совпадают, в этом случае меньшее ребро удаляется из. Например на рис. 6 нужно удалить ребро ab;

Рисунок 6.

· одно ребро находится внутри другого, и одна из вершин ребра ab совпадает с одной из вершин ребра cd, к примеру если a = c и вершины расположены в порядке: a=c, d, b (рис. 7), ребро ab удаляется из, а новое ребро db добавляется в матрицу.

Рисунок 7.