How to Use Pick's Theorem on Any Given Triangle

Question

So I want to calculate the number of points within any given triangle. I know I have to use Pick's Theorem, but my code ends up being ridiculously long with the amount of if-else if statements to test for every case. I've been using this as a guide How many integer points within the three points forming a triangle?, but then end up with this (vertices is an array of 3 arrays. Each array is the (x, y) coordinates of a vertex of the triangle):

    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);
    }

Could someone help me either fix the algorithm or give me an easier/better way to do this? This code pretty much never works.

Sorry about the long code, I didn't know what parts I should add so I put the whole algorithm.

Edit: So I changed the algorithm to this (Thanks to 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();
}

But, I don't always get the right answer. Did I do something wrong?

It's in my answer: b = b -3; //because vertex had been counted twice. — David Pérez Cabrera, Jul 03 '15 at 17:43
@DavidPérezCabrera I added the b - 3, but I still get wrong answers. — flamespirit919, Jul 03 '15 at 18:03
Could you give me the vertices and the expected result? did you tried with my algorithm? — David Pérez Cabrera, Jul 03 '15 at 18:04
@DavidPérezCabrera (2, 3), (6, 9), (10, 160), ans: 289 This one works. (91207, 89566), (-88690, -83026), (67100, 47194), ans: 1,730,960,165. This one gives me a number that's way off. — flamespirit919, Jul 03 '15 at 18:15

score 3 · Accepted Answer · edited Apr 13 '17 at 12:19

Picks theorem:
Number of lattice points inside

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

where A is area of triangle, b is number of lattice points at the borders
Area through crossproduct:

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))

NumPoints on the edge between points (x0, y0)-(x1, y1), including the first point, excluding the last (GCD is Great Common Divisor):

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

for all edges:

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)

Now you can get i

David Pérez Cabrera · Answer 2 · 2015-07-04T00:09:20.723

Based on @Mbo answer: [EDITED]

private static long gcd(long n0, long n1) {
    long a = n0;
    long b = n1;
    while (a != 0) {
        long temp = a;
        a = b % a;
        b = temp;
    }
    return b;
}

public static long pointOnLine(long[][] vertices) {        
    return gcd(Math.abs(vertices[0][0] - vertices[1][0]),
                Math.abs(vertices[0][1] - vertices[1][1])) + 
            gcd(Math.abs(vertices[1][0] - vertices[2][0]),
                Math.abs(vertices[1][1] - vertices[2][1])) + 
            gcd( Math.abs(vertices[2][0] - vertices[0][0]),
                Math.abs(vertices[2][1] - vertices[0][1]));
}

public static long area(long[][] vertices) {
    return 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]));
}

public static void main(String[] args) {
    long[][] vertices = {{91207, 89566}, {-88690, -83026}, {67100, 47194}};
    //long[][] vertices = {{2,3}, {6,9}, {10,160}};
    long i = (area(vertices) + 2 - pointOnLine(vertices)) / 2;
    System.out.println("points: " + i);

}

How to Use Pick's Theorem on Any Given Triangle

2 Answers2