J'ai donc écrit un calcul de la géométrie de la bibliothèque en Haskell parce que je ne pouvais pas en trouver un sur le Hackage, et j'ai pensé qu'il serait amusant de le faire de toute façon. Cependant, j'ai été bloqué pendant près d'une semaine sur un algorithme que j'ai juste ne peut pas sembler obtenir dans une belle "haskell-comme" la forme. Cet algorithme est la Bentley-Ottmann algorithme pour trouver les intersections dans un ensemble de segments de ligne. Si vous êtes familier avec l'algorithme, vous pouvez passer directement au dernier paragraphe de mon mendicité :)
La façon dont je choisis de mettre en œuvre cette fonction est une fonction qui prend une liste de segments de ligne et renvoie une liste de points, et les segments de lignes qui se croisent en ce point. Cela nous permet de traiter le cas où plusieurs segments se coupent au même point.
bentleyOttmann :: [Segment] -> [(Point, [Segment])]
L'algorithme de balayage en ligne de l'algorithme. On imagine une ligne de balayage de l'avion, faire algorithmique travailler à différents même points. Les points d'événement dans la Bentley-Ottmann algorithme sont:
- Le début de point de fin d'un segment de ligne.
- La fin de point de fin d'un segment de ligne.
- Le point d'intersection d'un ensemble de segments.
Note qu'un point d'événement peut être associé à plus d'un segment de ligne en plus d'une façon. Afin de garder une trace des segments qui correspondent aux points de fin, j'utilise une carte dans le paquet conteneurs. Les clés de cette carte sont les points, et les valeurs sont des listes de segments, marqué par si ils commencent à ce point, à la fin, à ce point, ou se croisent à ce point.
Le balayage de la ligne détermine l'ordre des points. Imaginez une ligne verticale de balayage de l'avion, s'arrêtant sur les points d'événement afin de faire le travail. Les points d'événement sont commandés par leur première valeur de x, avec de petits points étant traités en premier. De façon générique, c'est tout ce dont nous avons besoin. En cas dégénérés, les points d'événement peut avoir la même abscisse. Nous avons également commander par leurs coordonnées y, les points d'événement avec les petits et les coordonnées sont traitées en premier, si il y a une coordonnée x de la cravate.
Ainsi, la structure que j'utilise, naturellement, est une priorité de la file d'attente. Celui que j'utilise est de la des tas de paquet de Hackage.
Qu'est-ce que le travail que nous faisons à chaque point d'événement? Bien, d'abord, nous vérifions les segments qui sont associés à l'événement de point. Si il n'y a plus d'un, il est un point d'intersection. Nous pouvons ajouter à la liste des intersections, nous avons trouvé à ce jour.
Voici la partie la plus délicate. Alors que nous sommes de balayage à travers le plan, nous gardons la trace d'un ensemble de segments, a ordonné à l'égard du point où ils se croisent le balayage de la ligne. Lorsque nous traitons un point d'événement, nous avons d'abord supprimer tous les segments qui s'est terminée à ce point d'événement. Ensuite, tous les segments qui ont recoupé à ce point sont reprises dans l'ordre. Enfin, nous ajoutons des segments de commencer à ce point d'événement pour l'ensemble ordonné. Noter, que depuis ces segments se coupent au point d'événement, elles doivent être commandées à l'égard d'un balayage de la ligne qui est légèrement perturbé à l'avance.
À chaque événement, nous devons ajouter de tout nouveaux points d'événement, de nouvelles intersections qui se produisent. Parce que nous gardons la trace de l'ordre relatif des segments d'intersection de la ligne de balayage, nous faire une de deux choses:
Si nous avons échangé deux segments ou de l'ajout d'un nouveau segment, nous trouvons le bas (à l'égard de balayage de ligne) modifié segment, le plus haut modifié segment, et de les tester pour les intersections avec leurs immédiate non modifié voisins.
Si nous n'avons pas de swap ou d'ajouter de nouveaux segments, puis nous au moins enlevé un segment, et donc de faire de ses anciens voisins maintenant adjacentes. Les tests de ces nouveaux voisins pour l'intersection.
C'est la clé de la Bentley-Ottmann algorithme, que nous glissons à travers le plan, nous avons seulement un test de nouveau candidat segments avec leurs voisins. Cela signifie que nous avons battu le naïf O(n^2) algorithme lorsqu'il y a relativement peu d'intersections.
Mon problème (enfin, je suis désolé c'est tellement longue haleine) est ceci: je n'ai aucune idée de comment mettre en œuvre ce système de commande de la logique. Je ne peut pas utiliser les Données.Ensemble parce que la commande de changements que nous glissons. Je suis en train de mettre en œuvre ma propre structure de données afin de garder une trace de l'information, mais c'est crasseux, buggy, probablement inefficace, et aussi laid! Je déteste laide du code.
Je sais Haskell est tout au sujet de assez de code. Je crois aussi que si je ne peut pas mettre en œuvre un algorithme dans une jolie façon, cela signifie que je ne comprends pas vraiment. Quelqu'un peut-il me donner un aperçu de la propreté, de la mise en œuvre de cet algorithme?
Edit: j'ai un travail à mettre en œuvre maintenant. J'avais l'intention de travailler avec le générique d'entrée, ainsi que de multiples segments qui se coupent en un même point, et des segments verticaux. Il semble fonctionner sur ces intrants par les piètres les tests que j'ai fait. Il n'a pas de travail lorsque les segments se chevauchent. Je ne sais pas comment traiter avec les personnes encore. J'aimerais avoir des commentaires sur la façon de les accommoder. Actuellement, mon balayage de la ligne de structure assure le suivi de leur dans le même nœud, mais il n'utilise qu'un seul d'entre eux à l'intersection des tests, et peut donner des résultats incohérents.
Je me sers de Données.Ensemble pour ma file d'attente des événements, des Données.Carte pour la recherche, et la mise en œuvre d'arbres rouge-noir avec des fermetures éclair que j'ai basé hors de Okasaki dans son livre. Si mon extrait n'est pas suffisamment le contexte, je peux ajouter de plus.
J'aimerais avoir des conseils sur la restructuration de la mise en œuvre de sorte qu'il est... moins moche. Je ne peux pas dire de quelle façon correcte, il est et il me rend nerveux.
Le code peut être trouvé sur hpaste ici
