对于由等式 aX + bY <= c 在整数上指定的直角三角形
我想以伪随机顺序绘制三角形中的每个像素（*）一次且仅一次，并且不存储先前命中点的列表。
我知道如何用 0 和 x 之间的线段来做到这一点
沿线选择一个随机点'o'，
选择与x相对质数的'p'
重复最多x次：O next = (O cur + P) MOD x
要对三角形执行此操作，我会
1. 需要计算三角形中没有列表的像素数
2. 将整数 0..points 映射到 ax,y 对中，该对是三角形内的有效像素
我希望任何解决方案都可以推广到金字塔和更高维度的形状。
(*) 我将 CG 术语像素用于整数点 X、Y 对，从而满足等式。
由于您想保证访问每个像素一次且仅一次，因此考虑像素而不是真正的三角形可能会更好。您可以水平切割三角形并获得一堆水平扫描线。将扫描线连接在一起，您已将“三角形”转换为长线。将您的点访问算法应用于您的长链扫描线。
顺便说一句，这种映射只需要在纸上进行，您所需要的只是一个可以沿虚拟扫描线给定 (t) 的函数返回 (x, y)。
编辑：要将两个点转换为线段，您可以查找Bresenham 的扫描转换。将 3 条线段转换为一系列点后，您可以将所有点放入一个桶中并按 y 对所有点进行分组。在相同的 y 值内，按 x 对点进行排序。y 值内的最小 x 是扫描线的起点，y 值内的最大 x 是扫描线的终点。这称为“扫描转换三角形”。如果你谷歌，你可以找到更多信息。
这是三角点拾取的解决方案。
您需要做的是选择三角形的两个向量（边），将每个向量与 [0,1] 中的随机数相乘并将它们相加。这将在向量定义的四边形中提供均匀分布。您必须检查结果是否在原始三角形内；如果它没有将其重新转换或简单地丢弃它并重试。
一种方法是将所有像素放入一个数组中，然后将数组打乱（这是O（n）），然后按打乱数组中的顺序访问像素。不过，这可能需要相当多的内存。
这是一种浪费一些 CPU 时间的方法，但可能不会像更复杂的方法那样浪费。
计算一个外接三角形的矩形。很容易“线性化”那个矩形，每条扫描线都跟着下一条。使用您已经知道的算法来遍历矩形的像素。当你点击每个像素时，检查像素是否在三角形中，如果不是，则跳过它。
我会将三角形的线视为单条线，将其切成段。这些段将存储在一个数组中，其中还存储了段的长度以及行总长度的偏移量。然后根据 O 的值，您可以根据此信息选择包含您当时要绘制的像素的数组元素，并根据元素中的值绘制像素。