三个点内形成三角形的整数点数是多少？

@Cocksure然后不要理会这个,因为显示的方法不适用于[我们的三角形](http://imgur.com/S5F5ePA).使用[Shoelace Formula](http://en.wikipedia.org/wiki/Shoelace_formula)计算A要容易得多,用GCD计算边界点并解决Pick的定理为'I = A - B/2 + 1' (5认同)
你们在编辑时一定是在读书.:) (3认同)

Answer 2

Pick's定理(http://en.wikipedia.org/wiki/Pick%27s_theorem)指出放置在整数点上的简单多边形的表面由下式给出:

A = i + b/2 - 1

这里A是三角形的表面,i是内部点的数量,b是边界点的数量.通过对每条线的斜率的最大公约数求和,可以容易地计算边界点b的数量:

b =   gcd(abs(p0x - p1x), abs(p0y - p1y)) 
    + gcd(abs(p1x - p2x), abs(p1y - p2y)) 
    + gcd(abs(p2x - p0x), abs(p2y - p0y))

表面也可以计算.有关计算表面的公式,请参阅/sf/answers/1006788471/.结合这些已知值,我可以通过以下方式计算:

i = A + 1 - b/2

Answer 3

我的下意识反应是蛮力:

找到x和y方向上三角形的最大和最小范围.
循环遍历这些范围内的所有整数点组合.
对于每组点,使用标准测试之一(例如,相同或重心技术)来查看点是否位于三角形内.由于此类计算是用于检测光线/线段和三角形之间的交叉点的算法的组成部分,因此您还可以查看此链接以获取更多信息.

Answer 4

好的我会提出一个算法,它不会很棒,但它会起作用.

首先,我们需要一个三角形测试点.我建议使用这个优秀帖子中解释的"重心技术":

现在到算法:

let(x1,y1)(x2,y2)(x3,y3)是三角形顶点
设ymin = floor(min(y1,y2,y3))ymax = ceiling(max(y1,y2,y3))xmin = floor(min(x1,x2,x3))ymax = ceiling(max(x1,x2, 3))
迭代从xmin到xmax和ymin到ymax,你可以枚举包含三角形的矩形区域中的所有整数点
使用三角形测试点,您可以测试枚举中的每个点,看它是否在三角形上.

这很简单,我认为它可以在不到半小时内完成编程.

Answer 5

这被称为"三角形点"测试.

下面是文章有几种解决方案,这一问题:在三角测试点.

替代文字

检查点是否在三角形中的常用方法是找到将点连接到三角形的三个顶点中的每个顶点的向量,并对这些向量之间的角度求和.如果角度之和为2*pi(360度),则该点在三角形内,否则不是.