Je recherche une solution rapide pour le problème suivant:
J'ai un point fixe (disons la partie supérieure droite sur la ligne de mesure blanche) et doit trouver le point le plus proche sur une courbe en des points également espacés (la courbe inférieure). De plus, je le fais pour chaque point de la courbe supérieure pour dessiner les distances entre les courbes avec des couleurs différentes (trois niveaux: minimum [rouge], entre minimum et maximum [orange] et au-dessus de [vert]).
Ma solution actuelle est un compromis: je prends le point fixe, itérale à travers un intervalle arbitraire (E. g. 50 unités à gauche et à droite du point fixe) et calculez la distance de chaque paire. Cela permet d'économiser du pouvoir de la CPU, mais ce n'est ni élégant ni précis, car je pouvais manquer une distance minimale à l'extérieur de mon intervalle choisi.
Toute proposition d'algorithme plus rapide?
EDIT: ESPACALEMENT SPACÉED signifie que tous les points ont la même distance sur l'axe X, ceci est vrai pour les deux courbes. De plus, je n'ai pas besoin d'interpoler entre les points, cela prendrait trop de temps.
3 Réponses :
Plutôt qu'une distance arbitraire, vous pourriez peut-être itérer jusqu'à "hors de portée".
Dans votre exemple, supposons que vous commenciez avec le point sur la courbe supérieure en haut à droite de votre ligne. Puis déposez verticalement vers le bas, vous obtenez une distance de (par mes yeux) environ 200um.
Maintenant, vous pouvez passer à partir de points d'ici à des points de test jusqu'à ce que la distance horizontale soit 200um. Au-delà de cela, il est impossible d'obtenir une distance de moins de 200um.
Déplacement de gauche, la distance descend jusqu'à ce que vous trouviez le minimum de 150um, puis commence à augmenter à nouveau. Une fois que vous êtes 150um à gauche de votre point supérieur, il est impossible de battre le minimum que vous avez trouvé.
Si vous êtes parti en premier, vous n'auriez pas eu à aller jusqu'à présent à droite, de sorte qu'une optimisation suivie soit la direction dans laquelle la distance tombe, sinon travaille du milieu dans les deux sens à la fois.
Je ne sais pas combien d'unités UM 50 est, cela pourrait donc être plus lent ou plus rapide que ce que vous avez. Cela évite ce risque de manquer une valeur inférieure, cependant.
Puisque vous faites beaucoup de tests contre le même ensemble de points sur la courbe inférieure, vous pouvez l'améliorer de manière proportive en ignorant le fait que les points forment une courbe du tout. Collez-les tous dans un arbre K-D ou similaire et recherchez à plusieurs reprises. Ça s'appelle un Recherche de voisine la plus proche .
+1: Tant que nous ne pouvons pas faire d'autres hypothèses à la courbe (la valeur Y change uniquement avec les limites) Il s'agit de la méthode la plus rapide.
Nous n'avons en particulier aucun motif de savoir si la valeur de Y exactement 149um à droite de notre point de départ est égale à la valeur Y de notre point de départ en haut à droite. Si tel est le cas, c'est le point le plus proche de la courbe inférieure à notre point supérieur, mais la voie droite de la ligne droite passe en fait à travers la courbe supérieure. Ce qui pourrait "ne pas compter", je ne sais pas. Il pourrait également être physiquement invraisemblable - peut-être que le matériau ne peut peut-être pas tenir cette courbe serrée - dans laquelle nous pourrions arrêter de chercher plus tôt.
Merci pour vos suggestions. Je vais devoir expérimenter avec l'arbre de la K-D, cela prendra un certain temps.
Nous pouvons étiqueter la courbe supérieure Y = T (x) et la courbe inférieure Y = B (x). Étiquetez la fonction la plus proche x_b = c (x_t). Nous savons que la fonction la plus proche est faiblement monotone non diminuée car deux chemins les plus courts ne se croisent jamais.
Si vous savez que la fonction de distance D (x_t, x_b) n'a qu'un minimum local pour chaque X_T fixe (ceci se produit Si la courbe est "suffisamment lisse"), vous pouvez gagner du temps en "marche" la courbe: Si vous vous attendez à ce que X_B soit suffisamment lisse, mais que vous ne pouvez pas supposer Cela et vous voulez un résultat exact, marchez la courbe dans les deux sens. Où les résultats sont d'accord, ils sont corrects. Où ils sont en désaccord, courez une recherche complète entre les deux résultats (les plus à gauche et les maxima locaux la plus à droite). Échantillon le "bloc ambigu" dans une telle commande (division binaire) pour permettre la plus grande taille due à la monotonicité. comme un terrain d'entente: Marche de la courbe dans les deux sens. Si les résultats sont en désaccord, choisissez parmi les deux. Si vous pouvez garantir au plus deux maxima locales pour chaque X_T fixe, cela produit la solution optimale. Il y a toujours des cas pathologiques où la solution optimale n'est pas trouvée et contient un minimum local qui est flanqué de deux autres minima locaux pires que celui-ci. J'ose dire qu'il est rare de trouver un cas où la solution est loin d'être optimale (en supposant que le lisse y = b (x)).
Cela peut aider à identifier ce problème comme un Recherche la plus proche du voisinage problème. Ce lien inclut une bonne discussion sur les différents algorithmes utilisés pour cela. Si vous acceptez d'utiliser C ++ plutôt que le droit C, Ann ressemble à un bonne bibliothèque pour cela.
Il semble également que cette question ait été Demandé avant .
Merci pour la recommandation. Oui, j'ai aussi regardé les autres questions, mais j'espère que mon cas particulier avec ces courbes contigunes quitte la place pour une optimisation inhabituelle ou un raccourci.
Cela dépend de la définition de la forme de la courbe.
La courbe est la surface d'un matériau gravé et est échantillonnée à intervalles fixes. Je ne sais pas comment le décrire mieux en ce qui concerne votre commentaire.
Sont des points sur les deux courbes "également espacés"? Est-ce que "tout aussi espacé" signifie-t-il à des étapes X constantes, à des étapes diagonales constantes, ou quoi?
@ nullp01nter: il est donc essentiellement
point_n = (x_n, y_n) , oùx_n = h * n ety_n en fonction de la courbe?@ NullP01nter: Assez juste, je n'étais pas sûr de ce que "points aussi espacés" signifiait vraiment. Il est possible que le point d'approche le plus proche n'ait pas l'un des points mesurés de la courbe, c'est quelque part entre eux. Comment trouver cela dépend de la manière dont vous interpolez entre les points mesurés de la courbe: linéaire; Spline cubique; peu importe. Donc, vous faites déjà un compromis de précision pour la vitesse en comparant uniquement votre point avec les points mesurés de la courbe.
@ JWPAT7: Les points sont également espacés (étapes X constantes) sur les deux courbes.
@Stevejessop: À droite, mais j'ai besoin de mesurer entre des valeurs discrètes, l'interpolation serait surchargée.
@Zeta: Oui, avec H être un nombre entier.
Qu'est-ce qui empêche de multiples points sur la courbe de faire près de près? Le pire des cas pourrait être un demi-cercle parfait, où chaque point de la courbe est également proche de votre point unique.
Théoriquement, cela peut être le cas. Mais même si c'est le cas, la recherche minimale se termine, elle produira simplement le premier point minimum de mon approche ci-dessus. En pratique, toutes les coordonnées du point sont quantifiées et un demi-cercle parfait n'est pas possible.