¿Cuántos puntos enteros dentro de los tres puntos forman un triángulo?

Question

En realidad, este es un problema clásico, ya que el usuario SO Victor lo puso (en otro SO question con respecto a qué tareas hacer durante una entrevista).

No pude hacerlo en una hora (suspiro) Entonces, ¿cuál es el algoritmo que calcula el número de puntos enteros dentro de un triángulo?

EDIT: Supongamos que los vértices están en coordenadas enteras. (De lo contrario, se convierte en un problema para encontrar todos los puntos dentro del triángulo y luego restar todos los puntos flotantes para dejarlos solo con los puntos enteros, un problema menos elegante).

Answer 1

Suponiendo que los vértices están en coordenadas enteras, se puede obtener la respuesta mediante la construcción de un rectángulo alrededor del triángulo como se explica en Kyle Schultz de An Investigation of Pick's Theorem.

Para un j x k rectángulo, el número de puntos interiores es

I = (j – 1)(k – 1). 

para el rectángulo 5 x 3 a continuación, hay 8 puntos interiores.

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image008.jpg

Para triángulos con una pata vertical (j) y una pata horizontal (k) el número de puntos interiores está dada por

I = ((j – 1)(k – 1) - h)/2 

donde h es el número de puntos interior a la rectángulo que coinciden con la hipotenusa de los triángulos (no la longitud).

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image012.jpg

Para triángulos con un lado vertical o un lado horizontal, el número de puntos interiores (I) viene dada por

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula5.jpg

donde j, k, h1, h2, y b están marcadas en el siguiente diagrama

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Triangle3.jpg

Finalmente, TH El caso de triángulos sin lados verticales u horizontales se puede dividir en dos subcasos, uno donde el área que rodea el triángulo forma tres triángulos y otro donde el área circundante forma tres triángulos y un rectángulo (ver los diagramas a continuación).

El número de puntos interiores (I) en la primera sub-caso está dada por

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula7.jpg

donde todas las variables están marcados en el diagrama siguiente

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/triangle5.jpg

El el número de puntos interiores (I) en el segundo sub caso está dado por

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image042.png

donde todas las variables están marcados en el diagrama siguiente

alt text http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Main_files/image038.png

Answer 2

Ok Propondré un algoritmo, no será brillante, pero funcionará.

Primero, necesitaremos un punto en una prueba triangular. Propongo utilizar el "Baricéntrico Técnica", como se explica en este excelente post:

http://www.blackpawn.com/texts/pointinpoly/default.html

ahora al algoritmo:

1. let (x1, y1) (x2, y2) (x3 , y3) sea el triángulo vértices

2. let ymin = piso (min (y1, y2, y3)) ymax = techo (max (y1, y2, y3)) xmin = piso (min (x1, x2, x3)) ymax = techo (max (x1, x2,3))

3. la iteración de xmin a xmax y ymín a yMax puede enumerar todos los puntos enteros en la región rectangular que contiene el triángulo

4. utilizando el punto de prueba triangular se puede probar para cada punto de la enumeración para ver si se trata de en el triángulo

Es simple, creo que se puede programar en menos de media hora.

Answer 3

Esto se conoce como la prueba "Apuntar en el triángulo".

Aquí está un artículo con varias soluciones a este problema: Point in the Triangle Test.

Una forma común para comprobar si un punto se encuentra en un triángulo es encontrar los vectores que conecta el punto a cada uno de tres vértices del triángulo y suma de los ángulos entre aquellos vectores. Si la suma de los ángulos es 2 * pi (360 grados), entonces el punto es dentro del triángulo; de lo contrario, no lo es.

Answer 4

Mi reacción inmediata sería la de la fuerza bruta que:

• encontrar el máximo y el alcance mínimo del triángulo en las direcciones x e y.
• Circule sobre todas las combinaciones de puntos enteros dentro de esas extensiones.
• Para cada conjunto de puntos, utilice una de las pruebas estándar (Same side or Barycentric techniques, por ejemplo) para ver si el punto se encuentra dentro del triángulo. Dado que este tipo de cálculo es un componente de los algoritmos para detectar intersecciones entre rayos/segmentos de línea y triángulos, también puede marcar this link para obtener más información.

Answer 5

Solo tengo media respuesta para un método que no sea de fuerza bruta. Si los vértices fueran enteros, podrías reducirlos a averiguar cómo encontrar cuántos puntos enteros se intersecan los bordes. Con ese número y el área del triángulo (fórmula de Heron), puede usar el teorema de Pick para encontrar la cantidad de puntos enteros interiores.

