Точка пересечения сетки робототехники

Question

Я пытаюсь определить точку, в которой мой робот будет пересекаться с стеной, учитывая ее местоположение на карте и угол, указывающий на радианы. Таким образом, чтобы суммировать проблему, учитывая квадратную сетку любого размера [1-бесконечность], объект внутри этой сетки и угол, с которым этот объект сталкивается (радианы), найдите точку пересечения с границей сетки , Например, у вас есть сетка размером 10 x 10, ваш объект находится в положении (5,5), и он обращен под углом pi/8 радианов (северо-восточное направление). Если бы этот объект должен был двигаться по прямой, где бы он пересекался со стенкой? Есть ли обобщенное решение, которое будет работать для любой позиции и любого угла? Пока что я делаю вычисление точки вне сетки на той же траектории и глядя на все точки, пока не найду стену, но я чувствую, что есть, вероятно, более элегантное решение. Спасибо за помощь!

Answer 1

Вы можете просто найти точку пересечения двух отрезков.

Первый сегмент: сегмент от положения робота под углом поворота. Сделайте этот сегмент большим, чем диагональ вашей сетки, чтобы убедиться, что он пересечет границу, если это произойдет. Второй сегмент: сегмент линии, который составляет эту стену.

См. http://www.faqs.org/faqs/graphics/algorithms-faq/ Раздел 1.03 для алгоритма, который пересекает два отрезка.

Часто задаваемые вопросы о comp.graphics.algorithms - полезный ресурс для общих задач геометрии в робототехнике.

Answer 2

псевдокод для луча с отправных точек внутри прямоугольника:
Начальная точка (X0, Y0)
Ray угол Theta, c = Cos(Theta), s = Sin(Theta);
Прямоугольник координаты: bottom left (X1,Y1), top right (X2,Y2)

if c >= 0 then //up 
    XX = X2 
else 
    XX = X1 

if s >= 0 then //right 
    YY = Y2 
else 
    YY = Y1 

if c = 0 then //vertical ray 
    return Intersection = (X0, YY) 

if s = 0 then //horizontal ray 
    return Intersection = (XX, Y0) 

tx = (XX - X0)/c //parameter when vertical edge is met 
ty = (YY - Y0)/s //parameter when horizontal edge is met 

if tx <= ty then //vertical first 
    return Intersection = (XX, Y0 + tx * s) 
else   //horizontal first 
    return Intersection = (X0 + ty * c, YY)