Point le plus proche d'un point donné
J'ai un ensemble K de pixels sélectionnés au hasard dans une image 2D. Pour chaque autre pixel de l'image, j'ai besoin de savoir quel pixel de l'ensemble K est le plus proche (en utilisant la mesure de distance sqrt(DX^2 + dy^2) standard). Je suis conscient qu'il peut y avoir plus d'une solution pour chaque pixel. Évidemment, cela peut être fait par force brute contre chaque pixel de l'ensemble, mais je préfère éviter cela car ce n'est pas efficace. D'autres bonnes suggestions?
Acclamations.
8 réponses
N'oubliez pas que vous n'avez pas besoin de vous embêter avec la racine carrée.
Si vous voulez juste trouver le plus proche (et pas la distance réelle), utilisez simplement dx^2 + dy^2, qui vous donnera la distance au carré de chaque élément, ce qui est tout aussi utile.
Si vous n'avez pas de structure de données enveloppant cette liste de pixels, vous devrez simplement les tester tous.
Si vous avez une certaine flexibilité, il y a beaucoup de bonnes façons de réduire la charge de travail. Faire un Quadtree , Ou conservez la liste triée des pixels (triés par x et triés par y) pour affiner votre recherche plus rapidement.
Je devrai être d'accord avec jk et Ewan pour faire un Diagramme de Voronoi . Cela va partitionner l'espace en polygones. Chaque point de K aura un polygone décrivant tous les points qui sont les plus proches de lui. Maintenant, quand vous obtenez une requête d'un point, vous devez trouver dans quel polygone il se trouve. Ce problème est appelé Point Location et peut être résolu en construisant une Carte trapézoïdale .
JK déjà lié à la création du diagramme Voronoi en utilisant algorithme de Fortune qui prend O(N log n) étapes de calcul et coûte O (N) espace.
Ce site vous montre comment faire un trapézoïdale carte et comment l'interroger. Vous pouvez également y trouver quelques limites:
Temps de création attendu: O (N log N)
Complexité de l'espace attendu: O (n)
Mais surtout, temps de requête attendu: O (log n). C'est (théoriquement) mieux que O (√n) de l'arbre kD.
Ma source(autre que les liens ci-dessus) est: Calcul Géométrie: algorithmes et applications , chapitres six et sept.
Vous y trouverez des informations détaillées sur les deux structures de données (y compris des preuves détaillées). La version Google books n'a qu'une partie de ce dont vous avez besoin, mais les autres liens devraient être suffisants pour votre objectif. Il suffit d'acheter le livre si vous êtes intéressé par ce genre de chose (c'est un bon livre).
La construction de Diagrammes de Voronoï est une branche de la Calcul de la Géométrie. La construction de Triangulations Delaunay implique des considérations similaires. Vous pouvez adapter l'un des algorithmes Delaunay suivants à vos besoins.
- algorithmes Flip
- incrémental
- diviser pour régner
- Sweepline
Mettez les points dans un arbre KD, après cela, il est très rapide de trouver le voisin le plus proche. Voir Cet article sur wikipedia pour plus de détails.
C'est ce qu'on appelle la recherche du voisin le plus proche. Donald Knuth l'a appelé le problème de la poste.
Il existe un certain nombre de solutions: recherche linéaire, hachage sensible à la localité, fichiers d'approximation vectorielle et partitionnement spatial.
Googler ceux-ci devrait aider.
Ce que vous essayez de faire est de construire un diagramme voronoi cela peut être fait dans O (N log n) en utilisant un plane sweep
Autre indice: la distance est toujours supérieure ou égale à chaque différence de coordonnées, et toujours inférieure ou égale à leur somme, c'est-à-dire
d >= dx, d >= dy, d <= dx + dy.
Cela pourrait vous aider à faire le tri plus efficacement.
Selon la densité de ce graphique est rempli de pixels, vous pourriez être mieux de chercher vers l'extérieur à partir de votre pixel d'origine.
J'ai programmé quelque chose comme ça pour une émulation de terminal graphique. Ce que j'ai fini par faire était de programmer un modèle de recherche en forme de spirale carrée qui a grandi à partir du point central, et je l'ai laissé grandir jusqu'à ce qu'il frappe quelque chose. C'était suffisamment rapide pour le but, même sur un vieux CPU.