J'ai un ensemble de points qui forment un chemin. Je voudrais déterminer la distance minimale de tout point donné à ce chemin. Le chemin pourrait ressembler à quelque chose comme ceci: où la première valeur est la coordonnée X et la deuxième coordonnée y. Le chemin est ouvert à la fin (il ne formera pas une boucle fermée) et est constitué de segments droits entre les points. Donc, donné un point, par exemple. Je ne cherche pas nécessairement une solution complète, mais tous les pointeurs et idées être apprécié. [90, 84] , comment calculer la distance la plus courte de ce point sur le chemin?
7 Réponses :
Il est possible de construire des cas pathologiques dans lesquels le segment de ligne la plus proche à un point P connecte deux points qui sont eux-mêmes plus éloignés de P que tout autre point sur le chemin. Par conséquent, à moins que je ne manque que quelque chose de très subtil, vous devez calculer la distance à chaque segment de ligne pour obtenir la distance la plus courte du chemin.
Voici un exemple simple: P>
(5,1)-(4,2)-(1,3)-(20,3)-(15,2)-(14,1)
La distance entre un point et une ligne est donnée par:
d = | (x_2 - x_1) (Y_1 - Y_0) - (x_1 - x_0) (Y_2 - Y_1) | / sqrt ((x_2 - x_1) ^ 2 - (y_2 - y_1) ^ 2),
qui est une expansion du produit DOT, où (x_0, y_0) sont les coordonnées du point, et (x_1, y_1) et (x_2, y_2) sont les points finaux de la ligne.
Il serait assez simple de calculer cela pour chaque ensemble de points, puis déterminez simplement lequel est le plus bas. Je ne suis pas convaincu qu'il n'y a pas de moyen plus élégant de le faire, mais je ne le sais pas. Bien que j'aimerais voir si quelqu'un ici répond avec un!
Edit: Désolé que les mathématiques ici ont l'air si désordonnée sans formatage. Voici une image de ce que cette équation ressemble bien:
Une autre modification: Comme Chris a signalé dans son poste, cela ne fonctionne pas si les points sont en ligne, c'est-à-dire si la ligne est définie par (0,0) - (0,1) et le point de (0,10). Comme il l'explique, vous devez vérifier pour vous assurer que le point d'être regardé n'est pas réellement sur le "chemin étendu" de la ligne elle-même. Si c'est le cas, c'est juste la distance entre le point final de plus près et le point. Tout crédit à Chris! 
(de Mathworld - une ressource Web Wolfram: Wolfram. com )
Vous devez utiliser une algèbre linéaire ( frissons ) pour calculer la distance du point sur chacune des lignes.
Voici un lien vers un article qui décrit les mathématiques: http: // mathforum. org / bibliothèque / drmath / vue / 55501.html
Et voici un jolie bonne bibliothèque . Vous devez examiner les méthodes appelées pointsegmentdistance . Un segment est apparemment une ligne qui commence à un point et se termine au deuxième point, alors qu'une ligne a deux points mais continuez à l'infini.
Vous devez d'abord trouver la distance la plus courte de chaque segment de ligne, puis vous choisissez la plus petite distance. Lorsque vous calculez la distance la plus courte, vous devez trouver le point le plus proche du segment de ligne. Si le point le plus proche n'est pas compris entre le point de départ et de fin, vous devez utiliser la distance pour démarrer ou le point de fin (selon la plus proche).
Cette page a des formules que vous aurez probablement besoin.
La distance d'un point C à un segment de ligne AB est la zone du parallélogramme ABCC '.
Alors, je viens de cela pour une seconde. Erekalper a déjà posté la distance entre un point et une ligne. Cependant, le problème de cette formule est qu'il suppose que la ligne a une longueur infinie, ce qui n'est pas le cas pour votre problème. Juste un exemple pour le problème: supposez une ligne simple qui va de (0,0) à (0,1) et un point avec des coordonnées (0,10). La formule postée ci-dessus retournerait la distance de 0, car si vous étendez la ligne, elle toucherait le point. Malheureusement, dans votre cas, la ligne se termine à (0,1), la distance est donc réellement de 9.
Ainsi, mon algorithme serait: vérifiez si les angles des points d'extrémité de vos lignes sont <= 90 °. Si tel est le cas, la distance la plus courte de ce chemin sera calculable par la formule déjà affichée. Sinon, la distance la plus courte est la distance à l'un des points d'extrémité. Faites ceci pour toutes les parties du chemin, choisissez le minimum
Désolé, je pense que vous devez avoir mal interprété la formule que j'ai postée? Cela suppose définitivement deux points de terminaison à n'importe quelle ligne, pas une longueur infinie. Sauf si je suis mal compris que vous dites ...
@eekalper: Vous avez également utilisé lien cette formule, et je l'interprète de telle sorte que Il crée un angle de 90 ° à la ligne et supposant donc que la ligne est de longueur infinie
La première formule de la page n'assume aucun critère final, correct. Mais j'ai référencé le deuxième type qui est répertorié là-bas, où la ligne a un début et une fin définitives. Dans ce cas, avec une algèbre linéaire, vous pouvez voir que la distance de point de ligne se trouve en faisant saillie la distance entre le point et un point d'extrémité sur un vecteur perpendiculaire à la ligne. Donc, ce vecteur est à 90 °, mais le point lui-même ne doit pas être.
@eekalper: La 2e formule utilise simplement une ligne définie via 2 points, pas nécessairement des points finaux. Il suffit d'entrer l'exemple que j'ai posté dans ma réponse. Votre formule retournera d = 0 au lieu de D = 9
Great Scott, tu as raison! J'avais totalement oublié un cas en ligne comme ça. Excellent appel! +1!
La meilleure chose à faire serait de trouver le point le plus proche d'une ligne (faire le chemin) mesurer la distance et passer le long du chemin (et stockez le point de la distance la plus courte).
+1 pour votre utilisation de la couleur et du formulaire. Je ne suis pas sûr que l'Internet est toujours prêt à contenir le contenu de vos nombreux cahiers gribouillés, mais peut-être que HTML5 nous rapprochera de cet objectif et que la tyrie du paragraphe linéaire et le contour recachant se termineront. :RÉ
Que fait le chemin entre les points? Segments de ligne droite?
@Recursive, oui, juste des lignes droites simples.