以快速的方式找到LIne和网格之间的交点

Question

反正有没有让我找到一条线和一个网格之间的所有交叉点？(交叉圆圈不是按比例绘制的,我知道)

蛮力方法是计算非常交点为x-y与线网格,但是该算法是非常低效的(O(m*n)其中m是的数目x网格和n是的数y网格).

我正在寻找一个更好的算法.

Answer 1

听起来你需要数字差分分析仪或Bresenham的线算法.Bresenham与用于在位图上绘制线条的算法相同; 在这种情况下,着色像素等同于检查该正方形中的碰撞.

Answer 2

我不确定我是否真的理解这个问题.这是你想要的任何机会吗？