获取重叠抛物线的网格单元

Question

如何有效地找到抛物线上两点定义的区间内与抛物线（超覆盖）重叠的所有像素？所有坐标均为整数，网格单元格大小为 1x1。抛物线由 f(x) = ax^2 + bx 给出，其中 a 和 b 已知（假设 c = 0）

我发现了这个查找所有网格单元重叠一条线的实现。它如何适应使用抛物线？ http://playtechs.blogspot.com/2007/03/raytracing-on-grid.html

Answer 1

从初始点开始，然后在每一步检查下一个将与哪个单元格相交。此任务假设像素不是无大小的点，而是定义大小 S 的单元格。初始单元格的坐标为 (0,0)

利用抛物线方程计算抛物线与垂线的交点x=S

y = a * S * S + b * S
y_index = floor(y/S)`

所以我们遍历单元格 (0,0), (0,1)...(0,y_index)，然后右转进入 (1,y_index)（y_index 可能等于零）

重复与第二级线y_index_1 = a * 2*S*2*S + b*2*S的交点，得到y_index1，标记从(1,y_index)到(1,y_index1)的单元格等等。

Python 例子

import math
def markcells(a, b, S, xmax):
    newy = 0
    oldy = 0
    step = 0
    while step * S <= xmax:
        step += 1
        edgex = step * S
        newy = math.floor((a*edgex*edgex + b*edgex)/S)
        lst = []
        for y in range(oldy, newy + 1):
            lst.append([step - 1, y])
        print(lst)
        oldy = newy

markcells2(0.05, 0.1, 1, 5)

[[0, 0]]
[[1, 0]]
[[2, 0]]
[[3, 0], [3, 1]]
[[4, 1]]
[[5, 1], [5, 2]]

P.S.
我省略了抛物线恰好穿过单元格角的情况（当 y/S 是整数时）——为这种情况选择想要的策略：是否标记单元格（例如，抛物线 y=x*x 代表 x=2 : 我们应该标记 (3,4) 和 (4,3) 吗？）

获取重叠抛物线的网格单元

Get Grid Cells Overlapping Parabola

algorithm

geometry