Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide Recherche
776 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  Créer une liste de ligne

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Créer une liste de ligne

n°1664122
casafa
Posté le 30-12-2007 à 18:00:27  profilanswer
 

Bonjour,
 
Voici mon problème très simplifié (tous les membres des classes en public, etc.) :
 

Code :
  1. class Point
  2. {
  3.    float X, Y, Z;
  4. };
  5. class Line
  6. {
  7.    Line(Point p1, Point p2)
  8.    {
  9.       this->p1 = p1;
  10.       this->p2 = p2;
  11.       nbLine = 1;
  12.    }
  13.    Point p1;
  14.    Point p2;
  15.    int nbLine;
  16. };
  17. std::list<Line> lines;


 
Dans un fichier, j'ai 10 000 segments de droite qui sont définit par 2 points.
J'aimerais charger ces 10 000 segments de droite en mémoire en évitant de chargé 2 fois un segment de droite identique. Si 2 segments de droite sont identique je voudrait juste incrémenter la variable "nbLine".
 
Voici la solution que j'ai :
void addLine(Line newLine) //on appel la méthode 10 000 fois pour les 10 000 segments
{
      1) On parcours toutes la std::list "lines" pour vérifier si newLine se trouve déjà dans la liste.
      2) Si elle s'y trouve déjà, on incrément la variable nbLine  de la ligne concerné
      3) Si elle ne s'y trouve pas : lines.push_back(newLigne);
}
 
Tous fonctionne bien à l'exception que le point "1" est très lent car il faut parcourir toutes la liste à chaque fois que l'on ajoute un nouvelle ligne.
 
Donc je pensait utiliser une std::map par exemple mais que mettre comme clef à la std::map ?
J'ai pensé transformer les 6 float des 2 points en string et les concaténer pour obtenir la clef. Le problème c'est qu'une ligne définit par le points :
1.0; 2.0; 3.0 et 4.0; 5.0; 6.0
et une ligne définit par les 2 points suivant serait considérer comme 2 ligne différentes (ce que je ne veux pas):
1.0; 2.0; 3.0 et 4.0; 5.000001; 6.0
 
Que faire ? Merci d'avance...

Message cité 1 fois
Message édité par casafa le 30-12-2007 à 18:02:04
mood
Publicité
Posté le 30-12-2007 à 18:00:27  profilanswer
 

n°1664136
Joel F
Real men use shared_ptr
Posté le 30-12-2007 à 18:38:36  profilanswer
 

bah strictement parlant, c'ets 2 lignes differentes.
Ensuite, j'utiliserais autre chose que ca pour stocker ton truc.  
 
Genre calculer la distance entre tes deux droites me parait pas mal pr regrouper les droites proches.


---------------
[NumScale] [ MKM | EBay ]
n°1664148
Master p
My new cock ring :D
Posté le 30-12-2007 à 19:25:17  profilanswer
 

casafa a écrit :

Donc je pensait utiliser une std::map par exemple mais que mettre comme clef à la std::map ?
...
et une ligne définit par les 2 points suivant serait considérer comme 2 ligne différentes (ce que je ne veux pas):
1.0; 2.0; 3.0 et 4.0; 5.000001; 6.0


Y a quelque chose qui t'empêche d'utiliser une Line comme clef de ta map?
Et par la même occasion, en insérant ta ligne dans le conteneur, tu peux très bien diminuer la précision pour obtenir le comportement que tu veux.


---------------
HAHAHA I M USING TEH INTERNET
n°1664152
casafa
Posté le 30-12-2007 à 19:41:28  profilanswer
 

Merci pour vos réponses...je me demande qu'est ce qui est le plus approprié pour mon problème : map ? set ?
-Le calcul de la distance est pas mal comme idée, je me demande bien pourquoi je n'y ait pas pensé plutôt
-Pour ce qui est de Line comme key, je voit pas comment ça pourrait fonctionner...que va comparer le std::map ?
 
J'ai fait ce code :

