我有一个显示世界及其海岸线的网格。这里显示了英国周边地区的摘录
从海洋中任意位置的任意原点,我想找到那些位于原点视线范围内的海岸线点,而不必穿过另一个海岸线点。例如,如果原点位于英国西侧,我希望获得爱尔兰西部和英国西部的许多海岸线点,但不会从丹麦获得,因为它被英国“覆盖”。
我需要有关快速算法的建议,该算法可以“射出”射线并检测这些射线穿过第一条海岸线的位置(海岸线 map 以二进制格式提供)。
或者,我可以想象沿着所有海岸线像素移动,在原点和海岸线点之间建立连接线,并检查连接线上是否没有其他海岸线点。有没有想到任何算法可以有效地完成这种海岸线穿越检查?
我意识到这个问题是一个意外的问题,但也许有一个聪明的人在这方面有知识。非常感谢任何帮助。
最佳答案
最简单的方法是使用DDA将像素从感兴趣点移动到图像边缘上的点的算法。假设在第一次点击时停止,对于 5000x10000 的 map ,这会导致一个非常简单的循环迭代数百万次。
如果计算量太大,您可以使用一种空间分区方案(例如四叉树、均匀网格、BSP 树)来跳过大的空白区域。
关于python - 需要有关光线追踪算法的建议,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32590522/