Discussion :

[Sylvain255]

Bonjour,
j'ai un ensemble E de N points (xi,yi), et je voudrais trouver les 3 points les plus éloignés les uns des autres (distance euclidienne). On doit pouvoir remplacer 3 par un autre nombre P.
Merci
Bien cordialement

[Guesset]

Bonjour,

J'aurais tendance à penser qu'ils appartiennent au contour convexe (comme par hasard 3 est le nombre de points minimal d'un contour convexe). Le contour réduit singulièrement le nombre de points sur lesquels une recherche exhaustive est possible et peut certainement être optimisée peut être en cherchant le troisième point proche de la médiatrice du segment des deux autres.

Enfin, cela mérite d'être vérifié car ce n'est qu'une réflexion à brule-pourpoint.

Salutations

[Flodelarab]

Bonjour

J'aime bien quand on précise "distance euclidienne", comme pour être exhaustif, alors que la distance euclidienne n'a du sens qu'entre deux points. Pas trois.
On cherche quoi ? Le polygone à p côtés qui a le plus grand périmètre ? La plus grande aire ? Autre ?

[Sylvain255]

je voulais dire distance euclidienne entre deux points parmi trois, il faut maximiser la distance entre les trois points deux à deux

[Flodelarab]

Voilà des précisions qui ne précisent rien.

Qu'est-ce qui est le plus optimal ? 6 6 6 ou 5 6 7 ? Et pourquoi ?

[Sylvain255]

c'est les trois points les plus éloignés les uns des autres parmi l'ensemble des points. Mais c'est sûr il peut y avoir plusieurs solutions possibles.

[Sylvain255]

j'ai trouvé ça :
https://flothesof.github.io/farthest-neighbors.html

après avoir lu cette page en diagonale je fais cet algo (trouver les M points les plus éloignés les uns des autres parmi N points) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
tableau de listes L
pour chacun des points P :
   L[P]={}
   Point S=P
   pour i de 1 à M-1
       distance_max=0
       Point R
       pour chacun des points Q <>P :
          si distance(S,Q)>distance_max alors
                distance_max=distance(S,Q)
                R=Q
          findi
       finpour
       L[P].add(R)
       S=R
    finpour
finPour
 
Liste Résultat
pour chaque liste I de L
     sommeMax=0
     si somme de L[i] >sommeMax alors
         sommeMax=somme de L[i]
         Résultat=L[i]
     finsi
finpour

[dourouc05]

c'est les trois points les plus éloignés les uns des autres parmi l'ensemble des points. Mais c'est sûr il peut y avoir plusieurs solutions possibles.

Tu ne réponds pas vraiment à la question de flodelarab. Que cherches-tu exactement à maximiser, c'est-à-dire une seule et unique expression mathématique ? Vu ton pseudocode, il s'agit de la somme des distances maximales par rapport à l'ensemble des autres points (X désigne l'ensemble de tes points et x_i un point en particulier) :



De ton texte, j'avais compris que tu voulais maximiser la distance entre les P points, que j'aurais écrit comme ceci (en utilisant la distance minimum pour écarter les points autant que possible, c'est-à-dire chercher à maximiser les "pires cas" que tu souhaites éviter, quand deux points sélectionnés sont proches) :

[Guesset]

Bonjour,

Si le but, tel que je l'ai compris, est de trouver un triplet de points (A, B, C) tel que D(A,B) + D(B,C) + D(C,A) maximal, L'algorithme ne me semble pas le bon.

Si j'ai bien compris (ce qui n'est pas sûr) les listes récupèrent les points qui dessinent un parcours maximal sans revenir sur le point courant P. Comme les points déjà utilisés ne sont pas interdits, je ne vois pas ce qui empêche d'avoir des boucles comme{@R1, @R2, @R1, @R2, @R1,...}. Peut être que M = 3 (pour le triplet) ?

Même si c'est le cas, le résultat sera un triplet qui maximise D(A,B) + D(B,C) ce qui ne correspond pas à l'objectif. Illustration :

Salutations

[wiwaxia]

Bonjour,

j'ai un ensemble E de N points (xi,yi), et je voudrais trouver les 3 points les plus éloignés les uns des autres (distance euclidienne). On doit pouvoir remplacer 3 par un autre nombre P

.
Je crois qu'il faut se préserver des complications, et que la première intuition de Guesset était la bonne: le triangle constitué des points les plus éloignés se caractérise par une aire maximale, aisément calculable:

S = (1/2)║MiMj×MiMk║ = (1/2)║MiMj×MjMk║

Deux triangles de même aire pourraient être départagés en retenant celui présentant la plus grande des distances minimales.

Le recours exclusif à ce dernier critère critère permettrait d'étendre la sélection sur un nombre quelconque (P) de points - sous réserve de l'alourdissement du procédé, exigeant le calcul de P(P- 1)/2 distances.

Dans le cas d'un nuage tridimensionnel, on pourrait aussi rechercher le tétraèdre de volume maximal, celui-ci étant proportionnel à la valeur absolue du déterminant de 3 vecteurs:

V = (1/6)│Det(MiMj, MiMk, MiMl)│ = (1/6)│Det(MiMj, MjMk, MkMl)│.

Les relations proposées impliquent l'intervention de distances euclidiennes, et conduisent à des résultats indépendants de l'ordre d'indexation du nuage de points.