Elégant/Propre (cas spécial) en ligne Droite de la Grille de la Traversée de l'Algorithme?

Je suis de dépoussiérer un vieux projet de la mine. Une des choses qu'il avait à faire, étant donné une grille Cartésienne du système, et de deux places sur la grille, trouver une liste de toutes les cases d'une ligne joignant le centre de ces deux carrés permettrait de passer à travers.

Le cas particulier ici, c'est que tous les points de début et fin sont confinés à l'exact centre de places/cellules.

Voici quelques exemples -- avec des couples de l'échantillon de départ et les points de fin. Les places ombragées sont celles qui devraient être retourné par l'appel de fonction

retiré morts ImageShack lien - exemple

De départ et les points d'extrémité sont visés par les carrés ils sont. Dans l'image ci-dessus, en supposant que la partie inférieure gauche est [1,1], la ligne en bas à droite serait identifié comme [6,2] à [9,5].

Qui est, à partir de la (centre de l') carré sur la sixième colonne de la gauche, sur la deuxième rangée à partir du bas vers le centre (de la) carré sur la neuvième colonne de gauche, sur la cinquième rangée à partir du bas

Qui vraiment ne semble pas si compliqué que ça. Cependant, j'ai en quelque sorte semblait avoir trouvé un peu complexe algorithme en ligne et de les mettre en place.

Je me souviens que c'était très, très rapide. Comme, optimisé-pour-une-des centaines ou des milliers de fois par les cadres rapide.

Fondamentalement, il a sauté d'une frontière à la carrés de, le long de la ligne (les points où la ligne traverse les lignes de la grille). Il savait où le prochain point de passage était pour voir quels point de passage était plus proche-une horizontale ou une verticale -- et s'installe à la suivante.

Qui est une sorte de bon dans le concept, mais la mise en œuvre effective s'est avéré être assez pas-si-jolie, et j'ai peur que le niveau d'optimisation pourrait être trop élevé pour ce que j'ai pratiquement besoin (je suis à l'appel de cette traversée de l'algorithme de peut-être cinq ou six fois par minute).

Est-il un simple, facile à comprendre, transparent en droite ligne de la grille de la traversée de l'algorithme?

En termes de programmes:

def traverse(start_point,end_point)
  # returns a list of all squares that this line would pass through
end

où la donnée des coordonnées d'identifier les carrés eux-mêmes.

Quelques exemples:

traverse([0,0],[0,4])
# => [0,0], [0,1], [0,2], [0,3], [0,4]
traverse([0,0],[3,2])
# => [0,0], [0,1], [1,1], [2,1], [2,2], [3,2]
traverse([0,0],[3,3])
# => [0,0], [1,1], [2,2], [3,3]

Notez que les lignes qui se déplacent directement dans les virages ne devrait pas inclure des carrés sur le "aile" de la ligne.

(Bon ol' Bresenham de travail ici, mais c'est un peu en arrière de ce que je veux. Autant que je sache, pour l'utiliser, j'avais au fond de l'appliquer à la ligne, puis la numérisation de chaque carré de la grille pour de vrai ou faux. Impossible, ou au moins inélégante -- pour les grands réseaux)

(Je suis re-regarder dans Bresenham, et Bresenham algorithmes, en raison d'un malentendu de la mine)

Pour plus de précisions, une application possible de ce serait, si j'étais le stockage de tous mes objets dans un jeu à l'intérieur de zones (une grille), et j'ai un rayon, et que vous voulez voir quels objets le rayon touche. À l'aide de cet algorithme, j'ai pu tester le rayon de seulement les objets qui sont à l'intérieur des zones, à la place de chaque objet sur la carte.

La réelle utiliser dans mon application, c'est que chaque tuile a un effet associé avec elle, et un objet qui se déplace à travers un segment de ligne à chaque tour. À chaque tour, il est nécessaire de vérifier pour voir ce qui les places de l'objet a parcouru à travers, et par conséquent, les effets à appliquer à l'objet.

Noter que, à ce stade, la mise en œuvre actuelle, j'ai fait le travail. Cette question est surtout de la curiosité du but. Il y a un moyen plus simple...en quelque sorte...pour un problème simple.

Ce que je cherche exactement? Quelque chose de conceptuellement/soigné et propre. Aussi, j'ai réalisé que grâce à ce que je suis exactement de préciser, de tous les points de début et fin sont toujours au centre des carrés ou des cellules; donc peut-être quelque chose qui prend avantage de cette serait bien ainsi.

Où voulez-vous que les extrémités de la ligne à coins des carrés (si oui, lesquelles) ou dans les centres?
merci pour souligner l'ambiguïté; j'ai ajouté une photo de la clarification. Je veux dire les centres.
merci pour la clarification et de l'image - il est beaucoup plus claire

InformationsquelleAutor Justin L. | 2010-07-13

17

Ce que vous voulez, c'est un cas particulier d'un supercover, qui est de tous les pixels traversés par un objet géométrique. L'objet peut être une ligne ou d'un triangle, et il y a des généralisations à des dimensions supérieures.

De toute façon, voici une mise en œuvre pour des segments de ligne. Cette page compare également les supercover avec le résultat de l'algorithme de Bresenham - ils sont différents.
le texte d'alt http://eugen.dedu.free.fr/projects/bresenham/diff.png

Je ne sais pas si vous considérez l'algorithme il y a aussi élégant, le nettoyage, mais il semble assez simple à adapter le code et passer à d'autres parties de votre projet.

Par ailleurs, votre question implique que l'algorithme de Bresenham n'est pas efficace pour les grands réseaux. Ce n'est pas vrai - il génère, les pixels de la ligne. Vous n'avez pas à faire un test vrai ou faux pour chaque pixel de la grille.

Mise à jour 1: j'ai remarqué que sur la photo il y a deux "extra" carrés bleus que je crois que la ligne ne passe pas à travers. L'un d'eux est adjacente à la 'h' dans 'Cet algorithme". Je ne sais pas si cela reflète une erreur dans l'algorithme ou le diagramme (mais voir @kikito de commentaire ci-dessous).

En général, le " dur " cas sont probablement lorsque la ligne passe exactement en un point de grille. Je suppose que si vous utilisez virgule flottante qui flottent point d'erreur peut désordre vous dans ces cas. En d'autres termes, les algorithmes doivent probablement s'en tenir à l'arithmétique des nombres entiers.

Mise à jour 2: Une autre mise en œuvre.
- +1 surtout pour l'observation au sujet de Bresenham. Bresenham est le bon outil pour le travail (y compris éventuellement l'anticrénelage de version).
- Je vous remercie pour cette des propos de Bresenham. Ma compréhension de la il était imparfait (je pensais que c'était une façon de tester si un pixel a été une partie d'une ligne donnée). Mais je suis à la recherche dans l'algorithme de remplacement maintenant 🙂
- J'ai regardé à travers elle; honnêtement, je ne crois pas que l'algorithme dans le papier a beaucoup d'élégance par rapport à celle que j'ai déjà eu (voir a_m0d réponse de), mais je vais regarder dans supercover algorithmes.
- L: je suis d'accord que l'algorithme ressemble un peu désordonné et manque une explication simple. Mais évite de virgule flottante (qui peut gâcher le cas où la ligne va exactement en un point de grille).
- La virgule flottante d'évitement est assez soignée, en fait =)
- Je m'attends à ce que les cas où une ligne va exactement à travers une grille de point de former un Pythagoricien triple. Il devrait donc être facile de déterminer si une ligne a une chance de traverser un point de grille, il faut déterminer si elle correspond à une connu de Pythagore triple, où l'hypoténuse valeur n'est pas supérieure à la longueur de la ligne. Je pense que ce problème est rendu plus obscur par le fait que les lignes commencent entre les points de la grille plutôt que les points de la grille.
- "J'ai remarqué que sur la photo il y a deux "extra" carrés bleus que je crois que la ligne ne passe pas par" je pense que cette question est adressée par l'auteur à la fin de la page, où il dit: "Ici, nous avons supposé que si la ligne passe à travers un coin, les deux places sont tirées. Si vous souhaitez supprimer cela, vous pouvez simplement retirer la partie traitant du coin".
- Comme @DrewHall l'a déjà souligné: une version modifiée de l'anticrénelage version pourrait être utilisée aussi: en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm
InformationsquelleAutor brainjam
5

Un papier sur ce sujet peuvent être trouvées ici. C'est en ce qui concerne le raytracing, mais qui semble tout à fait approprié à ce que vous êtes après de toute façon, et je suppose que vous serez en mesure de travailler avec elle un peu.

Il y a aussi un autre papier ici, de traiter avec quelque chose de similaire.

Ces deux documents sont liés dans partie 4 de Jakko Bikkerexcellent des tutoriels sur le raytracing (qui comprennent également son code source, de sorte que vous pouvez parcourir /rechercher de mises en œuvre).
- Malheureusement, il semble que le premier document est exactement l'algorithme que je suis déjà. Il fait tout très bien; je voudrais juste trouver peut-être une qui était peut-être un peu plus élégant. Je ne pouvais pas trouver quoi que ce soit de la pertinence sur le deuxième article =/ mais merci pour les suggestions
- désolé combat que: - quel a été le chances de venir avec exactement le même papier?
- haha probablement petit. mais cela signifie seulement que vous et j'ai pensé la même lignée.
InformationsquelleAutor a_m0d
4

Il est très facile de l'algorithme pour Votre problème qui s'exécute en temps linéaire:
1. Étant donnés deux points A et B, déterminer les points d'intersection de la ligne (A, B) avec chaque ligne verticale de la grille, qui se trouve dans cet intervalle.
2. Insérer deux points d'intersection à l'intérieur des cellules contenant A et B au début/à la fin de la liste à partir du point 1.
3. Interpréter tous les deux sequent points d'intersection comme le min et le max de vecteurs d'un axe aligné rectangle et marquer toutes les cellules de la grille qui se trouvent à l'intérieur de ce rectangle (c'est très facile, à l'intersection de deux axes alignés rectangles), compte tenu en particulier, que le rectangle a une largeur de 1 et, par conséquent, n'occupe que 1 colonne de Votre grille)
Exemple:
```
+------+------+------+------+
|      |      |      |      |
|      |      | B    *      |
|      |      |/    |      |
+------+------*------+------+
|      |     /|      |      |
|      |    /|      |      |
|      |   / |      |      |
+------+--/---+------+------+
|      | /   |      |      |
|      |/    |      |      |
|      *      |      |      |
+-----/+------+------+------+
|    /|      |      |      |
*   A  |      |      |      |
|      |      |      |      |
+------+------+------+------+ 
```
"A" et "B" sont les points de terminaison de la ligne représentée par des "/". "*" les marques de points d'intersection de la ligne avec la grille. Les deux points d'intersection sont nécessaires afin de marquer les cellules qui contiennent Un & B et de gérer des cas particuliers comme l'A. x == B. x

Une optimisation de la mise en œuvre des besoins Θ(|B. x - A. x| + |B. y - A. y|) pour une ligne (A, B). De plus, on peut écrire cet algorithme pour déterminer les points d'intersection avec les lignes horizontales de la grille, si c'est plus facile pour l'opérateur.

Mise à jour: affaires Transfrontalières

Comme brainjam correctement le souligne dans sa réponse, les cas les plus sérieux sont ceux, quand une ligne va exactement en un point de grille. Supposons un tel cas se produit et l'arithmétique à virgule flottante opérations de renvoyer correctement un point d'intersection avec l'intégrale des coordonnées. Dans ce cas, l'algorithme proposé uniquement les marques de cellules appropriées (comme spécifié par l'image fournie par l'OP).

Cependant, la virgule flottante erreurs vont se produire tôt ou tard, et le rendement des résultats incorrects. De mon avis, même en utilisant le double ne suffira pas, et on doit passer à un Decimal type de numéro. Une optimisation de la mise en œuvre permettra d'effectuer Θ(|max.x - min.x|) ajouts sur ce type de données chacun prenant en Θ(log max.y) de temps. Cela signifie que, dans le pire des cas (la ligne ((0, 0), (N, N)) avec d'énormes N (> 10⁶) l'algorithme se dégrade à un O(N log N) le cas le pire moment de l'exécution. Même la commutation entre les verticales/horizontales de la grille de ligne de intersection de détection en fonction de la pente de la droite (A, B) n'aide pas dans ce pire des cas, mais il est certain que dans la moyenne des cas - je ne compte pour mettre en œuvre un tel changement si un profiler les rendements de la Decimal opérations du col de la bouteille.

Enfin, je peux imaginer que certains gens intelligents pourraient être en mesure de venir avec un O(N) solution qui est correctement traite de ce cas transfrontaliers. Toutes Vos suggestions sont les bienvenues!

Correction

brainjam souligné, qu'un type de données décimal n'est pas satisfaisante, même si elle peut représenter une précision arbitraire des nombres à virgule flottante, puisque, par exemple, ¹/₃ ne peut pas être correctement représentés. Par conséquent, on devrait utiliser une fraction type de données, qui doit être capable de gérer les affaires transfrontalières correctement. Thx brainjam! 🙂
- +1. Nice! Je pense que tous ces algorithmes peuvent être un peu prudent avec virgule flottante erreurs à éviter d'avoir des ennuis lorsque l'intersection est exactement sur un point de grille (mais les erreurs, il est un peu en dehors de la grille de point).
- (voir modifié réponse)
- L. LOL, je viens de remarquer, que l'algorithme que j'ai proposée est la même, que a_m0d des liens vers dans sa réponse (j'ai sauté le premier "ici") et qu'il est celui que Vous utilisez déjà. Que détestez-Vous au sujet de Votre algorithme? Je ne peux imaginer une belle mise en œuvre de celui - ci- malheureusement, tout ne peut pas être un one-liner. Peut-être un peu d'abstraction pourrait aider^^ ou à partir d'un code de golf xD.
- C'est en fait conceptuellement différente de la papier en a_m0d de réponse; il suit à travers les places de la prise de note à la fois horizontale et axes verticaux des intersections. Mais j'aime la généralisation qu'il doit se croisent toutes les places de entre le y intersections.
- si vous faites allusion à l'Python Decimal type, je ne pense pas qu'il vous achète beaucoup. 1/3 ne peuvent pas être représentés exactement. Cependant, le Python Fraction type devrait faire l'affaire.
- Je fais référence à une pseudo nombre décimal de type qui peut représenter une précision arbitraire des nombres à virgule flottante comme java BigDecimal par exemple. Mais oui, Vous avez raison, une fraction type est beaucoup mieux adapté pour cette tâche car il doit être capable de gérer les affaires transfrontalières.
InformationsquelleAutor Dave O.

Ici est une mise en œuvre simple en Python, à l'aide de numpy. Cependant, quelle est la matière utilisée ici est uniquement de la 2D, de vecteurs et de la composante par composante des opérations qui est plutôt courant. Le résultat semble assez élégant pour moi (~20 loc sans commentaires).

Ce n'est pas générale, car elle suppose tuiles sont centrés en entier coordonnées, tout en séparant les lignes apparaissent à chaque entier en plus de la moitié (0.5, 1.5, 2.5, etc.). Cela permet d'utiliser l'arrondissement pour obtenir carreau entier coordonnées de coordonnées monde (qui n'est pas réellement nécessaire dans votre cas particulier) et donne le nombre magique 0.5 pour déterminer quand nous avons atteint la dernière tuile.

Enfin, notons que cet algorithme ne traite pas exactement la traversée de la grille à une intersection.

import numpy as np

def raytrace(v0, v1):
    # The equation of the ray is v = v0 + t*d
    d = v1 - v0
    inc = np.sign(d)  # Gives the quadrant in which the ray progress

    # Rounding coordinates give us the current tile
    tile = np.array(np.round(v0), dtype=int)
    tiles = [tile]
    v = v0
    endtile = np.array(np.round(v1), dtype=int)

    # Continue as long as we are not in the last tile
    while np.max(np.abs(endtile - v)) > 0.5:
        # L = (Lx, Ly) where Lx is the x coordinate of the next vertical
        # line and Ly the y coordinate of the next horizontal line
        L = tile + 0.5*inc

        # Solve the equation v + d*t == L for t, simultaneously for the next
        # horizontal line and vertical line
        t = (L - v)/d

        if t[0] < t[1]:  # The vertical line is intersected first
            tile[0] += inc[0]
            v += t[0]*d
        else:  # The horizontal line is intersected first
            tile[1] += inc[1]
            v += t[1]*d

        tiles.append(tile)

    return tiles

InformationsquelleAutor Kolaru

Vous devez vous connecter pour publier un commentaire.

Mise à jour: affaires Transfrontalières

Correction