在构成三角形的三个点中有多少个整数点?

假设顶点是整数坐标,您可以通过在三角形周围构建一个矩形来得到答案,如Kyle Schultz的解释。 An Investigation of Pick's Theorem .

对于JXK 矩形 ,内部点数为

I = (j – 1)(k – 1).

对于下面的5 x 3矩形,有8个内部点。

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image008.jpg

对于具有垂直支腿(j)和水平支腿(k)的三角形,内部点的数量由以下公式给出:

I = ((j – 1)(k – 1) - h) / 2

其中h是矩形内部与三角形斜边重合的点数(不是长度)。

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image012.jpg

对于有垂直边或水平边的三角形,内部点(i)的数量由以下公式给出:

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula5.jpg

其中j、k、h1、h2和b标记在下图中

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Triangle3.jpg

最后,没有垂直或水平边的三角形的情况可以分为两个子情况,一个是三角形周围的区域形成三个三角形,另一个是周围区域形成三个三角形和一个矩形(见下图)。

第一个子案例中的内部点数(i)由下式给出

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula7.jpg

在下图中标记所有变量

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/triangle5.jpg

第二个子案例中的内部点数量(i)由下式给出

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image042.png

在下图中标记所有变量

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image038.png

皮克定理( 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))

表面也可以计算。有关计算曲面的公式,请参见 https://stackoverflow.com/a/14382692/2491535 . 结合这些已知值,我可以通过以下方式计算:

i = A + 1 - b/2

我下意识的反应是野蛮地强迫它:

• 找出三角形在x和y方向上的最大和最小范围。
• 循环这些范围内的所有整数点组合。
• 对于每一组点,使用一个标准测试( Same side or Barycentric techniques 例如)查看点是否位于三角形内。由于这种计算是检测光线/直线段和三角形之间交叉点的算法的一个组成部分,因此您还可以检查 this link 更多信息。

这被称为“三角形中的点”测试。

这里是 文章 对于这个问题有几种解决方案: Point in the Triangle Test .

检查点是否在三角形中的常用方法是 找到向量 将该点连接到三角形的三个顶点中的每一个,以及 求和 在这些向量之间。如果角度之和为 2×PI (360度)然后点是 在三角形内 否则就不是了。

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

首先,我们需要三角测试中的一个点。我建议使用“重心技术”,如这篇优秀文章所述:

http://www.blackpawn.com/texts/pointinpoly/default.html

现在来看看算法:

1. 设(x1,y1)(x2,y2)(x3,y3)为三角形顶点

2. 设Ymin=地板(min(y1,y2,y3))Ymax=天花板(max(y1,y2,y3))Xmin=地板(min(x1,x2,x3))Ymax=天花板(max(x1,x2,3))。

3. 从xmin迭代到xmax,从ymin迭代到ymax,可以枚举包含三角形的矩形区域中的所有整数点。

4. 使用三角形中的点测试,您可以测试枚举中的每个点,以查看它是否在三角形上。

它很简单,我想它可以在不到半小时内被编程。

对于非暴力方法,我只有一半的答案。如果顶点是整数,可以将其简化为计算如何找到边相交的整数点。利用这个数字和三角形的面积(Heron公式),您可以使用pick定理来找到内部整数点的数量。

编辑:对于另一半,找到与边缘相交的整数点,我怀疑它是点之间x和y差减去1的最大公分母,或者如果距离减去1,如果x或y差之一为零。

这是另一种方法,不一定是最好的,但一定能打动面试官。

首先,用最低的x坐标“l”、最高的x坐标“r”和剩余的点“m”(左、右和中)调用该点。

然后,建立了两个布雷森汉姆直线算法实例。参数化一个实例从L到R,第二个实例从L到M。同时运行x=x[l]到x[m]的算法。但是,不要绘制任何线条或打开任何像素,而是计算线条之间的像素。

从x[l]到x[m]后,将第二个bresenham的参数从m改为r,然后继续同时运行x=x[m]到x[r]的算法。

这与7小时前Erwin Smout提出的解决方案非常相似,但使用的是Bresenham而不是线性斜率公式。

我认为为了计算像素的列数,需要确定m是在线lr的上方还是下方,当然,当两个点具有相同的x或y坐标时,会出现特殊情况。但当这一点出现时,你的面试官会适当地感到敬畏,你可以继续下一个问题。

快速n'dirty伪代码:

-- Declare triangle
p1 2DPoint = (x1, y1);
p2 2DPoint = (x2, y2);
p3 2DPoint = (x3, y3);
triangle [2DPoint] := [p1, p2, p3];

-- Bounding box
xmin float = min(triangle[][0]);
xmax float = max(triangle[][0]);
ymin float = min(triangle[][1]);
ymax float = max(triangle[][1]);

result [[float]];

