Question

Point proche

  • 26 March 2019
  • 7 replies
  • 44 views
Y
Badge

Bonjour

 

j'ai un "nuage de points" et je cherche a les trier par distance :

le resultat attendu est le suivant:

le point 2 est proche du point 1, le point 5 est proche du point 2, le point 3 est proche du point 5 etc...

j'utilise un neighborfinder en candidates only

mais le probleme est que dans ce cas j'ai comme resultat

le point 2 est proche du point 1

et le point 1 est proche du 2

et je ne les trie pas

 

il faudrait que lorsque le point 1 est traité il "disparaisse"

 

je ne suis pas sur d’être très clair

merci a la communauté de votre aide

 

 

7 replies

Y
Badge

Je joins un petit schéma pour illustrer ce que je souhaite avoir

je cherche a obtenir une série de points ordonnées suivant leur proximite

merci

jdh
Rank
Badge +22

Alors en commençant par point 1, vous voulez trouver le point la plus proche qui n'est pas encore utiliser, ou connecter les points en ordre qui réduit le distance totale?

Starting with point 1, do you want to connect the next nearest point (that hasn't already been used), or do you want to connect the points so as to reduce the total distance (travelling salesman problem)?

Y
Badge

Oui c'est ca

trouver le point le plus proche qui n'est pas encore utilisé

au final on obtient en effet une serie avec le plus court chemin du point 1 au point 4 en passant par tous les points

 

merci

jdh
Rank
Badge +22

Si tu veux le chemin le plus court, ce n'est pas normalement d'aller toujours au point plus proche.

 

 

C'est un algorithm qui s'appelle Problème de Voyageur de commerce. https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce

 

 

@mark2atsafe a écrit un blogue y a quelques année https://www.safe.com/blog/2016/11/fmeevangelist158/

 

jdh
Rank
Badge +22

Voici un workbench qui creer le chemin le plus court entre le premier point et le dernier. Si l'ordre des points est sans importance, tu peux changer le paramètre "Reorder From-To Line" dans le ShortestPathFinder à "All Points"travellingsalesman.fmw

Y
Badge

Oui en effet cela devient tres complique si on cherche le chemin le plus court

dans mon cas je pars a partir du point 1 par exemple

 

j avais egalement imagine la solution par un traitement de liste en python par exemple

machbrown2

Hello,

To sort a cloud of points by distance such that each point is compared only once, you can use the following algorithm:

- Initialize an empty list sorted_points

-Iterate through each point in the original list.

-For each point, find its nearest neighbor from the remaining points using a neighbor-finding algorithm.

-Add the pair (current point, nearest neighbor) to sorted_points

-Remove both the current point and its nearest neighbor from the remaining points.

-Repeat steps 2-5 until all points are processed.

Ensure your neighbor-finding logic correctly identifies the nearest neighbor based on your distance metric. This approach ensures each point is considered and sorted only once.

Also visit python course in delhi.

Reply


Community Stats

28,707
Posts
109,478
Replies
36,552
Members
Terms & ConditionsCookie settings
A product of
Safe Software respectfully acknowledges that we live, learn and work on the traditional and unceded territories of the Kwantlen, Katzie, and Semiahmoo First Nations.