Ajouter le lien inverse dans le graphe de conflits

[lemairecarl]

En ce moment, on peut savoir quels points sont en conflit avec une face. Il faut aussi pouvoir savoir quels faces sont en conflits avec un point!

[lemairecarl]

@atompacman La meilleure solution aurait été le bimap (map qui fonctionne dans les deux sens) mais ça prendrait boost. La seule vraie solution que je vois à date serait:

map<FacetNode*, list<PointNode*>> FacetToPoints;
map<PointNode*, list<FacetNode*>> PointToFacets;

As-tu une meilleure idée?

[atompacman]

Je n'ai pas encore de problème avec

std::list<sptr<FacetNode>>* m_Conflicts;

donc pour l'instant je n'y porte pas beaucoup d'attention

[lemairecarl]

Ok, je viens de réaliser que c'est un tableau primitif (car il y a `*ˋ). Donc, on peut trouver les faces en conflit avec un point.

Peux-tu m'expliquer comment faire le chemin inverse, soit trouver les points en conflit avec une face?

[atompacman]

Je crois qu'on a jamais besoin de savoir out of nowhere quels sont les points en conflits avec une face. On connait les faces qu'on veut interroger en utilisant la relation point->facetnode et avec les facetnode on sait quels sont les points en conflits avec elles.

[lemairecarl]

Aux étapes 13 et 16 de l'algo, on a besoin de la liste de points en conflit avec une certaine face.

De plus, quand on retire une face, elle a encore des références à plusieurs endroits dans m_Conflicts. (elle pouvait être en conflit avec plusieurs points.) Il faut enlever la face en question de chaque liste qui la contenait. Si on a le lien face->point, on obtient les points instantanément à modifier instantanément, sans avoir à boucler sur tous les points et regarder s'il sont en conflit avec la face.

[lemairecarl]

Voici ce que je propose:

struct PointNode
{
    uint m_Point;
    list<sptr<FacetNode>> m_Conflicts;
};

struct FacetNode
{
    sptr<Facet> m_Facet;
    list<sptr<PointNode>> m_Conflicts;
};

struct ConflictGraph
{
    map<uint, sptr<PointNode>> m_PointNodes; // Pas une liste car il peut y avoir des trous
    map<sptr<Facet>, sptr<FacetNode>> m_FacetNodes;
};

Avec ça, à l'étape 13, on trouve f' (un sptr<Facet>) avec le DCEL, donc sans avoir son FacetNode. Le membre m_FacetNodes permet de trouver le FacetNode à partir du sptr<Facet>, et ainsi d'avoir la liste de points en conflit.

[atompacman]

Je dis qu'on pourrait remplacer les deux map par des beaux gros tableaux sales car ben... des int comme clé messemble que c'est un overhead et les Facet on des ID aussi donc l'efficacité serait au rendez-vous.

[lemairecarl]

Ok, j'ai pas de problème à utiliser des ID. Mais il va falloir trouver une façon élégante d'avoir des trous dans les tableaux, car aux lignes 19 et 20 de l'algo on supprime des noeuds du graphe...

[atompacman]

Je sais pas si juste le fais de remplacer la valeur par un null ça va automatiquement supprimer les nodes car les shared_pointer se rendent compte qu'ils n'ont plus de références...

[lemairecarl]

Ah! J'avoue! Vu que c'est un pointeur on peut mettre null. Parfait alors. On aurait donc quelque chose dans le genre:

struct PointNode
{
    uint m_Point;
    list<sptr<FacetNode>> m_Conflicts;
};

struct FacetNode
{
    sptr<Facet> m_Facet;
    list<sptr<PointNode>> m_Conflicts;
};

struct ConflictGraph
{
    sptr<FacetNode> m_FacetNodes[NUM_FACES];
    sptr<PointNode> m_PointNodes[NUM_PTS];
};

EDIT: Et la classe Facet va contenir un champ ID pour aller chercher le FacetNode correspondant.

[atompacman]

sptr<FacetNode> m_FacetNodes[NUM_FACES]

N'oublions pas que le nombre de faces est variable !

[lemairecarl]

Ouais! Donc ça pourrait être: vector<sptr<FacetNode>> m_FacetNodes.

Notes:

• Quand une Facet est éliminée, la case correspondant à son ID dans le vecteur est laissée à NULL.
• Quand une Facet est créée, on lui donne un nouveau ID unique, égal à la taille actuelle du vecteur m_FacetNodes

On se croirait en BD

[lemairecarl]

Good job