光束方向算法

Question

假设我们有一组镜子，还有一个光束发射器和一个光束接收器。 然后，我们应该找到发射器应该发射的方向，以便光束通过最短路径到达接收器。 如何有效地完成这项任务？ 图只是一个示例草图。

- Fedor Nesterenko

---

这是一个非常好的问题，但是缺乏你的努力会破坏它。此外，角度将取决于镜子的尺寸和发射器/接收器的坐标。它们是如何设置的？ - Alma Do

非常困难，因为现实世界中有无限的可能性。 - Christian

我认为在这种情况下，算法无法足够通用以适应所有可能的配置。 - Ankit Kumar

如果您省略了折射，您可以将真实世界的几何形状映射到光束上，而不是反过来。因此，解决方案就是找到从发射器到最近的未被阻挡的接收器之间的直线。请注意，这里的直线是真实世界中的直线而非光线。 - Aki Suihkonen

@AlmaDo，我确实搜索了答案，但是什么都没有找到。也许我只是不知道关于这个主题的正确术语。无论如何，我的任何幼稚的算法都太复杂了，不能适当地解决这个挑战。 接收器和发射器可以设置为具有一定半径的圆形，但为了简单起见，我们假设它们只是点。 - Fedor Nesterenko

唯一好的方法是复制镜像空间。任何其他尝试都是无意义的，所以他不得不询问。 - Gangnus

Answer 1

对于矩形网格，可以使用简化算法来计算接收器在下一个网格中的虚拟位置——就像你玩台球想要进行一次惊人的反弹一样。

     +---------+----------+---------+----------+
     | O                  |                    |
     |===>                |                <===|
     |     Real           |    Virtual copy    |
     |                    |                    |
     A---------+----------+---------+----------a

在这里，您希望将 O 球打到 A 口袋中，因此您需要在脑海中镜像池的几何形状，并瞄准虚拟口袋“a”。通过水平和垂直地反复镜像几何形状，可以无限地重复此场景。在某个时刻，应该存在一些不存在任何阻碍物的虚拟口袋/接收器 a(n) 的副本。

- Aki Suihkonen

---

有没有什么方法可以找出最好的镜像方式，还是只能通过试错来进行镜像，直到你运气好为止？ - Chris

不错的解决方案，尽管我认为它并不能保证最短路径... - Ron Teller

候选人A、a、a'、a''必须按欧几里得距离排序。第一个可到达的候选人是根据定义最短的路径（忽略折射）。目标“A”实际上不是一个点，而是一个区域，这使问题更加复杂。在这种情况下，当宽度=2*高度时，有几个其他的候选人需要首先尝试——它们都在“ A ”下面或上面。 - Aki Suihkonen

@RonTeller 这是有保证的。你只需要比较所有找到的行的长度并选择最短的一行。当到接收器图像的距离大于找到的最小值时，就不需要再检查更多的复制空格了。 - Gangnus

@AkiSuihkonen，如果评论没有针对帖子的作者，请将您的评论直接回复到该帖子中。否则，作者将无法看到它。在这条评论中，已经成功地提及了作者。 - Gangnus