algorithm - triangulo - ¿Cuántos puntos enteros dentro de los tres puntos forman un triángulo?
demuestre que el triangulo cuyos vertices son es un triangulo rectangulo (13)
En realidad, este es un problema clásico, como lo puso el usuario Victor (en otra question sobre las tareas a realizar durante una entrevista).
No podría hacerlo en una hora (suspiro), ¿cuál es el algoritmo que calcula el número de puntos enteros dentro de un triángulo?
EDITAR : Suponga que los vértices están en coordenadas enteras. (de lo contrario, se convierte en un problema de encontrar todos los puntos dentro del triángulo y luego restar todos los puntos flotantes para que queden solo con los puntos enteros; un problema menos elegante).
(extraño) pseudo-código para un bit-mejor que la fuerza bruta (debería tener O (n))
Espero entiendas 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 para vértices de tipo float (solo necesita un poco de redondeo en la parte "para i ..", con un caso especial para p2.x que es entero (allí, redondeado hacia abajo = redondeado hacia arriba))
Y hay algunas oportunidades de optimización en una implementación real.
Aquí hay otro método, no necesariamente el mejor, pero que 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 centro).
Luego, configura dos instancias del algoritmo de línea de 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 cualquier píxel, 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 utilizando Bresenham en lugar de una fórmula de pendiente de línea.
Creo que para contar las columnas de píxeles, deberá 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 llegue el momento, su entrevistador estará sorprendido y podrá pasar a la siguiente pregunta.
Aquí hay una implementación de Python de la solución de @ Prabhala :
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
El teorema de Pick ( http://en.wikipedia.org/wiki/Pick%27s_theorem ) establece que la superficie de un polígono simple colocado en puntos enteros viene 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 de límite. El número de puntos de límite b se puede calcular fácilmente sumando el mayor divisor común 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 se puede calcular. Para una fórmula que calcula la superficie, consulte https://.com/a/14382692/2491535 . Combinando estos valores conocidos se puede calcular por:
i = A + 1 - b/2
Encontré un enlace bastante útil que explica claramente la solución a este problema. Soy débil en geometría de coordenadas, así que utilicé esta solución y la codifiqué 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);
}
Esto se denomina prueba "Punto en el triángulo".
Aquí hay un artículo con varias soluciones a este problema: Punto en la Prueba de triángulo .
Una forma común de verificar si un punto está en un triángulo es encontrar los vectores que conectan el punto a cada uno de los tres vértices del triángulo y sumar los ángulos entre esos vectores. Si la suma de los ángulos es 2 * pi (360 grados), entonces el punto está dentro del triángulo , de lo contrario no lo es.
Mi reacción instintiva sería forzarlo brutalmente:
- Encuentra la extensión máxima y mínima del triángulo en las direcciones x e y.
- Recorra todas las combinaciones de puntos enteros dentro de esas extensiones.
- Para cada conjunto de puntos, use una de las pruebas estándar ( técnicas del mismo lado o baricéntricas , por ejemplo) para ver si el punto se encuentra dentro del triángulo. Dado que este tipo de cálculo es un componente de algoritmos para detectar intersecciones entre rayos / segmentos de línea y triángulos, también puede consultar este enlace para obtener más información.
Ok, voy a proponer un algoritmo, no será brillante, pero funcionará.
Primero, necesitaremos un punto en la prueba del triángulo. Propongo usar la "técnica baricéntrica" como se explica en este excelente post:
http://www.blackpawn.com/texts/pointinpoly/default.html
Ahora al algoritmo:
sea (x1, y1) (x2, y2) (x3, y3) sean los vértices de triángulos
vamos ymin = piso (min (y1, y2, y3)) ymax = techo (max (y1, y2, y3)) xmin = piso (min (x1, x2, x3)) ymax = techo (max (x1, x2, 3))
iterando de xmin a xmax e ymin a ymax puede enumerar todos los puntos enteros en la región rectangular que contiene el triángulo
Al usar el punto en la prueba de triángulos, puedes probar cada punto de la enumeración para ver si está en el triángulo.
Es simple, creo que se puede programar en menos de media hora.
Pseudocódigo rápido de n''dirty:
-- 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);
}
}
}
Solo tengo la mitad de una respuesta para un método sin fuerza bruta. Si los vértices fueran enteros, podría reducirlos para 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), puedes usar el teorema de Pick para hallar el número de puntos enteros interiores.
Edición: para la otra mitad, encontrando los puntos enteros que intersectan el borde, sospecho que es el mayor denominador común entre la diferencia x y y entre los puntos menos uno, o si la distancia menos uno si una de las diferencias x o y es cero
Suponiendo que los vértices están en coordenadas enteras, puede obtener la respuesta construyendo un rectángulo alrededor del triángulo como se explica en el Teorema de una investigación de Pick de Kyle Schultz.
Para el rectángulo ajxk, el número de puntos interiores es
I = (j – 1)(k – 1).
Para el rectángulo 5 x 3 de abajo, hay 8 puntos interiores.
texto alt 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 viene dado por
I = ((j – 1)(k – 1) - h) / 2
donde h es el número de puntos en el interior del rectángulo que coinciden con la hipotenusa de los triángulos (no la longitud).
Para los triángulos con un lado vertical o un lado horizontal, el número de puntos interiores (I) viene dado por
texto alternativo http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula5.jpg
donde j, k, h1, h2 yb están marcados en el siguiente diagrama
texto alternativo http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Triangle3.jpg
Finalmente, el caso de triángulos sin lados verticales u horizontales se puede dividir en dos subcasos, uno donde el área que rodea al triángulo forma tres triángulos, y uno donde el área circundante forma tres triángulos y un rectángulo (vea los diagramas a continuación) .
El número de puntos interiores (I) en el primer subcaso viene dado por
texto alternativo http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/Pick_Formula7.jpg
Donde todas las variables están marcadas en el siguiente diagrama.
texto alternativo http://jwilson.coe.uga.edu/EMAT6680Fa05/Schultz/6690/Pick/triangle5.jpg
El número de puntos interiores (I) en el segundo subcaso viene dado por
Donde todas las variables están marcadas en el siguiente diagrama.
Tengo esta idea ...
Sean A (x1, y1), B (x2, y2) y C (x3, y3) los vértices del triángulo. Deje que ''contar'' sea 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 de Distancia Euclidiana http://en.wikipedia.org/wiki/Euclidean_distance , se puede determinar la longitud de los tres lados. La suma de longitud de los tres lados - 3, daría ese conteo.
Para encontrar el número de puntos dentro del triángulo, necesitamos usar un algoritmo de relleno de triángulo y, en lugar de hacer el renderizado real, es decir, ejecutar drawpixel (x, y), solo recorra los bucles y siga actualizando la cuenta mientras hacemos el bucle. Un algoritmo de relleno de triángulo de
Fundamentos de gráficos de computadora por Peter Shirley, Michael Ashikhmin
debería ayudar. Su referencia aquí http://www.gidforums.com/t-20838.html
aclamaciones
Yo iría así:
Tome el punto más alto del triángulo (el que tiene la coordenada Y más alta). Hay dos "pendientes" a partir de ese punto. No es la solución general, pero para una fácil visualización, piense en uno de los dos "ir a la izquierda" (disminuyendo las coordenadas x) y el otro "ir a la derecha".
A partir de 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. Iterando sobre las coordenadas Y decrecientes, sume todos esos puntos de puntos juntos.
Detente cuando tus coordenadas Y decrecientes alcancen el segundo punto más alto del triángulo.
Ahora ha contado todos los puntos "por encima del segundo punto más alto", y ahora tiene el problema de "contar todos los puntos dentro de algún triángulo (¡mucho más pequeño!), Del cual sabe que su lado superior es paralelo al Eje x
Repita el mismo procedimiento, pero ahora tome el "punto más a la izquierda" en lugar del "más alto" y continúe "aumentando x", en lugar de "disminuyendo y".
Después de eso, se queda con el problema de contar todos los puntos enteros dentro de un triángulo, una vez más mucho más pequeño, del cual sabe que su lado superior es paralelo al eje X, y su lado izquierdo es paralelo al eje Y.
Continúa repitiendo (recurriendo), hasta que no cuentes puntos en el triángulo que te quedan.
(¿He hecho tu tarea para ti?)