Editar: para la otra mitad, al encontrar los puntos enteros que se cruzan con el borde, sospecho que es el mayor común denominador entre la diferencia x e y entre los puntos menos uno, o si la distancia menos uno si uno de los x o y las diferencias son cero.

Answer 6

n'dirty rápida pseudocódigo:

-- Declare triangle 
p1 2DPoint = (x1, y1); 
p2 2DPoint = (x2, y2); 
p3 2DPoint = (x3, y3); 
triangle [2DPoint] := [p1, p2, p3]; 

-- Bounding box 
xmin float = min(triangle[][0]); 
xmax float = max(triangle[][0]); 
ymin float = min(triangle[][1]); 
ymax float = max(triangle[][1]); 

result [[float]]; 

-- Points in bounding box might be inside the triangle 
for x in xmin .. xmax { 
    for y in ymin .. ymax { 
    if a line starting in (x, y) and going in any direction crosses one, and only one, of the lines between the points in the triangle, or hits exactly one of the corners of the triangle { 
     result[result.count] = (x, y); 
    } 
    } 
} 

Answer 7

tengo esta idea -

Sea A (x1, y1), B (x2, y2) y C (x3, y3) son los vértices del triángulo Deje que 'cuente' el número de puntos enteros que forman el triángulo.

Si necesitamos los puntos en los bordes del triángulo utilizando la fórmula Euclidiana Distancia http://en.wikipedia.org/wiki/Euclidean_distance, se puede determinar la longitud de los tres lados. La suma de la longitud de los tres lados - 3, daría esa cuenta.

Para encontrar el número de puntos dentro del triángulo necesitamos usar un algoritmo de relleno triangular y en lugar de hacer la representación real, es decir, ejecutar drawpixel (x, y), simplemente pasar por los bucles y seguir actualizando el conteo aunque. Un algoritmo de relleno triángulo de

Fundamentos de gráficos de ordenador de Peter Shirley, Michael Ashikhmin

debe ayudar. Sus mencionados aquí http://www.gidforums.com/t-20838.html

aplausos

Answer 8

me gustaría ir como esto:

Tome la punta del triángulo (el que tiene la más alta coordenada Y) hacia arriba. Hay dos "pendientes" que comienzan en ese punto. No es la solución general, pero para una visualización fácil, piense en una de las dos "yendo hacia la izquierda" (disminuyendo las coordenadas x) y la otra "yendo hacia la derecha".

Desde esas dos pendientes y cualquier coordenada Y dada menor que el punto más alto, debe poder calcular el número de puntos enteros que aparecen dentro de los límites establecidos por las pendientes. Al iterar sobre las coordenadas Y decrecientes, sume todos esos puntos.

Pare cuando las coordenadas Y decrecientes lleguen al segundo punto más alto del triángulo.

Has contado todos los puntos "por encima del segundo punto más alto", y ahora te queda el problema de "contar todos los puntos dentro de un triángulo (¡mucho más pequeño!), Del cual sabes que es el lado superior es paralelo al eje X.

Repita el mismo procedimiento, pero ahora con tomar el "punto más a la izquierda" en lugar del "más alto", y con el procedimiento "aumentando x", en lugar de "disminuyendo y".

Después de eso, te queda el problema de contar todos los puntos enteros dentro de un triángulo, una vez más mucho más pequeño, del cual sabes que su lado superior es paralelo al eje X, y su lado izquierdo es paralelo al Y -eje.

Sigue repitiendo (recurriendo), hasta que no cuentes ningún punto en el triángulo que te queda.

(¿He hecho ahora su tarea para usted?)

Answer 9

(extraño) pseudo-código para un-bit mejor que el de fuerza bruta (que debe tener O (n))
espero que entienda lo que quiero decir

n=0 
p1,p2,p3 = order points by xcoordinate(p1,p2,p3) 
for int i between p1.x and p2.x do 
    a = (intersection point of the line p1-p2 and the line with x==i).y 
    b = (intersection point of the line p1-p3 and the line with x==i).y 
    n += number of integers between floats (a, b) 
end 
for i between p2.x+1 and p3.x do 
    a = (intersection point of the line p2-p3 and the line with x==i).y 
    b = (intersection point of the line p1-p3 and the line with x==i).y 
    n += number of integers between floats (a, b) 
end 

