Bonjour bonjour, 

Je souhaite assigner un poids a un ensemble de N points (3D) en fonction de leur distance par rapport a un point de reference V. Une des methodes pour faire ca est l'inverse distance weighting (IDW, ou ponderation inverse a la distance en francais, je ne sais pas quelle appelation est la + repandue), mais en me basant sur l'article wikipedia, je ne comprends pas bien la formule.

Instinctivement, j'aurai tendance a faire quelque chose comme :

somme de 1 / ( |V-Ni|^p  )

pour i allant de 0 a nombre de points, et en faisant varier p pour influer sur l'interpolation.

Mon souci, c'est que quand mon point de reference V se trouve pile sur un des points de N, je me retrouve avec une division par 0. Comment contourner ce probleme ? Je n'ai rien trouve la dessus sur le wiki fr, et meme si le wiki anglais semble + detaille, ca ne m'aide pas davantage parce que je n'arrive pas a lire la formule (je precise que je n'ai pas vraiment un background de maths..^^). Je vois qu'ils prevoient la situation si la distance V->Ni est nulle, mais je ne comprends pas ce qu'on fait dans ce cas.

Est-ce que quelqu'un pourrait m'eclairer ?

Un grand merci d'avance =]

-
Edité par fruity' 29 décembre 2017 à 20:07:40

Bonjour Fruity,

Il te suffit de retourner zéro quand ton dénominateur est nul ... puis-ce que ça veut qu'il se trouve bien sur ton point d'origine (distance = 0).

Ce que je comprends dans l'équation c'est que la variable P permet d'accroître un écart sur l'ensemble de tes points - de manière individuel accroître la distance entre ton point de référence et ton point calculé. Pour éviter des difficultés avec un point de référence qui ne serait pas à l'origine du repère, tu peux tout simplement effectuer une translation.

En espérant t'avoir aidé.

Hello yarflam, 

J'ai pense a retourner 0, malheureusement on parle d'inverse distance et non de distance (i.e. + la distance est petite, + la valeur renvoyee (le poids) est grande). Techniquement, quand la distance est de 0, ca devrait retourner une grande valeur (etant donne que lim(1/0) tend vers l'infini, c'est coherent). C'est pour ca qu'il ne faut pas retourner 0, dans ce cas. Sur la page wiki, d'ailleurs, on voit qu'ils retournent queqlue chose d'autre 

En loccurrence Ui, mais je ne sais pas a quoi Ui correspond.

D'autres idees ?

Je ne sais pas trop comment appliquer cette équation.

Voici ce que j'aurais fait dans ton cas :

/* Assigner un poids à un ensemble de N points */
function inv_weights_points (points) {
	var i,
		output = [], // sortie
		origin = [0,0,0], // origine du repère
		listDist = [], // liste des distances
		dist_min = 0, // distance min.
		dist_max = 0, // distance max.
		dist = 0; // distance (temporaire)

	/* Calcul de toutes les distances, conserver en mémoire min-max */
	for(i=0; i < points.length; i++) {
		dist = dist_points(origin, points[i]);
		dist_min = (i ? Math.min(dist, dist_min) : dist);
		dist_max = Math.max(dist, dist_max);
		listDist.push(dist);
	}

	/* Assignation des poids */
	for(i=0; i < points.length; i++) {
		output.push({
			'weight': 1-(1/(dist_max-dist_min||1))*(listDist[i]-dist_min),
			'distance': listDist[i],
			'position': points[i]
		});
	}

	return output;
}

/* Retourner la distance entre deux points */
function dist_points (a, b) {
	return Math.sqrt(
		(b[0] - a[0]) * (b[0] - a[0]) +
		(b[1] - a[1]) * (b[1] - a[1]) +
		(b[2] - a[2]) * (b[2] - a[2])
	);
}

/* Liste de points */
var points = [
	[4, 3, 5],
	[5, 9, 12],
	[16, 14, 21],
	[21, 8, 3],
];

/* Affichage */
console.log(inv_weights_points(points));

La sortie donne :

[ { weight: 1,
    distance: 7.0710678118654755,
    position: [ 4, 3, 5 ] },
  { weight: 0.6168549003784898,
    distance: 15.811388300841896,
    position: [ 5, 9, 12 ] },
  { weight: 0,
    distance: 29.88310559496787,
    position: [ 16, 14, 21 ] },
  { weight: 0.3161285969287855,
    distance: 22.67156809750927,
    position: [ 21, 8, 3 ] } ]

En faisant le calcul 1-(1/(dist_max-dist_min||1))*(listDist[i]-dist_min) on obtient des poids entre 0 et 1 ; 1 étant le plus proche et 0 le plus lointain. Grâce à ça, tu peux même multiplier le résultat avec un ratio pour obtenir la valeur maximale que tu veux. Pas de problème de zéro avec la condition directement dans la division.

Qu'est-ce que tu en penses ?

-
Edité par yarflam 30 décembre 2017 à 19:38:37

salut yarflam !

Effectivement, bien vu ! j'avais un peu trop le nez dedans, et je voulais un peu trop appliquer exactement la formule wikipedia, jpense ! Je ne normalise pas de la meme maniere, mais l'idee est la meme, et c'est en lisant ce que tu as fait que ca m'a debloque, donc cool !

En gros, si la distance est de 0, le weight est de 1 et tous les autres points ont un weight de 0 !

Voila mon implementation en python (avec numpy as np). Merci encore pour l'aide =]

def assign_weights(O, pts):
    num_pts = len(pts)
    weights_vec = np.zeros([num_pts])
    # on mesure la dist a chaque point. Si elle est >0, rien de foufou, on fait 1/dist^2
    # si elle est =0, on peut pas avoir l'inverse, dc on ajoute -1 au vecteur de weights (ca pourrait etre -325, ou nimporte quel
    # autre chiffre, peu importe, c'est juste pour pouvoir le retrouver facilement par la suite)
    for i in xrange(num_pts):
        dist = np.linalg.norm(O - pts[i])
        inv_dist = 1./ np.power(dist, 2) if dist != 0 else -1
        weights_vec[i] = inv_dist

    # une fois qu'on a tous les weights, je check juste si ya un -1 dans le vecteur,
    # et si oui, ca veut dire que le vecteur devrait ressembler a un truc genre
    # [0,0,0,....,1,0,0...], puisque l'output est normalise. Donc je le recree manuellement
    if -1 in weights_vec:
        for i in xrange(len(weights_vec)):
            if weights_vec[i] == -1:
                weights_vec[i] = 1 
            else:
                weights_vec[i] = 0
    # dans le cas contraire, ben je normalise juste tout connement (weight / sum(weights)
    else:
        weights_vec = weights_vec / np.sum(weights_vec)
    return weights_vec

-
Edité par fruity' 2 janvier 2018 à 23:29:48