Couverture radars et zones isolees

[rayane314]

Bonjour,
Mon professeur m'a proposé un problème en ISN sur lequel j'ai réfléchi et pour lequel je n'ai pas de début de piste de résolution.

Le problème :

On me donne une liste d'emplacement de radars omnidirectionnels de même portée que l'on peut représenter sur un graphe par des cercles de mêmes rayons.
Il existe des configurations ou des cercles créent des zones isolées de l'extérieur (des zones isolées que les radars n'atteignent pas) si la portées des radars atteint un seuil.
Cela donne :


Je dois créer un algorithme qui reçoit le nombre de radars et les coordonnées x,y des radars et qui renvoie 0 si quelque soit la portée des radars il n'y a aucune zone isolée, mais si il y'en a je doit renvoyer la portée minimale pour que ces zones soit bouchées.

Exemple:
4 radars aux positions (10,10); (10,-10); (-10,-10); et (-10;10)
Cela donne un carrée.
On voit qu'avec une portée de 5 il n'y a pas de zone isolée, mais qu'avec une portée de 10 il y a une. On renvoie donc 10xracine(2) qui est la portée minimale pour boucher cette zone.
Je dois dire qu'après maintes réflexions je n'entrevois aucune piste. Si quelqu'un en avais une je serais heureux qu'il la partage car ce problème me tient a coeur. Merci.

[Ericovitchi]

tu peux toujours faire un algorithme bestial qui teste tous les points avec un pas donné.
tu fais une double boucle qui fait varier les coordonnées du point à tester dans le plan.
tu testes s'il est à moins d'un rayon d'un radar ou pas (en faisant une nouvelle boucle et en testant SI (x-xR)²+(y-YR)² < R² ) si oui tu bascules une variable à vrai que tu as d'abord initialisé à faux (et puis tu peux afficher la position si tu veux, ou la dessiner sur un plan)
en sortie de la double boucle, on aura tester tous les points.
tu re-testes la variable et si elle affiche faux tu affiche un message disant qu'il y a des points non couverts.
tu peux aussi faire varier le rayon avec un pas donné et trouver le rayon minimal qui crée une couverture complète.

Par exemple, sous algobox, ça devrait être possible de dessiner les centres des radars, et les points non couverts et avoir une visualisation de la situation. Mais tu peux programmer également ça en visual basic par exemple, (et sans doute en Pyton ou en java etc ... ça dépend ce que tu connais déjà)

[rayane314]

J'ai tout à fait saisi là ou tu veux en venir et c'est faisable même si je dois donner un résultat a 10^-3 près et que les coordonnées sont comprises entre 0 et 10000 au moins ça marcherai et je t'en remercie ! Mais as-tu une idée de comment différencier un point non couvert isolé d'un point non couvert mais non isolé?

[Ericovitchi]

qu'est-ce que tu entends par "point isolé" ?

[rayane314]

Un point isolé est un point qui est dans une des zones rouges du schéma plus haut

[nodjim]

Quelle est la différence entre les pts entourés de cercles rouges et ceux de cercles noirs ?

[rayane314]

Quelle est la différence entre les pts entourés de cercles rouges et ceux de cercles noirs ?

Il n'y en a pas enfaite j'ai trouvé ce schéma sur internet pour illustrer mais j'ai pas fais attention..

J'ai trouvé un énoncé différent portant sur le même sujet.
C'est plus clair :

[nodjim]

Pour R=1/2: pas de jaloux, c'est étonnant, non ?

[fatal_error]

salut,

les centres des radars, c'est des noeuds.
(1) Tu crèes un graphe avec tous tes noeuds, et tu lies des noeuds si deux radars se couvrent (tu testes leur distance avec leur rayon).

Dans ton graphe, tu cherches tous les cycles (tels que les noeuds soient pas alignés... sur une droite)
Pour chacun de ces cycles, tu dois regarder si ya des jaloux, idem au milieu t'as de la zone non couverte.
Pour ca, un algorithme stupide est le suivant :
tu prends la distance de chacun des noeuds aux autre de ce cycle.
tu prends la plus petite des distance correspondant à mettons n_1 et n_2.
tu agrandis le rayon d'autant... pour que les radars associés se couvrent.
et tu réitères à partir de (1) avec ton nouveau rayon.

