Ничего. Прямая может не пересекать отрезок, например, как на картинке:
Пересечение прямой и выпуклого многоугольника
Чтобы найти пересечение прямой L и выпуклого многоугольника, можно сначала найти пересечение каждой из сторон данного многоугольника с прямой L. Рассмотрим возможные результаты пересечения прямой и отрезка:
Одна точка. Если отрезок пересекает прямую и не лежит на ней, то пересечение прямой и отрезка - одна точка:
Отрезок. Если отрезок и прямая имеют хотя бы 2 общие точки, то отрезок лежит на данной прямой, так как прямая определяется двумя точками:
Теперь можно рассмотреть пример алгоритма по нахождению пересечения прямой и отрезка, если прямая задана формулой \(ax + by + c = 0\), а отрезок - координатами двух точек: \((x_1, y_1)\) и \((x_2, y_2)\):
1. Для начала запишем формулу для прямой, на которой лежит отрезок - \(x(y_1 - y_2) + y(x_2 - x_1) + (x_1y_2 - x_2y_1) = 0\). Чтобы убедиться, что такая формуда описывает прямую, на которой лежит данный отрезок вы можете подставить в эту формулу значения \(x\) и \(y\) в точках (\(x_1, y_1\)) и (\(x_2, y_2\)).
2. Теперь можно вспомнить, про алгоритм нахождения пересечения двух прямых, описанных формулами \(a_1x + b_1y + c1 = 0\) и \(a_2x + b_2y + c_2 = 0\):
• Если \({a_1b_2} = {a_2b_1}\) и \({b_1c_2} \ne b_2c_1\), то прямые параллельны, а значит не имеют точек пересечения. Тогда становится очевидным, что данные прямая с отрезком также не имеют общих точек.
• Если \({a_1b_2} = {a_2b_1}\) и \({b_1c_2} = b_2c_1\), то прямые совпадают, а значит пересечение данных прямой и отрезка - весь отрезок.
• А если \({a_1b_2} \ne {a_2b_1}\), то пересечение двух прямых - точка с координатами \((x_3, y_3)\), где \(x_3 = {b_1c_2 - b_2c_1 \over a_1b_2 - a_2b_1}\) и \(y_3 = {a_1c_2 - a_2c_1 \over a_2b_1 - a_1b_2}\).
В данном случае также надо определить принадлежность точки \((x_3, y_3)\) данному отрезку (\(x_1, y_1\)) (\(x_2, y_2\)). Для этого надо использовать скалярное произиедение. Если скалярные произведения векторов \(((x_1, y_1), (x_3, y_3))\) и \(((x_1, y_1), (x_2, y_2))\) и векторов \(((x_2, y_2), (x_3, y_3))\) и \(((x_2, y_2), (x_1, y_1))\) неотрицательные, то точка \((x_3, y_3)\) принадлежит отрезку, а значит пересечение данной прямой с отрезком - точка \((x_3, y_3)\). Иначе прямая не пересекает отрезок.
Теперь можно найти пересечение прямой L с многоугольником, найдя пересечение каждой из сторон многоугольника с прямой L. Объеденеие найденных множеств точек - это и будет пересечение всего многоугольника с прямой L. Посмотрим - что же могло получиться в результате пресечения многоугольника в прямой L:
Ничего. Если прямая не пересекает ни одной из сторон многоугольника, то она не имеет общих точек с многоугольником:
Одна точка. Если одна из вершин многоугольника нахходится на прямой, и прямая не имеет общих точек с внутренней частью многоугольника (внутренняя часть не включает стороны и вершины многоугольника), то пересечение прямой L с многоугольником - одна вершина многоугольника:
Две точки. Если прямая L пересекает хотя бы 2 отрезка в разных точках и ни один из них не лежит на прямой L, то пересечение прямой L и многоугольника - 2 точки, так как, если их пересечение - хотя бы 3 точки, то многоугольник невыпуклый, что можно наблюдать на рисунке:
Отрезок.Если прямая L пересекает многоугольник хотя бы в трёх точках, то эти три точки лежат на одной стороне многоугольника, так как на разных сторонах они не могут лежать по рисунку из предыдущего пункта:
Чтобы найти объединение множеств, каждое из которых - пересечение стороны с прямой L, то:
1. Если одно из этих множеств - отрезок, то этот отрезок и есть объединение всех множеств.
2. Если среди этих множеств нет отрезка, то, находя в каком-то множестве точку, надо её добавлять в объединение, если она не окажется в конечном множестве второй раз.