Algorithme rapide pour trouver le x points les plus proches d'un point donné sur un plan

Je voudrais trouver un algorithme rapide pour trouver les x points les plus proches d'un point donné sur un plan.

Nous sommes en occupe pas trop de points (entre 1 000 et 100 000), mais j'ai besoin de x points les plus proches pour chaque de ces points. (où x est généralement entre 5 et 20.)

J'ai besoin de l'écrire en C#.

Un peu plus de contexte à propos du cas d'utilisation: Ces points sont des coordonnées sur une carte. (Je sais, cela signifie que nous ne sommes pas exactement parler d'un avion, mais j'espère pour éviter de faire face avec la projection de questions.) En fin de compte les points qui ont de nombreux autres points proches d'eux doit être affiché en rouge, les points qui n'ont pas trop de points proches d'eux doit être affiché en vert. Entre ces deux extremees les points sont sur un dégradé de couleur.

Je ne suis pas sûr que l'algorithme que vous proposez est la mieux adaptée à votre cas d'utilisation. Vous pourriez peut-être une boucle sur tous les points et de calculer un grossier fonction de densité de (2-D de l'histogramme). Ensuite, vous pouvez simplement la couleur de chaque point calculé la densité de la cellule, il est, peut-être en considérant les cellules voisines, trop.

OriginalL'auteur Michael Junk | 2012-02-02

  1. 14

    Ce que vous avez besoin est une structure de données appropriée pour l'organisation de points dans un plan. Le K-D-Arbre est souvent utilisé dans de telles situations. Voir k-d tree sur Wikipédia.

    Ici, j'ai trouvé une description générale de Algorithmes Géométriques

    Mise à JOUR

    J'ai porté une implémentation Java d'un KD-tree pour C#. Veuillez voir Utilisateur:Ojd/KD-Tree sur RoboWiki. Vous pouvez télécharger le code là ou vous pouvez télécharger CySoft.Collections.zip directement à partir de mon page d'accueil (seulement de téléchargement, pas de docu).

    L'amour, effectue beaucoup plus rapidement que la solution mentionnée ci-dessous.

    OriginalL'auteur Olivier Jacot-Descombes

  2. 10

    Pour un point donné (pas tous) et que le nombre de points n'est pas extrême, on pourrait calculer la distance de chaque point:

    var points = new List<Point>();
Point source = ...
....
var closestPoints = points.Where(point => point != source).
                           OrderBy(point => NotReallyDistanceButShouldDo(source, point)).
                           Take(20);

private double NotReallyDistanceButShouldDo(Point source, Point target)
{
   return Math.Pow(target.X - source.X, 2) + Math.Pow(target.Y - source.Y, 2);
}

    (J'ai utilisé x = 20)

    Les calculs sont basés sur les doubles, de sorte que le fpu devrait être en mesure de faire un travail décent ici.
    Notez que vous pouvez obtenir de meilleures performances si le Point est une classe plutôt que d'une struct.

    encore plus rapide: laissez les Mathématiques.Sqrt, il semble que vous n'avez pas besoin de connaître la distance exacte 🙂
    vrai, nous allons le rendre encore plus rapide
    pourquoi même appel à des Mathématiques.pow() ici? <code> double dx = cible.x - source.x; double dy = cible.y - source.y; return dxdx + dydy; </code>
    cette méthode est très inefficace. utilisation kd tree

    OriginalL'auteur vc 74

  3. 1

    Vous avez besoin de créer une fonction de distance, puis calculer la distance de chaque point et trier les résultats et prendre les x premiers.

    Si les résultats doivent être précis à 100%, alors vous pouvez utiliser la distance standard de la fonction:

    d = SQRT((x2 - x1)^2 + (y2 - y1)^2)

    l'utilisation de sqr racine n'est pas nécessaire, vous pouvez trier sur base de dx2 + dy2
    en fait, vous pouvez également effectuer un tri sur abs(dx) + abs(dy)
    Wow, c'est probablement le plus rapide.

    OriginalL'auteur Roy Dictus

  4. 1

    De le rendre plus efficace. permet de dire que la distance est k. Prendre tous les points avec les coordonnées x entre x-k x+k. aussi, y-k et y+k. Si vous avez enlevé tous les excès de coordonnées. maintenant, faire de la distance par (x-x1)^2 + (y-y1)^2. Faire un min tas de k éléments sur eux , et les ajouter au tas si nouveau point < min(tas). Vous avez maintenant la k minimum d'éléments dans le tas.

    OriginalL'auteur Kshitij Banerjee