Code :
  1. struct comp
  2. {
  3.   bool operator()(const Line* line1, const Line* line2) const
  4.   {
  5.     float dist1 = line1->p1->distance(line2->p1);
  6.     float dist2 = line1->p2->distance(line2->p2);
  7.     if( (dist1 + dist2) < 0.002 )
  8.       return false;
  9.     else
  10.       return true;
  11.   }
  12. };
  13. int main()
  14. {
  15.   set<Line *, comp> test;
  16.   Line *line1 = new Line(new Point(1.0, 2.0, 4.0), new Point(4.0, 5.0, 6.0));
  17.   Line *line2 = new Line(new Point(1.0, 2.0001, 4.0), new Point(4.0, 5.0, 6.0));
  18.   Line *line3 = new Line(new Point(8.0, 9.0, 10.0), new Point(11.0, 12.0, 13.0));
  19.   test.insert(line1);
  20.   test.insert(line2);
  21.   test.insert(line3);
  22.   cout<<"Resultat : "<<test.size()<<endl;
  23.   return 0;
  24. }


Résultat : 2
 
J'ai donc ce que je voulait : line1 et line2 sont tellement proche qu'elle sont considéré comme 2 lignes identiques.
 
Il me reste un problème : comment incrémenter nbLine quand un insert à "échoué" ?


Message édité par casafa le 30-12-2007 à 19:42:03
n°1664153
Joel F
Real men use shared_ptr
Posté le 30-12-2007 à 19:45:49  profilanswer
 

la distance a testée c'ets plutot la racine carré de la somme des carrées des différences entre chaque coordonnées de ta ligne.


---------------
[NumScale] [ MKM | EBay ]
n°1664155
casafa
Posté le 30-12-2007 à 19:59:33  profilanswer
 

Oui c'est bien ce que fait ma méthode "distance" de la classe "Point"...
 
Edit :  
Donc dist1 représente la distance entre le point1 de la ligne 1 et le point 2 de la ligne 2
Idem pour dist2 avec les point2
 
C'est vrai que ma condition "if( (dist1 + dist2) < 0.002 )" est un peu bourrin, cette condition aurait été mieux :
if(dist1<0.001 && dist2<0.001)


Message édité par casafa le 30-12-2007 à 20:09:05
n°1664156
Joel F
Real men use shared_ptr
Posté le 30-12-2007 à 20:02:57  profilanswer
 

zut j'avais mal lu [:dawa] ok donc :D


---------------
[NumScale] [ MKM | EBay ]
n°1664177
bjone
Insert booze to continue
Posté le 30-12-2007 à 23:02:11  profilanswer
 

moi je ferais:
 
un map<Point, int> pour avoir des vertices unique, faire un weld (ou pas) au moment du chargement:
 
- lookup du point par le map avec un prédicat de comparaison custom
- si trouvé la ligne utilise le int associé, sinon le point est inseré avec un compteur de vertices incrémenté
- ajout d'une Line ressemblant juste alors a un pair<int,int> dans un vector, référençant les vertexs par leur indice
 
=> déroulement du map<Point,int> dans un vector<Point> pour les traitements suivants.  
 
tu te retouves avec:
- un vector<> de vertices uniques
- un vector<> de pair<int,int> pour les lignes
 
après tu peux encore pousser le schmilibilik plus loin en faisant un set<> de Line en en ayant ton Line.a < Line.b pour faciliter le lookup (et en linéarisant par la suite dans un vector<> une fois que la géométrie saine).
 
ce qui est bien mieux pour le traitement (tu peux créer les listes de dépendances par vertex) et le rendu (direct dans un Vertexbuffer / Indexbuffer)
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  Créer une liste de ligne

 

Sujets relatifs
[Resolu] Transformation d'un fichier en liste doublement chainéeComment on fait pour créer une miniature affichée dans l'explorateur?
[c#] Liste des connexions réseauXMLHttpRequest qui marche en local, mais pas en ligne...
créer des formulaires sur ACCESSListe déroulante
Création d'un système de pétition en ligneboutique en ligne
[resolu][PHP/JS] Afficher div via selection dans une liste/radiofonction saisie ligne sans limite
Plus de sujets relatifs à : Créer une liste de ligne



Copyright © 1997-2014 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC