Polygon triangulieren: C++ Sourcecode gesucht



  • Hallo,

    ich habe eine Menge an (äußeren) Punkten eines Objekts, die ich in OpenGL gerne als gefüllte Fläche darstellen würde. Alle Punkte liegen auf einer Ebene (2D). Suchen brachte zu Tage, dass ich diese Punktemenge bzw. das Polygon triangulieren muss um dann mit GL_POLYGONS zu arbeiten.

    Frage: Hat jemand einen Link zu C++-Quellcode? Im Idealfall werfe ich einen std::vector<Point2D> (o.ä.) in eine Klasse/Funktion und erhalte dann die entsprechenden Dreiecke als Ergebnis.

    Mit google finde ich nur Beschreibungen, Applets usw. aber nichts fertiges. Ich möchte das auch gar nicht selber implementieren... Danke euch 🙂



  • Die Beschreibung "äussere" Punkte irritiert mich.
    Meinst du dass dein Polygon immer konvex ist, oder meinst du nur dass die Punkte halt nicht "im" Polygon liegen (d.h. das Polygon kann auch konkav sein)?



  • Unglücklich von mir beschrieben. Ich habe eine Punktemenge, wobei ich die konvexe Hülle mittels Graham Scan berechne ("äußere Punkte"). Habe eben noch herausgefunden, dass das Füllen dieser Hülle mit OpenGL möglich sein soll, da konvex.

    Aus Interesse möchte ich aber weiterhin nach einer schlanken Bibliothek zum triangulieren fragen



  • Wenn es um ein konvexes Polygon geht, kannst du es einfach als Triangle Fan rendern... 😉



  • for(size_t i=2u;i<Aussenpunkte.size();i++)
     Triangles.push_back(Triangle(Aussenpunkte[0],Aussenpunkte[i-1],Aussenpunkte[i]);
    

    Ich hoffe, dass meine Bibliothek schlank genug für dich ist.



  • Ich bin damals auf poly2tri gestoßen (funktioniert auch mit Löcher):
    http://sites-final.uclouvain.be/mema/Poly2Tri/



  • im konvexen Fall ist das einfach - wurde bereits oben erklärt.
    Nur minimal schwieriger ist ein einfaches Polynom zu triangulieren: siehe z.B. Two-Ears Theorem. Sofern man eine Bibliothek für die Lineare Algebra (zB Eigen) verwendet ist das auch in wenigen Zeilen runterprogrammiert.


Log in to reply