[rayane314]

nodjim: Pour un rayon de 1/2 il n'y a pas de jaloux oui mais pas pour un rayon de 1.
Et l'énoncé dit "Si quelle que soit la portée du routeur, il n'y a a jamais de jaloux renvoyez 0."

fatal_error:
alors ça j'y avais pas pensé et ça me parait être LA solution que mon professeur attends. Et pour le rayon pour le premier tour de boucle est-ce que je prends la plus petite distance entre deux nœuds ?

et a chaque tour est-ce que j'agrandis de n1n2 ou de n1n2-2r juste pour que les cercles soit tengeants ?

[fatal_error]

ben tu initilises r tel que les cercles les plus proches soient tangents.
et puis à chaque itération, tu te débrouilles pour que les cercles les plus proches soient...au moins tangents. (si tu as pas besoin d'augmenter r, alors t'as fini)

[rayane314]

Merci de ta remarquable aide je suis en train d'implémenter tout ça et je te tiens au courant.

[rayane314]

J'ai une autre question du coup.
Pour les cycles est-ce que je cherche les cycles sans cordes ou peut importe ?

[fatal_error]

je sais pas ce qu'est un cycle sans cordes, mais dtu devrais considérer les strongly connected components.
(idem des cycles tq si tu ajoutes un autre noeud, tu as plus un cycle)

[rayane314]

Pour ce dernier point je vois pas en quoi les strongly connected compenents peuvent m'aider a choisir quels cycles je prends en compte et lesquels non..

[fatal_error]

ben tu les prends tous en compte (par défaut).
pour t'épargner un peu de calcul, si tu as un cycle qui est contenu dans un plus grand cycle, alors tu considères que le plus grand cycle (d'où le strongly connected component).

enfin, faudra revoir la fonction d'agrandissement de rayon quand tu manipules un cycle, prendre la minimum distance entre deux noeuds de ce cycle n'est pas suffisant (si tu as deux noeuds cote à cote, ils sont évidemment connectés, donc on va pas agrandir le rayon)

[Ericovitchi]

si les centres de tes radars sont alignés et régulièrement espacés (ce que tu avais oublié de nous dire) alors le problème est beaucoup plus simple

[fatal_error]

bon, c'est pas si trivial en fait...
par exemple, si on considère l'algorithme suivant:

prendre toutes les strongly connected component

Code: Tout sélectionner

minRadius = 0
P le polygone definit par scc
pour chaque scc
 pour chaque noeud n
   S  minRadius, minRadius = r

sauf que ca marche pas forcément

on voit par ex que la zone en rouge est pas couverte...

Donc (à réfléchir un peu ce donc..) pour etre safe, il faut pour chaque noeud d'un cycle, faire en sorte qu'il soit au moins tangent à tous les autres.
la difficulté étant des lors de trouver les minimum cycles

[rayane314]

Sur ton schéma il suffit de relancer la recherche de cycle donc on revoit ce cycle et on le ferme a son tour avec un plus grand rayon

[fatal_error]

sauf que dans la première image, tu as un grand cycle (qui contient le plus petit)...et donc ton rayon va augmenter d'autant (ca fait un méga gros rayon...).
Donc quand tu vas itérer...
tu vas prendre le plus petit cycle (ok, pas besoin de toucher au rayon mettons)
puis tu vas trouver un autre cycle...(ok on augmente le rayon)
...
puis tu vas trouver le méga cycle, et là tu augmentes le rayon alors que c'est plus nécessaire.

Une idée je pense, c'est à partir de chaque scc, de décomposer le sousgraphe en des "faces" (sachant qu'on va se retrouver dans des cas non planaires au fur et à mesure qu'on augmente le rayon) qui correspondent à des cycles minimals et de updater le rayon pour chacun de ces cycles.