点检查与方程光线投射效率

Question

我有一个项目需要检测 2D 生物正在看的其他生物（如果有的话）。我已经实施了一个四叉树来协助这些方法。我有两个建议的方法：

1. 通过检查一条线上的几个点对少量生物进行点检查。首先找到的是 returned
2. 通过求解 mx+b=sqrt(r^2-(x-x1)^2)+y1 检查一定范围内的任何生物是否与直线相交的方程式。但是为了这个工作，我必须：
   • 将视图转换为线条
   • 获取四根并检查 b^2-4ac >=0
   • 确保其他看到的生物不在视图生物后面
   • 检查跟随它的一组生物，看看哪个最接近
   • return那个

我的最终问题是：考虑到所有因素，最终什么是最有效的？为什么？

备注：

这个项目专门在 Java 但我很好奇语言是否重要。 结果应该是每条射线，并被用作神经网络的输入。

Answer 1

第二种方法可以转化为quadtree-ray交集查询。 JavaScript 中的一个相当不错的实现可以在 here 中找到。对于射线相交的每个节点，执行与之前概述的相同的距离查询，并在找到第一个生物时立即 return。