-- Points in bounding box might be inside the triangle
for x in xmin .. xmax {
  for y in ymin .. ymax {
    if a line starting in (x, y) and going in any direction crosses one, and only one, of the lines between the points in the triangle, or hits exactly one of the corners of the triangle {
      result[result.count] = (x, y);
    }
  }
}

我有这个主意-

设a(x1,y1),b(x2,y2)和c(x3,y3)为三角形的顶点。“count”是构成三角形的整数点的数目。

如果我们需要三角形边上的点,那么使用欧几里得距离公式 http://en.wikipedia.org/wiki/Euclidean_distance ,三边的长度都可以确定。 所有三个边的长度之和-3,将给出这个计数。

为了找到三角形内的点数,我们需要使用三角形填充算法,而不是执行实际的渲染,即执行drawpixel(x,y),只需遍历循环并在循环时不断更新计数。 三角形填充算法

计算机图形学基础 彼得·雪莉,迈克尔·阿什金

应该帮助。这里提到的 http://www.gidforums.com/t-20838.html

干杯

我要这样做:

取三角形的最高点(Y坐标最高的点)。从那一点开始有两个“斜坡”。这不是一般的解决方案,但为了便于可视化,请考虑“向左”(减少x坐标)和“向右”两种情况。

从这两个斜面和任何小于最高点的给定Y坐标,您应该能够计算出现在由斜面设置的边界内的整数点的数目。迭代减少Y坐标,将所有这些点相加。

当减少的Y坐标达到三角形的第二个最高点时停止。

现在,您已经计算了所有“第二个最高点以上”的点,现在剩下的问题是“计算某些点(小得多)内的所有点”。!!!)三角形,你知道它的上边和x轴平行。

重复同样的步骤,但现在用“最左边的点”代替“最上面的点”,用“增加x”代替“减少y”继续。

在那之后,剩下的问题是计算一个,再一次小得多的三角形中的所有整数点,你知道三角形的上边平行于x轴,左边平行于y轴。

不断重复(重复),直到你在你剩下的三角形中不计算任何点为止。

(我现在给你做作业了吗?)

(wierd)比蛮力强一点的伪代码(它应该有O(N))。
我希望你明白我的意思

n=0
p1,p2,p3 = order points by xcoordinate(p1,p2,p3)
for int i between p1.x and p2.x do
  a = (intersection point of the line p1-p2 and the line with x==i).y 
  b = (intersection point of the line p1-p3 and the line with x==i).y
  n += number of integers between floats (a, b)
end
for i between p2.x+1 and p3.x do
  a = (intersection point of the line p2-p3 and the line with x==i).y 
  b = (intersection point of the line p1-p3 and the line with x==i).y
  n += number of integers between floats (a, b)
end

此算法对于float类型的顶点相当容易扩展(只需要在“for i.”部分进行一些取整,p2.x的特殊情况是整数(此处,取整=向上取整))。
在实际的实现中也有一些优化的机会

我发现了一个非常有用的链接,它清楚地解释了这个问题的解决方案。我在坐标几何中很弱,所以我使用这个解决方案并在爪哇中编码它(至少对于我试过的测试案例)。

http://mathforum.org/library/drmath/view/55169.html

public int points(int[][] vertices){
      int interiorPoints = 0;
      double triangleArea = 0;
      int x1 = vertices[0][0], x2 = vertices[1][0], x3 = vertices[2][0];
      int y1 = vertices[0][1], y2 = vertices[1][1], y3 = vertices[2][1];

      triangleArea = Math.abs(((x1-x2)*(y1+y2))                             
                + ((x2-x3)*(y2+y3))
                + ((x3-x1)*(y3+y1)));

      triangleArea /=2;
      triangleArea++;

      interiorPoints = Math.abs(gcd(x1-x2,y1-y2))
                + Math.abs(gcd(x2-x3, y2-y3))
                + Math.abs(gcd(x3-x1, y3-y1));

      interiorPoints /=2;

      return  (int)(triangleArea - interiorPoints);
 }

下面是的python实现 @Prabhala's solution :

from collections import namedtuple
from fractions import gcd


def get_points(vertices):
    Point = namedtuple('Point', 'x,y')
    vertices = [Point(x, y) for x, y in vertices]

    a, b, c = vertices

    triangle_area = abs((a.x - b.x) * (a.y + b.y) + (b.x - c.x) * (b.y + c.y) + (c.x - a.x) * (c.y + a.y))
    triangle_area /= 2
    triangle_area += 1

    interior = abs(gcd(a.x - b.x, a.y - b.y)) + abs(gcd(b.x - c.x, b.y - c.y)) + abs(gcd(c.x - a.x, c.y - a.y))
    interior /= 2

    return triangle_area - interior

用途:

print(get_points([(-1, -1), (1, 0), (0, 1)]))  # 1
print(get_points([[2, 3], [6, 9], [10, 160]]))  # 289