Visiter les points dans un triangle dans un ordre aléatoire

Question

Pour un triangle rectangle spécifié par une équation ax + PAr < = c sur des entiers

Je veux tracer chaque pixel (*) dans le triangle une fois et une seule fois, dans un ordre pseudo-aléatoire, et sans stocker une liste de points de vie antérieurs.

Je sais comment faire cela avec un segment de ligne entre 0 et x

choisir un point'o aléatoire » le long de la ligne,
choix « p » qui est relativement premier x
répétition jusqu'à x fois: O _suivant = (O _{+ P} cur) MOD x

pour ce faire, un triangle, je voudrais
1. Nécessité de compter le nombre de pixels dans les listes sans triangle
2. mapper un 0..points entiers dans ax, y paire qui est un pixel valide à l'intérieur du triangle

j'espère pourrait être généralisé toute solution aux pyramides et aux formes dimensionnelles supérieures. (*) J'utilise le pixel CG terme pour la paire de points entiers X, Y de sorte que l'équation est satisfaite.

Answer 1

Puisque vous voulez garantir la visite de chaque pixel une seule fois, il est probablement préférable de penser en pixels plutôt qu'en vrais triangles. Vous pouvez découper les triangles horizontalement et obtenir une bande horizontale scan lines. Connectez les lignes de balayage ensemble et vous avez converti votre "triangle" en une longue ligne. Appliquez votre algorithme de visite de point à votre longue chaîne de lignes de balayage. D'ailleurs, cette cartographie ne doit se faire que sur papier, il vous suffit d'une fonction qui peut retourner (x, y) donné (t) le long de la ligne de balayage virtuelle.

Édition: Pour convertir deux points en segments de ligne, vous pouvez rechercher Bresenham's scan conversion. Une fois que vous avez converti les 3 segments de ligne en séries de points, vous pouvez placer tous les points dans un ensemble et grouper tous les points par y. Dans la même valeur y, trier les points par x. Le plus petit x dans une valeur y est le point de départ de la ligne de balayage et le plus grand x dans la valeur y est le point final de la ligne de balayage. Ceci est appelé "triangle de conversion de balayage". Vous pouvez trouver plus d'informations si vous Google.

Answer 2

Une méthode consiste à placer tous les pixels dans un tableau, puis de mélanger le tableau (c'est O (n)), puis visiter les pixels dans l'ordre dans le tableau mélangé. Cela pourrait nécessiter beaucoup de mémoire cependant.

Answer 3

Voici une méthode qui gaspille un peu de temps CPU mais ne gâche probablement pas autant qu'une méthode plus compliquée.

Calculez un rectangle qui circonscrit le triangle. Il sera facile de "linéariser" ce rectangle, chaque ligne de balayage suivie par la suivante. Utilisez l'algorithme que vous connaissez déjà pour parcourir les pixels du rectangle. Lorsque vous frappez chaque pixel, vérifiez si le pixel est dans le triangle et sinon, ignorez-le.

Answer 4

Voici une solution pour Triangle Point Picking.

Ce que vous avez à faire est de choisir deux vecteurs (côtés) de votre triangle, multipliez-les par un nombre aléatoire dans [0,1] et ajoutez-les. Cela fournira une distribution uniforme dans le quadrilatère défini par les vecteurs. Vous devrez vérifier si le résultat se trouve à l'intérieur du triangle d'origine; s'il ne le transforme pas en retour ou simplement le rejette et réessaye.

Answer 5

Je considérerais les lignes du triangle comme une seule ligne, qui est découpée en segments. Les segments seraient stockés dans un tableau où la longueur du segment serait également stockée ainsi que le décalage dans la longueur totale des lignes. Ensuite, en fonction de la valeur de O, vous pouvez sélectionner l'élément de tableau contenant le pixel que vous voulez dessiner à ce moment en fonction de cette information et peindre le pixel en fonction des valeurs de l'élément.