View
107
Download
1
Category
Preview:
Citation preview
Konkrete Beispiele
Bernhard Kornberger
Überblick
Installation Tipps zu Installation und Inbetriebnahme
Konkrete Beispiele Konvexe Hülle berechnen
Verschiedene Algorithmen
Fehler in der numerischen Genauigkeit Beispielprogramm Ursachen und Lösungen
Installation und Inbetriebnahme
Download http://www.cgal.org/cgi-bin/cgal_download.pl
Entpacken nach /opt/ tar fxvz CGAL-3.0.1.tar.gz
Installations-Doku installation.pdf (27seitig)
Starten der Installation ./install_cgal –i
Installation und Inbetriebnahme
Beispielprogramme sind vorhanden in /opt/CGAL/examples ...Beispiele ohne qt /opt/CGAL/demo ...Beispiele mit qt
Compilieren mit: cd /opt/CGAL/examples/einBeispiel/ Variable CGAL_MAKEFILE setzen (WICHTIG) make
Algorithmen zur Berechnung konvexer Hüllen im 2D
Programm zur Berechnung der konvexen Hülle einer Punktemenge (verkürzte Version)
typedef CGAL::Point_2<CGAL::Cartesian<double>> Point;int main(){ std::vector<Point> out, randomPoints;
// Vektor mit zufälligen 2D Punkten im Einheitskreis CGAL::Random_points_in_disc_2<Point> g(1); for(int count=0; count<300000; count++) randomPoints.push_back(*g++);
// Punkte der konvexen Hülle berechnen und im Vektor ‚out‘ speichern CGAL::ch_jarvis( randomPoints.begin(), (randomPoints.end()),
std::back_inserter(out) );
// Ausgabe std::vector<Point>::const_iterator it=out.begin(); for(;it!=out.end();++it) cout << it<<endl; return 0;}
...und das soll jetzt compiliert werden
1. /opt/CGAL-3.0.1/scripts/create_makefile...dieses Skript baut für alle *.c und *.cpp-Files im Directory ein Makefile
2. Variable CGAL_MAKEFILE setzen oder direkt ins Makefile eintragen:export CGAL_MAKEFILE=/opt/CGAL-3.0.1/make/makefile_i686_Linux-2.6.3-4mdk_g++-3.3.2
3. „make“ aufrufen, fertig.
Verschiedene Algorithmen zur Berechnung konvexer Hüllen im 2D Die Algorithmen weisen unterschiedliche
Laufzeiten für n Punkte mit h Extrempunkten auf: ch_akl_toussaint: O(n log n) ch_graham_andrew: O(n log n) ch_bykat: O(n h) ch_jarvis: O(n h) ch_eddy: O(n h)
Algorithmus: ch_eddy
Algorithmus: ch_akl_toussaint
Algorithmus: ch_bykat
Algorithmus: ch_graham_andrew
Algorithmus: ch_jarvis
Laufzeitvergleich (CPU: XP1700)
ch_jarvis O(n h)
ch_eddy O(n h)
ch_graham_andrew O(n log n)
Laufzeitvergleich (CPU: XP1700)
Robustheit und Rechengenauigkeit
Robustheit und Rechengenauigkeit
Die Typen int, float und double von C++ können ihre mathematischen Gegenstücke nur grob annähern Integer können überlaufen floats und double‘s produzieren
Rundungsfehler Gerade Algorithmen für Geometrie können
sehr empfindlich auf solche Fehler reagieren, wie das folgende Beispiel zeigt...
Programmbeispiel zur begrenzten Rechengenauigkeitint main(){std::vector<Point> convHullOut;std::vector<Point> inputPoints;
// Zwei Segmente, die sich ueberschneidenSegment seg1( Point(0,0), Point(900,1000));Segment seg2( Point(0,1000), Point(1000,0));
// Endpunkte des ersten Segments -> VektorinputPoints.push_back(Point(0,0));inputPoints.push_back(Point(900,1000));
// Den Schnittpunkt in den Vektor speichernCGAL::Object result =
CGAL::intersection( seg1,seg2 );Point pt;if (CGAL::assign( pt, result ) )
inputPoints.push_back(pt);
// Errechnen der konvexen Huelle
CGAL::ch_eddy( inputPoints.begin(), (inputPoints.end()), std::back_inserter(convHullOut) );
// Ausgabe der konvexen Huelle
std::cout << "Die Punkte der konvexen Huelle lauten:\n";
for(;it!=convHullOut.end();++it)
std::cout <<*it<<endl;
return 0;
}
Programmbeispiel zur begrenzten Rechengenauigkeit
Ursachen und Lösungen
Im vorigen Programmbeispiel wurde typedef CGAL::Point_2<CGAL::Cartesian<double>>
Point; verwendet. Die Rechengenauigkeit von ‚double‘ hat nicht ausgereicht.
LEDA – exakte DatentypenIntegers of Arbitrary Length Integers beliebiger Länge „integer“
Führen immer zu exakten Ergebnissen Kein Overflow/Underflow Verwendung wie und mit den eingebauten
Typen Vordefinierte arithmetische Operationen wie
Quadratwurzel, GCD, etc.
Aber 30-100 mal langsamer als ‚double‘
LEDA – exakte DatentypenRational Numbers Rationale Zahlen „rational“
Führen immer zu exakten Ergebnissen Implementiert als Quotient zweier Integer
beliebiger Länge und mit deren Eigenschaften Kann wie ‚double‘ gemeinsam mit den
eingebauten Datentypen verwendet werden.
Aber 30-100 mal langsamer als ‚double‘
LEDA – exakte DatentypenTyp „Rational“ - Beispiel#include <LEDA/rational.h> #include <LEDA/integer.h> using namespace leda; int main() {
integer denominator=1; int i; for (i=1;i<=40;i++) {denominator*=i;} // Nenner = (40!)
rational r(1000,denominator); // Rationale Zahl r=( 1000 / (40!) )cout << "r=" << r << endl;
// Einige Operationen mit r:r.normalize(); cout << "After r.normalize(): r=" << r << endl; r.invert(); cout << "\nAfter r.invert(): r=" << r << endl; cout << "\nsqr(r)=" << sqr(r) << endl; cout << "\nceil(r)=" << ceil(r) << endl; return 0;
}
LEDA – exakte DatentypenReal Numbers Algebraic Real Numbers „real“
Führen zu exakten Ergebnissen Können wie und gemeinsam mit ‚doubles‘ verwendet
werden Arithmetische Operationen wie die k-te Wurzel sind
vordefiniert Nachteile:
Speicherbedarf steigt linear mit der Größe der Berechnung – alle Operationen werden gespeichert.
10-80 mal langsamer als ‚double‘ Empfohlen für Berechnungen der k-ten Wurzel, sonst
besser Big Floatingpoint Numbers
LEDA – Typ mit Rundung Big Floatingpoint Numbers Big Floatingpoint Numbers „bigfloat“
Im Gegensatz zu den vorigen Typen ist „bigfloat“ ein Datentyp mit Rundung und führt nicht zu mathematisch exakten Ergebnissen
Aber im Gegensatz zu „double“ kann „bigfloat“ mit beliebiger Genauigkeit arbeiten.
Nachteile von „bigfloat“ 60-200 mal langsamer als double, abhängig
vom Rundungstyp Kompliziert in der Anwendung
LEDA - Weitere Typen
Floating Point Filter Schnell (nur noch 4 mal langsamer als double) Berechnet Fehlergrenzen und wenn das Resultat nicht
eindeutig ist, kann man immer noch den langsameren exakten Typ verwenden.
Intervall Arithmetik Vektoren und Matrizen
...aber diese Typen werden nicht direkt von CGAL unterstützt, das ist daher Stoff des LEDA-Vortrages.
Recommended