Учитывая 2 точки и линию - точки пересекаются с линией? : Алгоритм/псевдокод

Question

Коллега дал мне эту проблему, чтобы опробовать свои знания:

Рассмотрим две точки 1 и 2, имеющих координаты (x1, y1) и (x2, y2), соответственно. В той же плоскости, что и эти две точки, есть вертикальная линия, верх и низ которой представлены соответственно (xTop, yTop) и (xBot, yBot) соответственно. Две точки могут находиться на противоположных сторонах стены, на одной стороне стены или непосредственно над/под стенкой. Для простоты ни одна из точек не может быть непосредственно на стене. Линия берется из точки 1 в точку 2; если произойдет пересечение на стене (вертикальная линия), это произойдет в точке (xInt, yIint).

Учитывая две точки и одну стену, напишите алгоритм, чтобы определить, могут ли две точки видеть друг друга. Это может произойти только в том случае, если линия, проведенная от точки 1 до точки 2, не касается стены.

Я правильно определил, что если значения x обоих значений меньше или больше, чем у стены, они могут видеть друг друга. То же самое касается значений y. Я считаю, что в этой проблеме много геометрии. Но, я старик, просто возвращаюсь в программирование для удовольствия, и это действительно пытается понять меня. Любая помощь будет чрезвычайно оценена. Спасибо.

-Jon Н.

Answer 1

уравнение для линии у = х + Ь, где т наклон, а Ь у-перехват.

Чтобы определить, пересекает ли линия между двумя точками другую (в вашем случае вертикальную) линию, сначала определите наклон линии, соединяющей две точки.

м = наклон = (подъем/ход) = (у2 - у1)/(х2 - х1)

дальше, определяют у-перехват.

данный (x1, y1) находится на линии, а y = mx + b - уравнение для линии, тогда y1 = mx1 + b. Поскольку мы знаем y1, x1 и m, мы можем решить для b.

б = у-перехватывают = у1 - MX1 = у1 - ((у2 - у1)/(х2 - х1)) x1

Теперь, чтобы определить, является ли линия перехватывает стену, просто положить в х -координата для стены в уравнение для линии, соединяющей две точки, и если результат выходит за пределы диапазона значений y для стены, то он не перехватывает стену (две точки могут видеть друг друга).

Y @ стенки = mxbot + Ь

Если YBot < = Y @ стены < = YTop, то стенка между двумя точками.

Надеюсь, это вам поможет!

Answer 2

Как и многие геометрические алгоритмы, существует множество особых случаев. Давайте сделаем таблицу. L означает, что левая сторона стены, A означает выше, B мерседес означает, и R означает право. Y означает Да, ? означает, может быть, n означает нет (наличие перекрестка).

L A B R 
L n n n ? 
A n n Y n 
B n Y n n 
R ? n n n 

Когда одна точка находится слева, а другой справа, вычислим пересечение с линией, содержащей стенку и проверить, является ли она в стене.

Код:

def intersects(x1, y1, x2, y2, wallx, wallymin, wallymax): 
    if (x1 < wallx and x2 > wallx) or (x1 > wallx and x2 < wallx): 
     iy = ((x2 - wallx) * y1 + (wallx - x1) * y2)/(x2 - x1) 
     return iy >= wallymin and iy <= wallymax 
    elif x1 == wallx and x2 == wallx: 
     return (y1 < wallymin and y2 > wallymax) or (y1 > wallymax and y2 > wallymin) 
    else: 
     return False