Одной полуплоскости соответствуют точки, где F(x, у) > 0, а другой - где F(x,y) < 0. Условие пересечения отрезка прямой имеет вид F(X|, y\)F(x2, Уг) < 0. Если пересечение имеет место, то точка пересечения ищется в виде Л" = /Xj + (l - t)х2, v = 0'i +(t-~0.};2> Компьютерная графика. Полигональные модели о
ГДе t =-j-г-j-г
F(x2,y2)-F{x^yx)Это пересечение прямой и луча. Чтобы получить пересечение отрезка с лучом, достаточно сравнить координаты точки пересечения с концами отрезка.
Вследствие того, что проверка на пересечение луча с произвольным отрезком существенно сложнее, чем проверка на пересечение с горизонтальным или вертикальным отрезком, быстродействие данного алгоритма не так высоко.
Для повышения быстродействия можно попытаться использовать когерентность между соседними столбцами пикселов - если данный столбец соответствует некоторой стене, то скорее всего несколько последующих столбцов также будут соответствовать этой же стене. Изменим процедуру проверки луча на пересечение с заданной стеной - сразу найдем, каким столбцам с\ и с2 соответствуют концы отрезка, и запомним их, и, если потребуется проверить на пересечение луч с данной стеной, достаточно просто проверить, принадлежит ли номер луча (столбца) диапазону [с1,с2]. Удобно сразу же рассчитать высоты для проекций соответствующих столбцов этой стены (они изменяются линейно).
Тем самым мы приходим к следующей процедуре проверки.
float checkWall (int wallno ) {
Wall * wptr = &walls [wallno];
if (Iwptr -> flags ) // check if data not computed {
float u1 = -(wptr->x1-locX)*sin(angle)+(wptr->y1-locY)*cos(angie); float v1 = (wptr->x1-locX)*cos(angle)+(wptr->y1-locY)*sin(angle); float u2 = -(wptr->x2-locX)*sin(angle)+(wptr->y2-locY)*cos(angle); float v2 = (wptr->x2-locX)*cos(angle)+(wptr->y2-locY)*sin(angle);
// check if wall is behind if ( v1 < V_MIN && v2 < V_MIN )
{
wptr -> d = w -> ptr -> c2 = 10000; wptr -> flags = 1; return -1;
}
if ( v1 < V_MIN ) {