如何高效查找三角形内的所有整数点？顶点坐标范围0~10^9

嘿，这个问题确实戳中了大坐标下几何点查找的痛点——常规扫描线在1e9的范围里完全行不通，得靠几何规律来高效定位这些整数点。下面我给你一套实用的方案，既能精准找到符合要求的点（包括边界和内部的整数点），又不会做无用的遍历：

我们的目标是高效获取三角形边界及内部的整数点，若总数超过100则返回任意100个。核心逻辑是：先利用直线段的整数点规律快速生成边界点，再通过几何采样法生成内部点，全程避免逐行扫描的低效操作。

三角形的三条边都是直线段，每条边上的整数点可以通过最大公约数（GCD）来计算和生成：

• 对于两个顶点A(x₁,y₁)和B(x₂,y₂)，边上的整数点总数为 gcd(|x₂-x₁|, |y₂-y₁|) + 1（包含两个端点）
• 生成具体点的方法：计算dx = x₂ - x₁，dy = y₂ - y₁，g = gcd(|dx|, |dy|)，然后从A点出发，每次步进dx/g和dy/g，直到到达B点。比如A(0,0)、B(6,4)，g=2，步进(3,2)，就能得到点(0,0)、(3,2)、(6,4)

因为只需要最多100个点，我们不用生成所有内部点，用以下采样方法快速获取：

• 重心采样：计算三角形重心G((x₁+x₂+x₃)/3, (y₁+y₂+y₃)/3)，如果重心是整数点直接加入；如果不是，取重心坐标的整数近似值（比如向下取整、向上取整），用下面的叉积法判断是否在内部。
• 边界点偏移：选取任意边界上的非顶点整数点，沿着垂直于该边的方向向三角形内部步进整数单位，只要新点在三角形内就保留。比如边AB的方向向量是(dx, dy)，那么垂直方向的向量是(-dy, dx)，步进这个向量的单位整数步（除以GCD后的向量）就能得到内部点。
• 网格采样：从三角形的某个顶点出发，沿着两条边的方向生成网格点，判断是否在内部，直到凑够所需数量。

用叉积法可以快速判断点是否在三角形内（包含边界），完全避免除法，适合超大坐标：
对于点P(x,y)和三角形ABC，计算三个叉积：

cross1 = (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x)
cross2 = (C.x - B.x) * (P.y - B.y) - (C.y - B.y) * (P.x - B.x)
cross3 = (A.x - C.x) * (P.y - C.y) - (A.y - C.y) * (P.x - C.x)

• 如果三个叉积同号（全正或全负，取决于三角形的顺/逆时针方向），则P在内部；
• 如果任意一个叉积为0，则P在边界上。

• 先收集边界点，边生成边统计，一旦收集到100个就停止，随机返回这100个；
• 如果边界点不足100，再用内部点生成方法补充，直到凑够100个或所有点都收集完毕。

• 不用存储所有边界点，边生成边判断边收集，达到100个立即停止，节省内存；
• 内部点生成时优先选择靠近重心的区域，这些点大概率在内部，减少无效判断。

内容的提问来源于stack exchange，提问作者mahender singh