Visitar los puntos en un triángulo en un orden aleatorio

Question

Para un triángulo rectángulo especificado por una ecuación ax + by < = c en números enteros

Quiero trazar cada píxel (*) en el triángulo de una vez y sólo una vez, en un orden pseudoaleatorio, y sin almacenar una lista de puntos de golpe previamente.

sé cómo hacer esto con un segmento de línea entre 0 y x

escoger un point'o al azar' a lo largo de la línea,
selección 'p' que es primo con x
repetición para un máximo de x veces: O _siguiente = (O _cur + P) MOD x

para hacer esto para un triángulo, lo haría
1. Necesidad de contar el número de píxeles de los sans triángulo enumera
2. Asignar un número entero en 0..points hacha, par y que es un píxel válido dentro del triángulo

espero cualquier solución podría generalizarse a las pirámides y formas dimensionales superiores.

(*) Utilizo el término CG pixel para el par de puntos enteros X, Y, de modo que se cumple la ecuación.

Answer 1

Dado que desea garantizar la visita de cada píxel una vez y solo una vez, probablemente sea mejor pensar en términos de píxeles en lugar de triángulos reales. Puede cortar los triángulos horizontalmente y obtener un montón de scan lines horizontal. Conecte las líneas de escaneo y habrá convertido su "triángulo" en una línea larga. Aplique su algoritmo de visita de puntos a su larga cadena de líneas de exploración.

Por cierto, este mapeo solo tiene que suceder en papel, todo lo que necesita es una función que pueda devolver (x, y) dado (t) a lo largo de la línea de escaneo virtual.

Editar: Para convertir dos puntos en un segmento de línea, puede buscar Bresenham's scan conversion. Una vez que obtenga los 3 segmentos de línea convertidos en series de puntos, puede poner todos los puntos en un cubo y agrupar todos los puntos en y. Dentro del mismo valor de y, ordena los puntos por x. La x más pequeña dentro de un valor y es el punto de inicio de la línea de escaneo y la x más grande dentro del valor y es el punto final de la línea de escaneo. Esto se llama "triángulo de conversión de escaneo". Puede encontrar más información si Google.

Answer 2

Un método es poner todos los píxeles en una matriz y luego mezclar la matriz (esto es O (n)), luego visitar los píxeles en el orden en la matriz mezclada. Sin embargo, esto podría requerir bastante memoria.

Answer 3

Este es un método que desperdicia algo de tiempo de CPU, pero probablemente no desperdicia tanto como lo haría un método más complicado.

Calcula un rectángulo que circunscribe el triángulo. Será fácil "linealizar" ese rectángulo, cada línea de exploración seguida de la siguiente. Usa el algoritmo que ya conoces para atravesar los píxeles del rectángulo. Cuando golpee cada pixel, verifique si el pixel está en el triángulo, y si no, omítelo.

Answer 4

Aquí hay una solución para Triangle Point Picking.

Lo que tienes que hacer es elegir dos vectores (lados) de tu triángulo, multiplicar cada uno con un número al azar en [0,1] y sumarlos. Esto proporcionará una distribución uniforme en el cuadrilátero definido por los vectores. Deberá verificar si el resultado se encuentra dentro del triángulo original; si no lo vuelve a transformar o simplemente lo descarta y vuelve a intentarlo.

Answer 5

Consideraría las líneas del triángulo como una sola línea, que se corta en segmentos. Los segmentos se almacenarían en una matriz donde la longitud del segmento también se almacena, así como el desplazamiento en la longitud total de las líneas. Luego, dependiendo del valor de O, puede seleccionar qué elemento de la matriz contiene el píxel que desea dibujar en ese momento en función de esta información y pintar el píxel en función de los valores en el elemento.