Couverture radars et zones isolees

[rayane314]

En gros tout le problème est dans le choix des cycles et cela revient a ma question initiale de trouver des cycles sans cordes : des cycles minimals autrement dit,sans autre chemins interieurs.

C'est comme les cordes des cercles

[fatal_error]

je vois pour l'instant deux possibilités:
1)
pour un scc
prendre le premier noeud
trouver un cycle minimal avec ce noeud
fusionner ces noeuds en un big noeud.
mettre à jour les adjacences vers ce big noeud.

réitérer (cette fois le premier noeud est un big noeud)
lorsqu'on a le cycle minimal, il faut déterminer quels sont les noeuds du big noeud concernés.
subprocédure:
pour les deux noeuds liés au big noeud, trouver le plus court chemin vers l'autre noeud en passant par que des noeuds de big noeud

2)
triangulariser scc (ou les sommets sont des noeuds)
puis pour chaque triangle, calculer le rayon pour couvrir le triangle.
edit: avec Delaunay par exemple https://github.com/ironwallaby/delaunay

[rayane314]

Donc il faut d'abord trouver tous les scc puis creer un big noeuds pour lequel on trouve un cycle puis au boit de tout ça trianguler ?

Et sinon que dirait tu de faire une fonction récurente qui prends un graphe en argument
qui devompose le graphe en un minimum de sous graphe composés du plus grand cycle possible de celui ci et des ses chemins interieurs ,donc les plus grand possible mais au minimum deux sinon c'est inutile (si elle ne peut plus decomposer elle renvoie la distance minimale de son cycles sauf si c'est un triangle auquel cas elle teste s'il caque noeuds est a une distance de moins de deux rayons de chaque autre noeuds et la il n'ya pas besoin d'augmenter le rayon et on renvoie -1 dans ce cas)
Et pour chaque cycle(ou sous-graphe) elle s'appelle elle meme avec le cycle en argument
A ce moment elle renvoie la plus petite des distance renvoyes precedement
qui sera le nouveau rayon
Ou elle renvoie -1 si tous les appels ont renvoyes -1




Cette fonction va marcher parceque logiquement si tous les trous sont bouches les cycles sont tous des triqngesl



Avec quoi tu fais tes schémas ? J'aimerais te monter plus precisement


Ps: Ericovitchi: Non les points sont plaçables n'importe oú même si seulement en coordonnées entieres

[rayane314]

J'ai un début de code où il me reste plus qu'a implémenter la recherche de cycles et la vérification des triangles et la partie ou il faut sélectionner la plus petite distance d'un cycle mais ça je sais faire je le ferais plus tard.

Code: Tout sélectionner

#include
#include
#include
using namespace std;
double Cycle(vector >&,vector >&, double);

class coord {
public:
  int x;
  int y;
};

vector > > chercher_cycles(vector >&);

float dist(coord point1, coord point2)
{
    return sqrt((point1.x-point2.x)*(point1.x-point2.x)+(point1.y-point2.y)*(point1.y-point2.y));
}


int main()
{

    /**
    Entrées
    **/
    int n;
    std::cin >> n >> std::skipws;
    std::vector coords(n);
    for (int i = 0; i > coords[i].x >> std::skipws >> coords[i].y;
    }



    /**
    Tableu des distances de chaque points aux autres
    **/
    vector > distances(n,vector(n));
    float distance_mini = 1000000;
    for(int i(0); i > graphe(n,vector(n));
    double resultat = 0;
    while(resultat != -1)
    {
        /**
        Mise a jour du graphe d'intersections
        **/
        for(int i(0); i rayon*2)
                        distance_mini=distances[i][j];
                }
            }
            rayon = distance_mini/2;
        }
            //augmenter rayon de la plus courte distance restante
        else if(resultat>0)
            rayon += resultat;
    }
    //afficher arondi rayon
}
vector > > chercher_cycles(vector > &graphe,vector > &distances)
{
    vector > > cycles;
    return cycles;
}
double Cycle(vector > &graphe,vector > &distances, double rayon)
{
    /**
    Recherche de cycles
    **/
    vector > > cycles = chercher_cycles(graphe,distances);
    if(cycles.size()==0)//si aucun cycle
        return 0;
    if(cycles.size()==1)//si non décomposable:1 seul cycle minimal
    {
        if(cycles[0].size()==3)//test si triangle
        {
            //test si zone isolée
                //renvoie distance pour fermer
            //sinon
                //renvoie -1
        }
        else
        {
            //renvoie distance min
        }
    }
    //si on arrive jusque là: plusieurs cycles a décomposer
    double resultat = -1;
    for(size_t i(0); i<cycles.size(); i++)//décomposition
    {
        double tmp = 0;
        tmp=Cycle(cycles[i],distances,rayon);
        if(resultat == -1)
            resultat = tmp;
        else if(tmp<resultat && tmp!=-1)
            resultat = tmp;
    }
    return resultat;
}


