需要关于光线跟踪算法的建议

Question

我有一个显示世界和海岸线的网格。以下是英国周边地区的摘录

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

我需要一个快速算法的建议，可以“射出”射线，并检测这些射线穿过第一条海岸线的位置（海岸线地图以二进制格式提供）。在

或者，我可以想象沿着所有海岸线像素移动，在原点和海岸线点之间建立连接线，并检查连接线上是否没有其他海岸线点。有没有什么算法可以有效地完成海岸线交叉的检查？在

我知道这个问题是一个晴天霹雳，但也许有一个聪明的人在这方面有知识。任何帮助都是非常感谢的。在

Answer 1

最简单的方法是使用DDA算法从感兴趣的点向图像边缘的点移动像素。假设在第一次命中时停止，对于5000x10000映射，这将导致几百万次非常简单的循环迭代。在

如果计算量太大，可以使用一种空间划分方案（如四叉树、统一网格、BSP树）跳过较大的空白区域。在