Discussion :

[ferraoun]

Bonsoir,

Important. Je dois écrire un programme en C, voici l'énoncé du problème:

J'ai une image satellite en format png sur laquelle je voudrais placer N antennes de relais. Sachant que ces antennes ne couvrent qu'un rayon de largeur R. Je cherche à écrire un programme en c qui calculer le meilleur emplacement pour ces n antennes de façon à obtenir la meilleure couverture possible. Pour cela, je dois savoir les altitudes du terrain qui se trouvent sur la carte. Mais comment faire?

[-mod- Problème d'algorithme et non de C. Déplacé]

[parp1]

Donne nous une image, as tu les informations d'altitude sur tes images?

si oui,par exemple, sur une image en niveau de gris, plus c'est blanc, plus c'est haut. il suffit de faire un seuillage, pour avoir les valeurs les plus blanche afin de déterminer les points stratégique potentiels pour y mettre des antennes, ensuite tu parcours ton image en regardant les distances de séparation entre antenne...

Après tu mets une antenne sur les pics les mieux placé.

[acx01b]

il y a un algorithme très simple qui convergera rapidement si la carte n'est pas trop grande

placer les n antennes au hasard
s = la surface couverte par les antennes
unsigned t = time(NULL);
while(time(NULL) < t + 60) { // boucler pendant 1 minute
prendre une antenne au hasard
enregistrer sa position
la deplacer au hasard
s2 = la surface couverte par les antennes
si (s2 < s) restaurer l'ancienne position de l'antenne
sinon s = s2
}

la proposition de parp1 peut être intéressante pour l'initialisation:
au lieu de mettre les antennes au hasard tu peux les placer au départ selon sa méthode, mais tu fais quand même des essais au hasard après

a+

[ToTo13]

Bonjour,

pour les altitudes, tu considère que ton image est en fait une carte d'élévation : un pixel de valeur 25 a une élévation de 255, etc.

Tu peux tenter de faire une opération de calcul des bassins versant pour avoir les lignes de partage des eaux et ainsi obtenir toutes les crêtes qui pourraient faire obstacle à la diffusion des ondes de tes antennes. C'est développé dans ImageJ.

Ensuite tu as plusieurs possibilités d'algorithme ne n'utilisant que les points des crêtes et des pics.

[acx01b]

salut toto13 je ne sais pas si tu as lu mon message

peux tu détailler tes possibilités d'algorithmes n'utilisant que les crêtes et les pics ?

et puis si c'est une carte toute plate, il suffit de faire un quadrillage régulier d'antennes, et je ne vois pas comment ton algo résoud cela

a+

[ToTo13]

salut toto13 je ne sais pas si tu as lu mon message

peux tu détailler tes possibilités d'algorithmes n'utilisant que les crêtes et les pics ?

et puis si c'est une carte toute plate, il suffit de faire un quadrillage régulier d'antennes, et je ne vois pas comment ton algo résoud cela

a+

1 - Oui, j'ai lu ton message, c'est le minimum avant de répondre.
2 - Pour ta carte, recherche du coté des cartes d'élévations ou volume sous la nappe. Comme je l'ai marqué avec une erreur, I(x,y) = 255 => hauteur en (x,y) = 255. Ca te permettra d'avoir le relief de ton terrain.
3 - Tu pourras peut être sortir les crêtes et les pics avec l'algorithme des bassins versant. Sinon l'extraction de pic et de crêtes est encore un problème ouvert, qu'il faut aborder de façon multi-échelle. Lis par exemple la thèse de Thi Thanh Hai TRAN qui traite de ce sujet.
Il y a aussi l'algorithme de Deriche, voir Canny/Deriche.
4 - Un fois que tu as les crètes et les pics, tu peux calculer la portée d'une antenne placée sur n'importe quel point de crète.
Ensuite une petite méta-heuristique pourra résoudre le problème.