三角形内部的格点计数

Question

我有一个大三角形，称之为a，b，c。其中a = (x, y)等。

现在我想计算这个三角形所包含的整数点数量，所以我首先看了Pick's定理。第二种方法是生成由三角形的最大值和最小值绑定的点列表，然后检查每个点是否在三角形内。

我使用重心坐标法来实现这一点。它能够工作，但是我的三角形非常巨大，我的程序基本上是通过点来进行暴力破解。如何改进这个算法呢？

代码可在此处找到：https://bpaste.net/show/58433b6e389c

- Nopestradamus

---

Pick 定理有什么问题？ - David Eisenstat

@DavidEisenstat 嗯，首先，皮克定理只适用于整数三角形，因此如果一个坐标是有理/无理点，它就会失效... 当然，OP没有指定他/她正在处理什么类型的三角形，但说尝试了皮克定理，所以我想假设它是一个整数三角形？ - Hyacinth

Answer 1

这个问题可以并且应该使用皮克定理来解决。阅读文章以全面了解其工作原理，它适用于您能想到的任何多边形。因此，“皮克说”如果您想计算多边形的面积，您有以下公式：area = noOfInsidePoints + noOfBoundaryPoints /2 - 1。要计算任何多边形的面积，您可以使用以下代码，其中pc是表示多边形顶点的结构体数组。

float computeArea()
{
    float area = 0;
    for(int i=1;i<=n;++i) // n is the total number of vertices
        area += (pc[i].x*pc[i+1].y - pc[i+1].x*pc[i].y );
    if(area < 0)
        area *= (-1);
}

计算出区域后，我们需要计算多边形边界上的点的数量。可以使用以下方法完成：

int getBoundaryPoints()
{
    long left=0, right=0;
    int noPoints = 0;
    for(int i=1;i<=n;++i)
    {
        st = abst( pc[i].x - pc[i+1].x );
        right = abs( pc[i].y - pc[i+1].y );
        if(right == 0)
            right = left;
        if(left == 0)
            left = right;
        noPoints += gcd(left, right) +1;
    }
}

有了这个计算，我们可以找到内部的点数

noPointsInside = (computeArea() - (getBoundaryPoints() - n)) / 2 + 1;

最终时间复杂度：O(N) 最终内存复杂度：O(N)

- Iulian Popescu

Answer 2

三角形内格点数量：皮克定理

from operator import abs
def renj(pts):
    X=[]
    Y=[]
    for i in range(len(pts)):
        if i in [0,2,4]:                    #(0-x1, 1-y1) (2-x2,3-y2) (4-x3,5-y3)
            X.append(pts[i])
        else:   
            Y.append(pts[i])
    return [min(X), max(X), min(Y), max(Y)]             # returns the range for triangle.

def m(a,b):
    from math import e
    if b[0]-a[0]:
        return (b[1]-a[1])/(b[0]-a[0])
    return e

def test(a,b,z):                                        # creating function to check if z lies on line(ab)
    if m(a,b)==m(a,z):
        return 1
    return 0    

n=int(input())      
for i in range(n):
    points = list(map(int, input().split()))
    count = 0
    A=[points[0], points[1]]
    B=[points[2], points[3]]
    C=[points[4], points[5]]
    r = renj(points)
    for u in range(r[0], r[1]+1):
        for v in range(r[2], r[3]+1):
            Z=[u, v]
            if test(A,B,Z) or test(A,C,Z) or test(B, C, Z):
                count += 1
    aa=abs((A[0]*(B[1]-C[1])+B[0]*(C[1]-A[1])+C[0]*(A[1]-B[1]))/2)
    #print("are",aa)
    bb=count
    #print("b",bb)
    ii=(aa+1)-bb/2
    print(int(ii))

该解决方案基于：皮克定理

A + 1 = i + b/2

• A：三角形的面积

• i：内部点数

• b：边界点数，包括顶点

• 注意：仅适用于整数点。欢迎社区提出建议。

• 代码片段

  输入 用于整数输入。

  1                      # 三角形数量
  2 4 8 2 10 6           # x1 y1 x2 y2 x3 y3
  

  输出

  12        # 因为三角形中有12个点
  

- user16657590