Решение задачи 8.
Можно, конечно, из точки Z провести отрезки ко всем 3-м вершинам треугольника, и посмотреть: если сумма площадей трех треугольников ZAB, ZBC, ZCA равна площадей ABC, то точка внутри, иначе - снаружи, но так как все вычисления в машине проводятся с ограниченной точностью, то проверка на равенство ПРАКТИЧЕСКИ НИКОГДА не даст правильного ответа. Вы почти всегда будете получать, что Z вне ABC, не смотря на действительное расположение точки Z. Попробуем решить задачу по-другому:
Принадлежность точки стороне проверяется просто: если концевые точки стороны A(x1,y1) и B(x2,y2), то, если точка Z(x,y) принадлежит стороне, то должно существовать такое число p, 0<=p<=1, что
x=p*x1+(1-p)*x2
y=p*y1+(1-p)*y2
(тут используется то, что если прямая проходит через A и B, то точки прямой имеют координаты (p*x1+(1-p)*x2, p*y1+(1-p)*y2), p действительное число. При 0<=p<=1 мы получаем отрезок между точками A и B).
Далее, проведем из точки Z прямую, параллельную оси OX (ее уравнение будет x=u) и проверим, сколько сторон треугольника пересекает полулуч, идущий от точки Z, например, вправо. Если 0, то Z - вне треугольника, если 1 - то внутри, если 2 - то снаружи (определение пересечения прямой и стороны - задача 6).
Надо конкретно обработать случай, когда прямая пересекает одну из вершин треугольника (например, A).
Может быть 2 случая:
В случае 1, когда оба ребра, входящих в вершину A, лежат по одну сторону от прямой, количество пересечений можно считать равным двум (или нулю), в случае 2, когда ребра лежат по разные стороны от прямой, число пересечений примем равным 1. Проверка, по разные или по одну сторону от прямой лежат концевые точки отрезков - см. задачу 6. Если прямая проходит по стороне, то число пересечений будем считать равным 2.
Аналогично можно проверить, лежит ли точка Z внутри многоугольника (в алгоритме безразлично, выпуклый он или нет). Мы подсчитываем число пересечений луча со сторонами - если оно нечетное, то точка внутри, если четное - то снаружи.
|
