Pontos de um grid dentro de um polígono

lattice points inside non-lattice polygon

Para polígonos formados por um grid de pontos equidistantes existe a fórmula de Pick para enumerar os pontos dentro do polígono. E quanto aos polígonos com vértices arbitrários?

Vamos processar cada uma das arestas do polígono individualmente e, depois disso, podemos somar a quantidade de pontos sob cada aresta, considerando suas orientações para escolher um sinal (como no cálculo da área de um polígono usando trapézios).

Antes de tudo, devemos observar que, se a aresta atual tiver pontos finais em $A=(x_1;y_1)$ and $B=(x_2;y_2)$ ela poderá ser representada como uma função linear:

$$y=y_1+(y_2-y_1) \cdot \dfrac{x-x_1}{x_2-x_1}=\left(\dfrac{y_2-y_1}{x_2-x_1}\right)\cdot x + \left(\dfrac{y_1x_2-x_1y_2}{x_2-x_1}\right)$$

$$y = k \cdot x + b,~k = \dfrac{y_2-y_1}{x_2-x_1},~b = \dfrac{y_1x_2-x_1y_2}{x_2-x_1}$$

Agora, faremos uma substituição $x=x'+\lceil x_1 \rceil$ para que $b' = b + k \cdot \lceil x_1 \rceil$. Isso nos permite trabalhar com $x_1'=0$ e $x_2'=x_2 - \lceil x_1 \rceil$. Vamos denotar $n = \lfloor x_2' \rfloor$.

Não somaremos pontos em $x = n$ e em $y = 0$ para a integridade do algoritmo. Eles podem ser adicionados manualmente posteriormente. Portanto, temos que somar $\sum\limits_{x'=0}^{n - 1} \lfloor k' \cdot x' + b'\rfloor$. Também assumimos que $k' \geq 0$ and $b'\geq 0$. Caso contrário, deve-se substituir $x'=-t$ e adicionar $\lceil|b'|\rceil$ em $b'$.

Vamos discutir como podemos avaliar uma soma $\sum\limits_{x=0}^{n - 1} \lfloor k \cdot x + b\rfloor$. Temos dois casos:

Análise de complexidade

Temos que contar no máximo $\dfrac{(k(n-1)+2b)n}{2}$ pontos. Entre eles, contaremos $\dfrac{\lfloor k \rfloor (n-1)+2\lfloor b \rfloor}{2}$ no primeiro passo. Podemos considerar que $b$ é insignificantemente pequeno porque podemos começar com um valor menor de $1$. Nesse caso, podemos dizer que contamos cerca de $\dfrac{\lfloor k \rfloor}{k} \geq \dfrac 1 2$ de todos os pontos. Assim, terminaremos com $O(\log n)$ etapas.

Implementação

Aqui está uma função simples que calcula o número de pontos inteiros $(x;y)$ para $0 \leq x < n$ and $0 < y \leq \lfloor k x+b\rfloor$:

int count_lattices(Fraction k, Fraction b, long long n) {
    auto fk = k.floor();
    auto fb = b.floor();
    auto cnt = 0LL;
    if (k >= 1 || b >= 1) {
        cnt += (fk * (n - 1) + 2 * fb) * n / 2;
        k -= fk;
        b -= fb;
    }
    auto t = k * n + b;
    auto ft = t.floor();
    if (ft >= 1) {
        cnt += count_lattices(1 / k, (t - t.floor()) / k, t.floor());
    }
    return cnt;
}

Aqui Fraction é uma classe que manipula números racionais. Na prática, parece que se todos os denominadores e numeradores estiverem no máximo no valor $C$(como valor absoluto) nas chamadas recursivas eles serão no máximo $C^2$ se continuar dividindo numeradores e denominadores pelo maior divisor comum. Dada essa suposição, podemos dizer que é possível usar doubles e exigir precisão $\varepsilon^2$("EPS") onde $\varepsilon$ é a precisão com a qual $k$ e $b$ são dados. Isso significa que(em floor) deve-se considerar os números como número inteiro, se diferirem no máximo em $\varepsilon^2$ de um inteiro.