Y a-t-il de toute façon qui me permet de trouver tous les points d'intersection entre une ligne et une grille? (Les cercles d'intersection ne sont pas dessinés à l'échelle les uns avec les autres, je sais)
une force de force brutale consiste à calculer très intersection pour la grille xy avec la ligne, mais cet algorithme est terriblement inefficace ( Je recherche un meilleur algorithme à ce sujet. O (m * n) , où < code> m est le numéro de x grille et n est le numéro de y grille).
3 Réponses :
sonne comme si vous avez besoin d'un Analyseur différentiel numérique ou Algorithme de ligne de Bresenham . Bresenham est le même algorithme utilisé pour dessiner des lignes sur un bitmap; Dans ce cas, la coloration d'un pixel équivaut à la vérification des collisions sur ce carré.
Je crois que cela devrait être la réponse acceptée. L'utilisation d'un algorithme comme celui de Bresenham donnera aux points de grille de vérifier, puis à partir de là des points d'intersection individuels peuvent être calculés avec beaucoup plus de facilité - les composants horizontaux et verticaux sont tous connus.
Je ne suis pas sûr de bien comprendre la question. Est-ce ce que vous recherchez par hasard?
Je veux chaque point d'intersection entre la ligne rouge et la ligne de grille. Donc, les points sont (0, b) , ((hb) / m, h) , (w, mw + b) , (2W, 2wm + b) , ((2h-b) / m, 2h) , (3W, 3wm + b) et ainsi au
@DTB, rien manque. Mais je veux un algorithme efficace pour ça
Cela ressemble à un calcul par intersection pour moi. Je ne peux rien imaginer plus efficace que ça.
@DTB, si c'était le cas, cela serait terriblement inefficace. Considérez que vous avez une grille de 100 * 100, puis vous devez faire à 100 * 100 opération.
@Ngu bientôt Hui: Je ne comprends pas. La grille de ma réponse est composée de 5 lignes horizontales et 5 lignes verticales. La ligne rouge coupe avec les lignes de grille à 7 endroits. Pour trouver ces 7 intersections, vous devez effectuer au plus 10 calculs, pas 25.
@DTB, Ah, OK, vous avez raison. Mais n'y a-t-il pas d'autre moyen d'optimiser davantage la chose?
@Ngu bientôt Hui: Vous pouvez vous arrêter lorsque vous obtenez la première intersection en dehors de la grille. En variante, étant donné que toutes les intersections avec des lignes de grille horizontales et toutes les intersections avec des lignes de grille verticales sont équidistantes respectivement, vous pouvez simplement calculer la première intersection respectivement et obtenir les autres intersections en ajoutant le delta à plusieurs reprises. Quoi qu'il en soit, il faut 9 calculs pour l'exemple dans ma réponse.
Si la grille est alignée sur l'axe:
Si la grille est régulière, la distance entre les intersections avec chaque ligne horizontale sera la même. La même chose va aussi pour les lignes verticales. Vous pouvez simplement faire un simple algorithme itératif avec DX et DY dans ce cas.
La grille est-elle censée être régulière?
@Ignacio, oui la grille est régulière.