Points les plus éloignés dans un groupe de points

Version imprimable

14/10/2022, 11h52
Sylvain255

Points les plus éloignés dans un groupe de points

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
14/10/2022, 15h57
Guesset

Arc réflexe

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
15/10/2022, 18h55
Flodelarab

Bonjour :coucou:

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 ?
15/10/2022, 20h09
Sylvain255

je voulais dire distance euclidienne entre deux points parmi trois, il faut maximiser la distance entre les trois points deux à deux
16/10/2022, 11h42
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 ?
16/10/2022, 11h45
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.

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:

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

17/10/2022, 12h37
dourouc05

Citation:

Envoyé par 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.

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) :

$Formule mathématique$

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) :

$Formule mathématique$
18/10/2022, 12h19
Guesset

1 pièce(s) jointe(s)

Presque

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 :

Pièce jointe 627451

Salutations
20/10/2022, 00h27
wiwaxia

Points les plus éloignés dans un groupe de points

Bonjour,

Citation:

Envoyé par Sylvain255

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.