机器人方形网格交点

Question

我正在尝试根据机器人在地图中的位置和它指向的角度（以弧度表示）来确定我的机器人将与墙相交的点。所以总结一下这个问题，给定一个任意大小 [1-无穷大] 的正方形网格，该网格内的一个对象，以及该对象所面对的角度（弧度），找到与网格边界的交点.例如，您有一个 10 x 10 的网格，您的对象位于位置 (5,5)，并且它面向的角度为 pi/8 弧度（东北方向）。如果这个物体沿直线移动，它会在哪里与墙相交？是否有适用于任何位置和任何角度的通用解决方案？到目前为止，我正在做的是在同一轨迹上计算网格外的一个点，并查看所有点，直到找到一堵墙，但我觉得可能有一个更优雅的解决方案。感谢您的帮助！

Answer 1

起点在矩形内的射线的伪代码：
起点(X0, Y0)
光线角度 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)

Answer 2

你可以简单地找到两条线段的交点。

第一段：从机器人在指向角度的位置开始的段。使此段大于网格的对角线，以确保它会与边界相交（如果要的话）。第二段：构成相关墙的线段。

请参阅 http://www.faqs.org/faqs/graphics/algorithms-faq/ 1.03 节以了解相交两条线段的算法。

comp.graphics.algorithms 常见问题解答是解决机器人技术中常见几何问题的有用资源。

机器人方形网格交点

Robotics Square Grid Intersection Point

algorithm

math

geometry

robotics

trigonometry