algorithm - 机器人方形网格交点

Question

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

Answer 1

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

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

参见 http://www.faqs.org/faqs/graphics/algorithms-faq/ 1.03 节求两条线段相交的算法。

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