[fatal_error]

Donc il faut d'abord trouver tous les scc puis creer un big noeuds pour lequel on trouve un cycle puis au boit de tout ça trianguler ?

non, soit tu fais l'un soit tu fais l'autre.
mais trianguler c'est quand même vachement plus simple parce que les algos sont déjà là..

Et sinon que dirait tu de faire une fonction récurente qui prends un graphe en argument

je sais pas j'ai du mal à imaginer que ca marche dans tous les cas, l'idée derrière c'est que tes cycles représentent des faces, mais je pense que dans certains cas tu vas avoir des faces qui s'overlappent (parce que tu ne gères pas les coordonnées de tes noeuds, mais seulement la relation entre eux)

Avec quoi tu fais tes schémas ? J'aimerais te monter plus precisement

jplote dans un canvas html des cercles un impr écran et après gimp :hum:, t'as plus vite fait d'utiliser inkscape ou autre chose je pense :we:

[rayane314]

Mais tu es sur que si je triangule comme ça va trouver quand un scc est couvert ?


L'idee c'est que comme c'est un graphe d'intersection des que noeuds sont proches ils se connectent donc deux faces ne peuvent pas s'overlapper parceque sinon ces deux faces se seront divisées en 4 faces et mon algorithme le trouvera.

C'est mal fait dans mon début d'algorithme mais si je vais prendre en compte des distances car je veux chercher le plus grand cycle (un genre d'enveloppe connexe mais en gardant ce qu'il y a a l'interieur) que je sépare en deux par un chemin intérieur, ceux qui me donnera deux sous graphes ou plus si il y'a d'autres parties complètement déconnectées
mais en gros c'est une sorte de dichotomie sur un graphe..
J'espère que c'est clair parce que je suis pas le meilleur niveau
explications..


Ok merci je vais tenter de faire des schémas pour te montrer le suivi de l'algorithme dès que j'ai accès a l'ordinateur
J'espère finir ça ce soir parce que je dois le rendre demain

[fatal_error]

ui, je suis parvenu à la même conclusion.

pour un scc, trouver le plus grand cycle élémentaire (pas de répétition de noeuds) pgce (par ex algo de johson)
puis si pgce est croisé (des arrêtes se coupent) le décroiser, (par ex avec un 2opt)
on obtient donc l'enveloppe convexe délimitant la zone à couvrir.
on triangule les noeuds de l'enveloppe (par ex: delaunay)
pour chaque triangle on calcule le centre circonscrit (voir wiki pour coordonnées)
si à l'intérieur du triangle, alors le radius est distance(centre, un des sommets du triangle) (on test l'intersection style ray tracing, voir wiki)
sinon on cherche le plus petit r tq pour le triangle ABC, AC étant le plus grand côté on ait
-A' le point de [AB] à distance r de A compris dans le disque de centre B et de rayon r
-C' le point de [AB] à distance r de C compris dans le disque de centre B et de rayon r
(ca semble velu mais en fait c'est deux inéquations du premier degré)
on récupère le plus grand radius, on update le graph (ca va pe créer de nouveaux trous) et on recommence tant que le radius augmente