对于由等式aX + bY <= c表示的整数的直角三角形

我想以伪随机顺序绘制三角形中的每个pixel(*)一次且仅绘制一次，并且不存储以前的命中点列表。

我知道如何使用0到x之间的线段执行此操作

pick a random point'o' along the line,

     pick 'p' that is relatively prime to x

     repeat for up to x times:     Onext = (Ocur + P) MOD x

为此，我想
1.需要计算三角形无序列表中的像素数
2.将整数0..points映射到x，y对中，该对是三角形内的有效像素

我希望任何解决方案都可以推广到金字塔和更高尺寸的形状。

(*)我将CG项像素用于一对整数点X，Y，以便满足方程式。

解决方案

由于我们希望保证一次访问每个像素一次，因此最好考虑像素而不是真实的三角形。
我们可以水平切三角形，并获得一堆水平扫描线。将扫描线连接在一起，我们已将"三角形"转换为长线。将点访问算法应用于长条扫描线。

顺便说一下，这种映射只需要在纸上进行，我们所需要的只是一个函数，该函数可以沿虚拟扫描线返回(t)给定(t)。

编辑：
要将两个点转换为线段，可以查找不来梅的扫描转换。一旦将3个线段转换为一系列点，就可以将所有点放入存储桶中，并将所有点按y分组。在相同的y值内，按x排序点。 y值内的最小x是扫描线的起点，y值内的最大x是扫描线的终点。这称为"扫描转换三角形"。如果我们使用Google，则可以找到更多信息。

一种方法是将所有像素放入一个数组中，然后对数组进行混洗(这是O(n))，然后按混洗后的数组中的顺序访问像素。但是，这可能需要很多内存。

这是一种浪费一些CPU时间的方法，但是可能不会像更复杂的方法那样浪费很多时间。

计算一个外接三角形的矩形。将该矩形"线性化"变得很容易，每个扫描线后跟一个扫描线。使用我们已经知道的算法来遍历矩形的像素。当我们击中每个像素时，请检查像素是否在三角形中，如果不是，则跳过该像素。

这是三角点拾取的解决方案。

我们要做的是选择三角形的两个向量(边)，将每个向量与[0,1]中的随机数相乘，然后将它们相加。这将在矢量定义的四边形中提供均匀的分布。我们必须检查结果是否在原始三角形内；如果它不能将其转换回去，或者干脆将其丢弃，然后重试。

我将三角形的线视为单条线，将其切成段。线段将存储在一个数组中，其中线段的长度以及行的总长度中的偏移也将存储在该数组中。然后，根据O的值，我们可以根据此信息选择哪个数组元素包含此时要绘制的像素，并根据元素中的值绘制像素。