找到与任意形状的四边形相交的规则网格单元
Find regular grid cells intersecting arbitrary shaped quadrilateral
我需要找到与由其角坐标定义的任意形状四边形相交的网格单元的所有索引 [x, y]；
- 网格单元格是具有
128 x 128 px 的图块
网格单元格的整数索引在[-nx, -ny]和[nx, ny]之间
（最大扩展是(2nx * 128) * (2ny * 128) px的正方形）
四边形由角点定义，坐标 (qx, qy) 像素 space 给出为 (tl, tr, br, bl)
- 这是集成在three.js场景中的：
- 角 points/coordinates 是从基座上的相机光线投射的 THREE.PlaneBufferGeometry
如何在 JavaScript 中以计算高效的方式获取所有相交的图块？
现在我通过使用 mx + b 以瓷砖尺寸 (128px) 作为步骤遍历每个四边形边缘来计算周边瓷砖；从那里，我只是逐行添加内部瓷砖索引。但这有点笨拙，这可能是也可能不是编码技能问题。我正要尝试使用 THREE.Raycaster 来获取周边图块索引，但还不确定如何。
我正在寻求更好的算法解决方案；基本公式、伪代码、思想或定解。
要有效找到与四边形边相交的网格单元，可以使用 Woo 和 Amanatides 网格遍历算法：文章 "Fast Voxel Traversal Algorithm...".
实际实施在 grid traversal 部分 here
示例：
对于凸四边形的内部单元格：在边遍历期间，记住行中最左边的单元格用于 "right" 条边，最右边的单元格用于 "left" 条边，并填充它们之间的水平间隙。
我需要找到与由其角坐标定义的任意形状四边形相交的网格单元的所有索引 [x, y]；
- 网格单元格是具有
128 x 128 px 的图块
网格单元格的整数索引在
[-nx, -ny]和[nx, ny]之间
（最大扩展是(2nx * 128) * (2ny * 128) px的正方形）四边形由角点定义，坐标
(qx, qy)像素 space 给出为(tl, tr, br, bl)- 这是集成在three.js场景中的：
- 角 points/coordinates 是从基座上的相机光线投射的 THREE.PlaneBufferGeometry
如何在 JavaScript 中以计算高效的方式获取所有相交的图块？
现在我通过使用 mx + b 以瓷砖尺寸 (128px) 作为步骤遍历每个四边形边缘来计算周边瓷砖；从那里，我只是逐行添加内部瓷砖索引。但这有点笨拙，这可能是也可能不是编码技能问题。我正要尝试使用 THREE.Raycaster 来获取周边图块索引，但还不确定如何。
我正在寻求更好的算法解决方案；基本公式、伪代码、思想或定解。
要有效找到与四边形边相交的网格单元，可以使用 Woo 和 Amanatides 网格遍历算法：文章 "Fast Voxel Traversal Algorithm...".
实际实施在 grid traversal 部分 here
示例：
对于凸四边形的内部单元格：在边遍历期间，记住行中最左边的单元格用于 "right" 条边，最右边的单元格用于 "left" 条边，并填充它们之间的水平间隙。