如何在任何给定三角形上使用Pick定理

Question

所以我想计算任何给定三角形内的点数.我知道我必须使用Pick的定理,但是我的代码最终会被大量的if-else if语句用于测试每个案例.我一直用这个作为指导在形成三角形的三个点内有多少个整数点？,但最终得到这个(顶点是一个由3个数组组成的数组.每个数组是三角形顶点的(x,y)坐标):

    int maxX = Math.max(Math.max(vertices[0][0], vertices[1][0]), vertices[2][0]),
        minX = Math.min(Math.min(vertices[0][0], vertices[1][0]), vertices[2][0]),
        maxY = Math.max(Math.max(vertices[0][1], vertices[1][1]), vertices[2][1]),
        minY = Math.min(Math.min(vertices[0][1], vertices[1][1]), vertices[2][1]);

    int height = Math.abs(maxY - minY),
        width = Math.abs(maxX - minX);

    double area = Math.abs(((vertices[0][0] * (vertices[1][1] - vertices[2][1]
                   )) + (vertices[1][0] * (vertices[2][1] - vertices[0][1]))
                   + vertices[2][0] * (vertices[0][1] - vertices[1][1])) / 2);


    if ((vertices[0][0] == vertices[1][0]) && (vertices[0][1] == vertices[2][1]))
    {
        area = ((Math.abs(vertices[0][1] - vertices[1][1]) - 1) *
                   (Math.abs(vertices[0][0] - vertices[2][0]) - 1)) / 2;
    }
    else if ((vertices[0][0] == vertices[2][0]) && (vertices[0][1] == vertices[1][1]))
    {
        area = ((Math.abs(vertices[0][1] - vertices[2][1]) - 1) *
                   (Math.abs(vertices[0][0] - vertices[1][0]) - 1)) / 2;
    }
    else if ((vertices[1][0] == vertices[2][0]) && (vertices[1][1] == vertices[0][1]))
    {
        area = ((Math.abs(vertices[1][1] - vertices[2][1]) - 1) *
                   (Math.abs(vertices[1][0] - vertices[0][0]) - 1)) / 2;
    }
    else if ((vertices[1][0] == vertices[2][0]) && (vertices[1][1] == vertices[0][1]))
    {
        area = ((Math.abs(vertices[1][1] - vertices[2][1]) - 1) *
                   (Math.abs(vertices[1][0] - vertices[0][0]) - 1)) / 2;
    }
    else if(vertices[0][0] == vertices[1][0])
    {
        int b = Math.abs(vertices[0][1] - vertices[1][1]);

        /*double dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
                    Math.pow(vertices[0][1] - vertices[2][1], 2)),
               dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
                    Math.pow(vertices[1][1] - vertices[2][1], 2));*/
        if (vertices[0][1] > vertices[1][1])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist2*/) / 2);
        }
        else if (vertices[0][1] < vertices[1][1])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist1*/) / 2);
        }
    }
    else if(vertices[0][0] == vertices[2][0])
    {
        int b = Math.abs(vertices[0][1] - vertices[2][1]);

        /*double dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
                    Math.pow(vertices[0][1] - vertices[1][1], 2)),
               dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) +
                    Math.pow(vertices[2][1] - vertices[1][1], 2));*/
        if (vertices[0][1] > vertices[2][1])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist2*/) / 2);
        }
        else if (vertices[0][1] < vertices[2][1])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist1*/) / 2);
        }
    }
    else if(vertices[1][0] == vertices[2][0])
    {
        int b = Math.abs(vertices[1][1] - vertices[2][1]);

        /*double dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[0][0], 2) +
                    Math.pow(vertices[1][1] - vertices[0][1], 2)),
               dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) +
                    Math.pow(vertices[2][1] - vertices[0][1], 2));*/
        if (vertices[1][1] > vertices[2][1])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist2*/) / 2);
        }
        else if (vertices[1][1] < vertices[2][1])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist1*/) / 2);
        }
    }
    else if(vertices[0][1] == vertices[1][1])
    {
        int b = Math.abs(vertices[0][0] - vertices[1][0]);

        /*double dist1 = Math.sqrt(Math.pow(vertices[0][1] - vertices[2][0], 2) +
                    Math.pow(vertices[0][1] - vertices[2][1], 2)),
               dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
                    Math.pow(vertices[1][1] - vertices[2][1], 2));*/
        if (vertices[0][0] > vertices[1][0])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist2*/) / 2);
        }
        else if (vertices[0][0] < vertices[1][0])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist1*/) / 2);
        }
    }
    else if(vertices[0][1] == vertices[2][1])
    {
        int b = Math.abs(vertices[0][0] - vertices[2][0]);

        /*double dist1 = Math.sqrt(Math.pow(vertices[0][1] - vertices[1][0], 2) +
                    Math.pow(vertices[0][1] - vertices[1][1], 2)),
               dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) +
                    Math.pow(vertices[2][1] - vertices[1][1], 2));*/
        if (vertices[0][0] > vertices[2][0])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist2*/) / 2);
        }
        else if (vertices[0][0] < vertices[2][0])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist1*/) / 2);
        }
    }
    else if(vertices[1][1] == vertices[2][1])
    {
        int b = Math.abs(vertices[1][0] - vertices[2][0]);

        /*double dist1 = Math.sqrt(Math.pow(vertices[1][1] - vertices[0][0], 2) +
                    Math.pow(vertices[1][1] - vertices[0][1], 2)),
               dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) +
                    Math.pow(vertices[2][1] - vertices[0][1], 2));*/
        if (vertices[1][0] > vertices[2][0])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist2*/) / 2);
        }
        else if (vertices[1][0] < vertices[2][0])
        {
            area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
                    (height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
                    /*- dist1*/) / 2);
        }
    }
    else if (minX == vertices[0][0])
    {
        int a = 0,
            b = 0;

        /*double dist1 = 0,
               dist2 = 0,
               dist3 = 0;*/

        if(Math.min(vertices[1][0], vertices[2][0]) == vertices[1][0])
        {
            a = width - (vertices[1][0] - vertices[0][0]);
            b = height - (vertices [1][1] - vertices[0][1]);

            /*dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
                    Math.pow(vertices[0][1] - vertices[1][1], 2));
            dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
                    Math.pow(vertices[1][1] - vertices[2][1], 2));
            dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
                    Math.pow(vertices[0][1] - vertices[2][1], 2));*/
        }
        else if(Math.min(vertices[1][0], vertices[2][0]) == vertices[2][0])
        {
            a = width - (vertices[2][0] - vertices[0][0]);
            b = height - (vertices [2][1] - vertices[0][1]);

            /*dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
                    Math.pow(vertices[0][1] - vertices[2][1], 2));
            dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
                    Math.pow(vertices[1][1] - vertices[2][1], 2));
            dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
                    Math.pow(vertices[0][1] - vertices[1][1], 2));*/
        }

        area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1)
                    * (b - 1) /*- dist1*/) / 2) - (((width - a - 1) * (height - 1)
                    /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist3*/) / 2);
    }
    else if (minX == vertices[1][0])
    {
        int a = 0,
            b = 0;

        /*double dist1 = 0,
               dist2 = 0,
               dist3 = 0;*/

        if(Math.min(vertices[0][0], vertices[2][0]) == vertices[0][0])
        {
            a = width - (vertices[0][0] - vertices[1][0]);
            b = height - (vertices [0][1] - vertices[1][1]);

            /*dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[0][0], 2) +
                    Math.pow(vertices[1][1] - vertices[0][1], 2));
            dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
                    Math.pow(vertices[0][1] - vertices[2][1], 2));
            dist3 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
                    Math.pow(vertices[1][1] - vertices[2][1], 2));*/
        }
        else if(Math.min(vertices[0][0], vertices[2][0]) == vertices[2][0])
        {
            a = width - (vertices[2][0] - vertices[1][0]);
            b = height - (vertices [2][1] - vertices[1][1]);

            /*dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
                    Math.pow(vertices[1][1] - vertices[2][1], 2));
            dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
                    Math.pow(vertices[0][1] - vertices[2][1], 2));
            dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
                    Math.pow(vertices[0][1] - vertices[1][1], 2));*/
        }

        area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1)
                    * (b - 1) /*- dist1*/) / 2) - (((width - a - 1) * (height - 1)
                    /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist3*/) / 2);
    }
    else if (minX == vertices[2][0])
    {
        int a = 0,
            b = 0;

        /*double dist1 = 0,
               dist2 = 0,
               dist3 = 0;*/

        if(Math.min(vertices[0][0], vertices[1][0]) == vertices[0][0])
        {
            a = width - (vertices[0][0] - vertices[2][0]);
            b = height - (vertices [0][1] - vertices[2][1]);

            /*dist1 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) +
                    Math.pow(vertices[2][1] - vertices[0][1], 2));
            dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
                    Math.pow(vertices[0][1] - vertices[1][1], 2));
            dist3 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
                    Math.pow(vertices[1][1] - vertices[2][1], 2));*/
        }
        else if(Math.min(vertices[0][0], vertices[1][0]) == vertices[1][0])
        {
            a = width - (vertices[1][0] - vertices[2][0]);
            b = height - (vertices [1][1] - vertices[2][1]);

            /*dist1 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) +
                    Math.pow(vertices[2][1] - vertices[1][1], 2));
            dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
                    Math.pow(vertices[0][1] - vertices[2][1], 2));
            dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
                    Math.pow(vertices[0][1] - vertices[2][1], 2));*/
        }

        area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1)
                    * (b - 1) /*- dist1*/) / 2) - (((width - a - 1) * (height - 1)
                    /*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist3*/) / 2);
    }

