Étant donné n points sur un plan 2D, quel est le point tel que la distance de tous les points est minimisée? Ce point ne doit pas nécessairement provenir de l'ensemble des points donnés. Est-ce centroïde ou autre chose?Trouver le point le plus proche d'un ensemble de points dans le plan
Comment trouver tous ces points (s'il y en a plus d'un) avec un algorithme?
Ceci est connu comme le "Centre de Distance" et est différent du centroïde.
Premièrement, vous devez définir quelle mesure de distance vous utilisez. Si nous supposons que vous utilisez la métrique standard de d = sqrt ((x1-x2)^2 + (y1-y2)^2), alors elle n'est pas unique, et le problème est de minimiser cette somme.
L'exemple le plus simple pour montrer que cette réponse n'est pas unique est l'exemple de ligne droite. Tout point entre les deux points a une distance totale égale de tous les points.
Dans 1D, la réponse correcte sera toute réponse ayant le même nombre de points à droite et à gauche. Tant que cela est vrai, tout mouvement vers la gauche et vers la droite augmentera et diminuera les côtés gauche et droit du même montant, et laissera la même distance. Cela prouve également que le centroïde n'est pas nécessairement la bonne réponse.
Si nous étendons à 2D ce n'est plus le cas - car le sqrt fait peser le problème. Étonnamment pour moi, il ne semble pas y avoir d'algorithme standard! La page here semble utiliser une méthode de force brute. Je n'ai jamais su cela! Si je voulais utiliser un algorithme, je trouverais le point médian dans X et Y comme point de départ, puis utiliser un gradient descent algorithm - cela obtiendrait la réponse assez rapidement. Toute l'équation finit comme un quadratique, donc il semble qu'il devrait y avoir une solution exacte.
L'algorithme de force brute de votre premier lien ne le fait-il pas pour des points sur une sphère? –
Non, j'ai dit descente de gradient pour n points. Ecrivez votre fonction de score afin qu'elle calcule la distance totale à tous les n points, puis laissez votre fonction de descente minimiser cette valeur. Je ne vais pas ajouter de code au cas où ce serait des devoirs, ça devrait être facile à écrire. –
@ Matthijs, très probablement, je n'ai pas l'air trop dur. Merci de m'avoir signalé. C'est une question intéressante, n'est-ce pas? –
Il peut y avoir plus d'un point. Considérez un avion avec seulement deux points dessus. Ces points décrivent un segment de ligne. Tout point sur ce segment de ligne aura la même distance totale par rapport aux deux extrémités.
Alors, comment trouver tous ces points avec un algorithme? – nowonder
En fait, la réponse va être un simple polygone. La raison en est qu'une somme de fonctions convexes (comme la fonction de distance) est également convexe. Vous pourriez probablement trouver ses coordonnées exactes en commençant par un triangle et en ajoutant des points. Cependant, le faire naïvement serait «n^2». –
Un algo de force brute. pourrait vous donner les meilleurs résultats. Premièrement, localisez un rectangle/n'importe quel quadrilatère délimitant les points d'entrée. Enfin, pour chaque point à l'intérieur du rectangle, calculez la distance à partir d'autres points. Additionnez les distances du point de l'ensemble d'entrée. Dites que c'est le «coût» du point. Répétez pour chaque point et sélectionnez le point avec min. Coût.
L'intelligence peut également être ajoutée à l'algo. il peut éliminer les zones en fonction du coût moyen, etc ...
C'est comme ça que j'aborderais le problème au moins ... j'espère que cela aidera.
Mais il a une très grande complexité. Vérification de chaque point à l'intérieur du rectangle, comment faire, les coordonnées du point peuvent être n'importe quel nombre à virgule flottante. – nowonder
bien évidemment vous avez besoin d'une taille de pas, une distance minimale entre deux points consécutifs, un exemple simple utilisant C pourrait être: pour (int row = minR; row
Ceci est discuté en détail ici http://www.ddj.com/architect/184405252?pgno=1
C'était intéressant mais cela résout un problème différent. Le questionneur a demandé le point qui minimise la distance à tous les points. L'article DDJ trouve les deux points les plus proches les uns des autres. –
Ne fermez pas cela, les algorithmes de la géométrie sont tout à fait dans le cadre d'un débordement de pile –
est-il des devoirs? Aussi, dans quelle langue essayez-vous de mettre cela en œuvre? – Piskvor
Non ce n'est pas ses devoirs. J'étudie des algorithmes sur la géométrie computationnelle. Donc, j'ai un doute. Je le fais en C. – nowonder