latticeCount.c

/*
 * Lattice point counter in C
 *
 * Works by using shoelace formula for area and then using Pick's theorem from
 * there in order to find internal lattice points. External lattice points are
 * found using gcd, which is implemented via the Euclidean Algorithm.
 */

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int x;
    int y;
} point;

int gcd(int a, int b)
{
    int t;
    while(b != 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int latticeCount(point pntList[], int pCount) // unsure if NELEMS works always
{
    int a = 0; // counter variables for shoelace formula
    int b = 0;
    int outerPoints = 0; // counter variable for outer lattice points

    for(int i = 0; i<pCount; i++)
    {
        a += pntList[i].x * pntList[(i + 1) % pCount].y; // shoelace formula
        b += pntList[i].y * pntList[(i + 1) % pCount].x; // modulos for bounds

        int cx = abs(pntList[(i + 1) % pCount].x - pntList[i].x); // change in x
        int cy = abs(pntList[(i + 1) % pCount].y - pntList[i].y); // change in y

        outerPoints += gcd(cx, cy); // for counting outer lattice points
    }

    double area = abs(a - b) / 2;
    int latticePoints = area - (outerPoints / 2) + 1; // Pick's Theorem
    return latticePoints;
}

int main()
{
    point pointList[3] = {{3, -5},{-2, 5},{-3, 3}};

    int pointCount = latticeCount(pointList, 3);
    printf("Lattice points: %d\n", pointCount);
    return 0;
}