¿Cómo calcular el número entero de vértices de un triángulo bidimensional?

Question

Imagina un triángulo rectángulo bidimensional dibujado en papel cuadriculado (un entramado), con la esquina derecha originada en (0,0). Cada unidad del papel cuadriculado tiene una anchura de 1 unidad. Las longitudes de la base y la altura de este triángulo pueden ser cualquier número real. ¿Existe una fórmula para determinar el número de puntos de la red que contiene el triángulo? Por punto de entramado, me refiero al lugar donde se cruzan las líneas en el papel cuadriculado, que es donde las coordenadas son valores enteros. La imagen (# 1) a continuación muestra un triángulo con área de 2 unidades cuadradas, que contiene 6 puntos de celosía.

Y otra imagen similar (#2), esta vez con el área del triángulo siendo de 7 unidades cuadradas, y conteniendo 13 puntos de celosía:

PREGUNTA: ¿Existe una fórmula para calcular el número de celosías para valores arbitrarios de base y altura?

Como antecedente, estoy haciendo esto como un pasatiempo mientras trato de resolver un desafío de programación de computadoras. He estudiado hasta cálculo-1 y cálculo-2 en la universidad, pero eso fue hace muchos años. Si desea más detalles, hágamelo saber.

Soy consciente de que esto podría resolverse algorítmicamente con bucles en un programa de ordenador. Pero el verdadero desafío implica el volumen de una hiperpirámide de N dimensiones, con valores dimensionales muy grandes, y un requisito para ser calculado en < 1 segundo. Así que espero una fórmula real.

EDIT: (he cambiado "puntos de vértice" por "puntos de celosía" arriba, después de encontrar una mejor terminología).

ACTUALIZACIÓN: El estudio del enlace de Somos me llevó al teorema de Pick ( https://en.wikipedia.org/wiki/Pick%27s_theorem ):

A = i + b/2 - 1
or
Area = Number_of_internal_lattice_points + Number_of_boundry_lattice_points/2 - 1

Puedo calcular el área total "A" a partir de la fórmula de un triángulo, utilizando una función Floor() para que las dimensiones se alineen con los puntos de la red, necesaria para el teorema de Pick. Estoy buscando (i+b), por lo que necesito determinar a continuación b. Eso sería:

  Floor(base_length)+1    +

  Floor(height_length)+1  +

  number_of_lattice_points_on_hypotenuse_not_including_end_points

Entonces, ¿cómo calcular el número de puntos enteros de la red que caerían en la hipotenusa?

La imagen (#3) de abajo tiene una pendiente (m) = subida / recorrido = -1/4.

Pero la imagen #2, desde arriba, tiene una pendiente de -2/7 y NO tiene puntos de red en la hipotenusa.

Pero si escaláramos este triángulo por el factor 2, tendríamos una pendiente de -4/14 y 1 punto de red en la hipotenusa.

Así que creo que los pasos generales serán:

• Hallar la pendiente (m) mediante Suelo(altura) / Suelo(base)
• Encuentre el mayor número entero N que pueda reducir la pendiente manteniendo el numerador y el denominador enteros.
• Este número N es el número de segmentos divididos de la hipotenusa. El número de puntos de la red es N-1

Answer 1

Creo que he encontrado la solución a esto. Lo presentaré como un breve programa en c. Hace uso de una llamada a gcd (mayor común denominador), que obtuve de aquí: https://en.wikipedia.org/wiki/Binary_GCD_algorithm

long latticePointsInTriangle(double base, double height) {
  long intBase = floor(base);
  long intHeight = floor(height);
  long gcdValue = gcd(intHeight, intBase);
  long numBoundryLatticePoints = intBase+1 + intHeight + (gcdValue - 1);
  double area = double(intBase) * double(intHeight) / 2;
  long numInternalLatticePoints = floor(area - numBoundryLatticePoints/2 + 1);
  return numBoundryLatticePoints + numInternalLatticePoints;
}

¡Agradezco la ayuda de Somas y poetasis!

EDIT: Permítanme matizar esta solución. Lo primero que hace el algoritmo es reducir la base y la altura a números enteros y esto reduce efectivamente el triángulo. Para algunas entradas, esto da una respuesta correcta. Pero he encontrado un ejemplo (base = 140/19, altura = 140/7) en el que esto provoca soluciones perdidas, y un recuento demasiado pequeño. De acuerdo con este post: ¿Contar los puntos de la red integral en un triángulo que puede no tener coordenadas enteras? parece que no hay una fórmula sencilla para calcular las entradas no enteras que no sea la suma cíclica.

ACTUALIZACIÓN:
He estado pensando en cómo compensar los vértices perdidos cuando se reduce un triángulo con longitudes reales (no enteras) a longitudes enteras según mi solución publicada anteriormente. Considere la siguiente imagen. Tiene que ser grande para mostrar los detalles sutiles:

La línea roja es la hipotenusa del triángulo de origen con dimensiones no enteras. La línea azul es la nueva hipotenusa después de reducirla a dimensiones enteras, para poder utilizar el Teorema de Pick. Los círculos negros están resaltando todos los vértices que se pierden al contar JUSTO con el Teorema de Pick. El recuento correcto tendría que ampliarse en esta cantidad.

Entonces, ¿cómo codificar eficientemente para estos? La siguiente imagen muestra el siguiente paso hacia una generalización

Finalmente, tengo la siguiente imagen:

Aquí parece que el número de puntos de celosía "perdidos" se puede calcular por sí mismo con una fórmula de área triangular.

Cosas de las que no estoy seguro:

• ¿Cómo afecta la función floor() a la hipotenusa de este triángulo? ¿Es una línea recta? Los puntos de este gráfico fueron calculados. Más adelante probaré con un conjunto de datos más grande y calcularé un valor delta entre cada uno y veré si hay variación.
• Sería bueno si pudiera probar si este enfoque funcionará para todas las entradas.
• Tengo que poner esto en un algoritmo final para actualizar el que publiqué arriba.

ACTUALIZACIÓN

• He realizado más cálculos y experimentos con conjuntos de datos más grandes. Diré que la graficación de los puntos de celosía perdidos NO forma confiablemente una hipotenusa recta.

Answer 2

Dado $(a,b)$ como longitudes de dos lados del triángulo, podemos calcular el número de puntos de la red en él ( $n$ ) de la siguiente manera:

1. Calcula la pendiente: $m=\frac b a$
2. Calcula el número de puntos de uno de los dos lados sumando $1$ a la longitud:
   $$c=b+1$$
3. Utiliza la siguiente fórmula:
   $$n=\sum^{a}_{k=0} \lfloor c-|km| \rfloor$$

Tenga en cuenta que: utilizamos el valor absoluto para $km$ porque la pendiente puede ser un número negativo, y la función suelo para eliminar la parte decimal.

Podemos resumir estos pasos en la siguiente fórmula utilizando $(a,b)$ sólo:

$$n=\sum^{a}_{k=0} \lfloor b+1-|k \left( \frac b a \right)| \rfloor$$