Combien d'entiers points dans les trois points formant un triangle?

En supposant que les sommets sont au nombre entier coordonnées, vous pouvez obtenir la réponse par la construction d'un rectangle autour du triangle, comme expliqué dans Kyle Schultz Une Enquête de Choisir le Théorème de.

Pour un j x k rectangle, le nombre de l'intérieur de points est

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

Pour l'5 x 3 rectangle ci-dessous, il y a 8 intérieur des points.

_{(source: uga.edu)}

Pour les triangles avec un pied vertical (j) et d'un bras horizontal (k) le nombre de l'intérieur de points est donné par

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

où h est le nombre de points à l'intérieur du rectangle qui coïncident à l'hypoténuse des triangles (pas la longueur).

_{(source: uga.edu)}

Pour les triangles avec un côté vertical ou horizontal, le nombre de l'intérieur, les points (I) est donnée par

_{(source: uga.edu)}

où j, k, h1, h2, et b sont marqués dans le diagramme suivant

_{(source: uga.edu)}

Enfin, le cas de triangles sans la verticale ou à l'horizontale côtés peut être divisé en deux sous-cas, celui où la zone entourant le triangle formes de trois triangles, et où la région environnante forme trois triangles et un rectangle (voir les schémas ci-dessous).

Le nombre de l'intérieur, les points (I) dans le premier sous-cas est donné par

_{(source: uga.edu)}

où toutes les variables sont identifiées dans le schéma suivant

_{(source: uga.edu)}

Le nombre de l'intérieur, les points (I) dans le second sous-cas est donné par

_{(source: uga.edu)}

où toutes les variables sont identifiées dans le schéma suivant

_{(source: uga.edu)}

Mon réflexe serait de brute-forcer:

• Trouver le maximum et le minimum de l'étendue du triangle dans les directions x et y.
• En boucle sur toutes les combinaisons de nombre entier de points à l'intérieur de ces extensions.
• Pour chaque ensemble de points, utilisez l'un des tests standard (Même côté ou Barycentrique techniques, par exemple) pour voir si le point se trouve dans le triangle. Puisque ce genre de calcul est un composant d'algorithmes pour la détection des intersections entre les rayons/segments de ligne et de triangles, vous pouvez également vérifier ce lien pour plus d'info.

Ok, je vais proposer un algorithme, il ne sera pas brillant, mais il faudra travailler.

Abord, nous avons besoin d'un point dans le triangle d'essai. Je propose d'utiliser le "Barycentrique Technique", comme expliqué dans cet excellent billet:

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

Maintenant à l'algorithme:

1. soit (x1,y1) (x2,y2) (x3,y3) est le triangle de sommets

2. laisser ymin = sol(min(y1,y2,y3)) ymax = plafond(max(y1,y2,y3)) xmin = sol(min(x1,x2,x3)) ymax = plafond(max(x1,x2,3))

3. itération de xmin à xmax et ymin à ymax vous pouvez énumérer tous les entiers de points dans la zone rectangulaire qui contient le triangle

4. en utilisant le point dans le triangle de test, vous pouvez tester pour chaque point de l'énumération pour voir si elle est sur le triangle.

C'est simple, je pense qu'il peut être programmé en moins d'une demi-heure.

Voici une autre méthode, pas forcément le meilleur, mais assurez-vous d'impressionner les interviewer.

Tout d'abord, appelez le point le plus bas X co-ord 'L', le point le plus haut X co-ord 'R', et le reste des point 'M' (Gauche, Droit et central).

Ensuite, mis en place deux instances de Bresenham ligne de l'algorithme. Paramétrer un exemple de tirage de L à R, et la seconde à dessiner à partir de L à M. Exécuter les algorithmes simultanément pour X = X[L] X[M]. Mais au lieu de dessiner des lignes ou d'allumer les pixels, comptez le nombre de pixels entre les lignes.

Après progression de X[L] X[M], modifiez les paramètres de la deuxième Bresenham pour attirer de M à R, puis continuer à exécuter les algorithmes simultanément pour X = X[M] X[R].

Ceci est très similaire à la solution proposée par Erwin Smout 7 heures, mais à l'aide de Bresenham au lieu d'une ligne de pente de la formule.

Je pense que, pour compter les colonnes de pixels, vous aurez besoin de déterminer si M se situe au-dessus ou au-dessous de la ligne de LR, et bien sûr des cas particuliers surviennent lorsque deux points ont la même X ou Y à coordonner. Mais par le temps que cela arrive, votre interlocuteur sera suffisamment impressionné et vous pouvez passer à la question suivante.

J'ai cette idée -

Laisser Une(x1, y1), B(x2, y2) et(x3, y3) être les sommets du triangle. Laissez "compter" le nombre entier de points formant le triangle.

Si nous avons besoin de les points sur les bords des triangles, puis en utilisant la Distance Euclidienne formule http://en.wikipedia.org/wiki/Euclidean_distance, la longueur des trois côtés peut être établie.
La somme de la longueur des trois côtés - 3, donnerait qui comptent.

Pour trouver le nombre de points à l'intérieur du triangle, nous devons utiliser un triangle algorithme de remplissage et au lieu de faire le rendu réel c'est à dire l'exécution de drawpixel(x,y), il suffit d'aller à travers les boucles et les maintenir à jour le comte comme nous l'avons effectue une boucle.
Un triangle algorithme de remplissage de

Fondamentaux de l'infographie par
Peter Shirley,Michael Ashikhmin

devrait aider. Sa visée ici http://www.gidforums.com/t-20838.html

acclamations

(bizarre) pseudo-code pour un peu-mieux-que-brute-force (il doit avoir O(n))

j'espère que vous comprenez ce que je veux dire

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

cet algorithme est assez facile de le prolonger pour les sommets de type float (a seulement besoin d'une tour à l' "je.." partie, avec un cas particulier pour p2.x entier (y, arrondi=arrondi à la hausse))

et il y a certaines possibilités d'optimisation dans une véritable mise en œuvre

Ici est un Python de mise en œuvre de @Prabhala de la 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

Utilisation:

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