este algoritmo es bastante fácil de extender por vértices de tipo float (sólo necesita un poco de partida en el "para i .." parte, con un caso especial f o ser p2.x entero (allí, redondean hacia abajo = redondean))
y hay algunas oportunidades para la optimización en una implementación real

Answer 10

Aquí hay otro método, no necesariamente la mejor, pero seguro para impresionar a cualquier entrevistador.

Primero, llame al punto con la coordenada X más baja 'L', el punto con la coordenada X más alta 'R', y el punto restante 'M' (Izquierda, Derecha y Medio).

Luego, configure dos instancias del algoritmo de línea Bresenham. Parametrice una instancia para dibujar de L a R, y la segunda para dibujar de L a M. Ejecute los algoritmos simultáneamente para X = X [L] a X [M]. Pero en lugar de dibujar líneas o activar los píxeles, cuente los píxeles entre las líneas.

Después de pasar de X [L] a X [M], cambie los parámetros del segundo Bresenham para dibujar de M a R, luego continúe ejecutando los algoritmos simultáneamente para X = X [M] a X [R] .

Esto es muy similar a la solución propuesta por Erwin Smout hace 7 horas, pero usando Bresenham en lugar de una fórmula de pendiente de línea.

Creo que para contar las columnas de píxeles, tendrá que determinar si M se encuentra por encima o por debajo de la línea LR, y por supuesto surgirán casos especiales cuando dos puntos tengan la misma coordenada X o Y . Pero cuando esto ocurra, su entrevistador quedará impresionado y podrá pasar a la siguiente pregunta.

Answer 11

teorema de Pick (http://en.wikipedia.org/wiki/Pick%27s_theorem) establece que la superficie de un polígono simple colocado en puntos enteros está dada por:

A = i + b/2 - 1 

Aquí A es la superficie del triángulo, i es el número de puntos interiores y b es el número de puntos límite.El número de puntos de contorno b se puede calcular fácilmente sumando el máximo común divisor de las pendientes de cada línea:

b = gcd(abs(p0x - p1x), abs(p0y - p1y)) 
    + gcd(abs(p1x - p2x), abs(p1y - p2y)) 
    + gcd(abs(p2x - p0x), abs(p2y - p0y)) 

La superficie también puede ser calculada. Para una fórmula que calcula la superficie, ver https://stackoverflow.com/a/14382692/2491535. La combinación de estos valores conocidos se puede calcular por:

i = A + 1 - b/2 

Answer 12

Encontré un enlace bastante útil que explica claramente la solución a este problema. Soy débil en la geometría de coordenadas, así que utiliza esta solución y codificado en Java que funciona (al menos para los casos de prueba que probé ..)

http://mathforum.org/library/drmath/view/55169.html

public int points(int[][] vertices){ 
     int interiorPoints = 0; 
     double triangleArea = 0; 
     int x1 = vertices[0][0], x2 = vertices[1][0], x3 = vertices[2][0]; 
     int y1 = vertices[0][1], y2 = vertices[1][1], y3 = vertices[2][1]; 

     triangleArea = Math.abs(((x1-x2)*(y1+y2))        
       + ((x2-x3)*(y2+y3)) 
       + ((x3-x1)*(y3+y1))); 

     triangleArea /=2; 
     triangleArea++; 

     interiorPoints = Math.abs(gcd(x1-x2,y1-y2)) 
       + Math.abs(gcd(x2-x3, y2-y3)) 
       + Math.abs(gcd(x3-x1, y3-y1)); 

     interiorPoints /=2; 

     return (int)(triangleArea - interiorPoints); 
} 

Answer 13

Aquí es una implementación de Python de @Prabhala's solution:

from collections import namedtuple 
from fractions import gcd 


def get_points(vertices): 
    Point = namedtuple('Point', 'x,y') 
    vertices = [Point(x, y) for x, y in vertices] 

    a, b, c = vertices 

    triangle_area = abs((a.x - b.x) * (a.y + b.y) + (b.x - c.x) * (b.y + c.y) + (c.x - a.x) * (c.y + a.y)) 
    triangle_area /= 2 
    triangle_area += 1 

    interior = abs(gcd(a.x - b.x, a.y - b.y)) + abs(gcd(b.x - c.x, b.y - c.y)) + abs(gcd(c.x - a.x, c.y - a.y)) 
    interior /= 2 

    return triangle_area - interior 

Uso:

print(get_points([(-1, -1), (1, 0), (0, 1)])) # 1 
print(get_points([[2, 3], [6, 9], [10, 160]])) # 289