python - 需要有关光线追踪算法的建议

Question

我有一个显示世界及其海岸线的网格。这里显示了英国周边地区的摘录

从海洋中任意位置的任意原点，我想找到那些位于原点视线范围内的海岸线点，而不必穿过另一个海岸线点。例如，如果原点位于英国西侧，我希望获得爱尔兰西部和英国西部的许多海岸线点，但不会从丹麦获得，因为它被英国“覆盖”。

我需要有关快速算法的建议，该算法可以“射出”射线并检测这些射线穿过第一条海岸线的位置(海岸线 map 以二进制格式提供)。

或者，我可以想象沿着所有海岸线像素移动，在原点和海岸线点之间建立连接线，并检查连接线上是否没有其他海岸线点。有没有想到任何算法可以有效地完成这种海岸线穿越检查？

我意识到这个问题是一个意外的问题，但也许有一个聪明的人在这方面有知识。非常感谢任何帮助。

Answer 1

最简单的方法是使用DDA将像素从感兴趣点移动到图像边缘上的点的算法。假设在第一次点击时停止，对于 5000x10000 的 map ，这会导致一个非常简单的循环迭代数百万次。

如果计算量太大，您可以使用一种空间分区方案(例如四叉树、均匀网格、BSP 树)来跳过大的空白区域。