我们有一个带有半透明墙壁和几个光源的矩形区域。我们只考虑俯视图,所以这是一个 2D 问题。我们需要找到该区域每个点的近似照明(信号强度)。
我们需要让算法变得非常快。蛮力方法对于我们的目的来说太慢了。您可以假设所有墙壁都衰减相同的量,即使是恒定的衰减量也是可以接受的。
该区域最多为 1000x1000,并且不会有超过 100 个光源。光源的范围可以约为。50-100 个单位(它们不是无限的)。欢迎使用更快但近似的算法。
提前致谢!
我尝试的基本上是蛮力方法:将每个样本点与每个墙壁和光源进行比较以确定其光度。显然,它是 O(n^3) 并且慢得令人无法接受。
时间我并不是指任何特定的限制:但最好在 100 毫秒或更快的时间内完成整个图像。请记住,我对准确性的要求不如速度。