Calculer la distance à la ligne lissée

J'essaie de trouver la distance d'un point (en 4 dimensions, seulement 2 sont montrés ici) (toutes les croix colorées dans la figure) à une soi-disant frontière de Pareto (ligne noire). Cette ligne représente la meilleure représentation frontière de Pareto au cours d'un processus d'optimisation.Calculer la distance à la ligne lissée

Pareto = [[0.3875575798354123, -2.4122340425531914], [0.37707675586149786, -2.398936170212766], [0.38176077842761763, -2.4069148936170213], [0.4080534133844003, -2.4914285714285715], [0.35963459448268725, -2.3631532329495126], [0.34395217638838566, -2.3579931972789114], [0.32203302106516224, -2.344858156028369], [0.36742404637441123, -2.3886054421768708], [0.40461156254852226, -2.4141156462585034], [0.36387868122767975, -2.375], [0.3393199109776927, -2.348404255319149]]

En ce moment, je calcule la distance de tout point à la frontière Pareto comme ceci:

def dominates(row, rowCandidate): 
return all(r >= rc for r, rc in zip(row, rowCandidate)) 

def dist2Pareto(pareto,candidate): 
    listDist = [] 

    dominateN = 0 
    dominatePoss = 0 
    if len(pareto) >= 2: 
     for i in pareto: 
      if i != candidate: 
       dominatePoss += 1 
       dominate = dominates(candidate,i) 
       if dominate == True: 
        dominateN += 1 
       listDist.append(np.linalg.norm(np.array(i)-np.array(candidate))) 

     listDist.sort() 

     if dominateN == len(pareto): 
      print "beyond"    
      return listDist[0] 
     else: 
      return listDist[0]

Où je calcule la distance à chaque point de la ligne noire, et de récupérer la plus courte distance (distance jusqu'au point le plus proche de la Frontière connue). Cependant, je pense que je devrais calculer la distance au segment de ligne le plus proche à la place. Comment pourrais-je y parvenir?

Source

2015-11-11 Rodolphe

Ceci est une question d'algorithme, et serait probablement mieux migré vers l'un des autres sites SE ... mais lequel? Math.SE a beaucoup de succès pour "distance spline point". – smci

Eh bien, quand vous êtes capable de trouver les deux points les plus proches sur la frontière pareto, la connexion linéaire entre ces deux points est probablement l'élément de ligne le plus proche, n'est-ce pas? Ainsi, dans un deuxième temps, vous pouvez calculer la distance entre la ligne et le point. – jkalden

Prenons-nous cette approximation linéaire par morceaux, pas une spline réelle? – smci

La formule pour les coordonnées du point le plus proche sur la ligne est donnée here. Plus précisément, vous êtes intéressé par celui appelé "ligne définie par deux points". Pour la postérité, la formule est:

Parce que la frontière est relativement simple, vous pouvez faire une boucle à travers chaque segment de ligne à deux points de la frontière, et de calculer la distance la plus proche pour chaque, en gardant le plus petit. Vous pourriez introduire d'autres contraintes/pré-calculs pour limiter le nombre de calculs requis.

Source

2015-12-08 02:01:18 Benjamin

Votre formule est un peu difficile à extrapoler à des dimensions plus élevées, mais la dérivation peut être utilisée pour la ré-exprimer en termes de produits scalaires, ce qui la rendrait 100% applicable à la question originale. –

@ Mad Physicist: Oui, j'ai manqué cela dans la question originale. Il y a une bonne formulation ici: http://programmers.stackexchange.com/a/168577 – Benjamin

Aussi, c'est la distance à la ligne entière, pas le segment de ligne. Voir cet article pour quelques exemples de calculs dans différentes langues: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment –

Calculer la distance à la ligne lissée

Répondre

Questions connexes