有人可以帮我修复算法或给我一个更简单/更好的方法吗？这段代码几乎无法运行.

抱歉长代码,我不知道应该添加哪些部分,所以我把整个算法.

编辑:所以我将算法更改为此(感谢MBo):

public static int answer(int[][] vertices)
{
    int a = (Math.abs((vertices[1][0] - vertices[0][0]) * (vertices[2][1]
                - vertices[0][1]) - (vertices[2][0] - vertices[0][0]) *
                        (vertices[1][1] - vertices[0][1]))) / 2,
        b = pointsOnLine(vertices[0][0], vertices[0][1], vertices[1][0],
                vertices[1][1]) + pointsOnLine(vertices[1][0],
                vertices[1][1], vertices[2][0], vertices[2][1]) +
                pointsOnLine(vertices[0][0], vertices[0][1],
                vertices[2][0], vertices[2][1]),
           area = (2 * a - 2 - b) / 2;  // Also tried a + (b / 2) - 1;

    return (int)area;
}

public static int pointsOnLine(int x0, int y0, int x1, int y1)
{
    BigInteger b1 = BigInteger.valueOf(Math.abs(x1 - x0)),
               b2 = BigInteger.valueOf(Math.abs(y1 - y0));

    return b1.gcd(b2).intValue();
}

但是,我并不总能得到正确的答案.我做错什么了吗？

Answer 1

皮茨定理：
内部格点的数量

i = (2*A + 2 - b)/2

其中 A 是三角形面积，b 是边界处的格点数通过叉积
面积：

2*A = Abs (V[1].x-V[0].x)*(V[2].y-V[0].y) - (V[2].x-V[0].x)*(V[1].y-V[0].y))

点 (x0, y0)-(x1, y1) 之间边缘上的 NumPoints，包括第一个点，不包括最后一个点（GCD 是Great Common Divisor）：

function PointsOnLine(x0, y0, x1, y1) = GCD(Abs(x2-x1), Abs(y2-y1))

对于所有边：

b = PointsOnLine(V[0].x, V[0].y, V[1].x, V[1].y) + 
    PointsOnLine(V[1].x, V[1].y, V[2].x, V[2].y) + 
    PointsOnLine(V[0].x, V[0].y, V[2].x, V[2].y) 

现在你可以获得i