Thread-sichere Triangulationsbibliothek

Question

Ich schreibe eine C++ Software, die schnelle Minkowski-Summenberechnungen benötigt. Eine Implementierung basierend auf Doppel genügt.

I ausgewertet einige geometrische Bibliotheken wie

• CGAL
• LEDA
• boost::geometry (nicht die Minkowski-Summe Umsetzung, aber es gibt eine tutorial zu erklären, wie es zu implementieren)

aber ich endete mit einer anderen Third-Party-Bibliothek, die sehr schnell im Vergleich zu der vorherigen ist s und die FIST Bibliothek für Triangulation verwendet.

Mein Code funktioniert mehr oder weniger in der folgenden Art und Weise:

• ich meine Polygone lesen
• ich die Minkowski berechnen fasst ich
• Für n-mal brauchen
  • ich entscheiden, welche Polygone Verwenden Sie in der folgenden Berechnung
  • Ich mache einige Sachen auf der Grundlage der Minkowski Summen
  • Ich gebe ein val ue das Ergebnis
• ich mit dem besten Wert als das Endergebnis das Ergebnis nehmen

Da die Berechnungen innerhalb der Schleife von rund unabhängig bin abzurunden, parallelisiert ich die Schleife und alles hat gut funktioniert.

Dann habe ich beschlossen, die Minkowski Summenberechnung in jeder parallelen Runde zu bewegen:

meine Polygone

• Ich las
• Für number_of_threads (= n) mal
  • I, die Polygone zu verwenden, in der sich entscheiden folgende Berechnung
  • ich berechnen die Minkowski fasst ich in dieser Runde müssen
  • ich einige Sachen auf dem Minkowski Sie basiert fasst
  • Ich gebe einen Wert auf das Ergebnis

• ich mit dem besten Wert als das Endergebnis das Ergebnis nehmen

  aber die Drittanbieter-Bibliothek arbeitete nicht mehr.

ich number_of_threads - 1 Fehlermeldungen sagen

Assertionsfehler.

Die Dateien mit den Assertionsfehler Wechsel von Lauf verursacht zu laufen und von Faden einzufädeln, aber sie alle sind c-Dateien gleichen Namen wie die FIST-Header mit (während ich den Quellcode der Dritt Bibliothek , Ich habe nur eine .lib und die Header der FIST-Bibliothek)

Wie bereits erwähnt, habe ich versucht, alle Minkowski-Summen außerhalb des parallelisierten Codes zu berechnen und die Ergebnisse darin zu verwenden. Das war in Ordnung. Ich bin mir also fast sicher, dass die Probleme von FIST kommen.

Ich habe zwei Fragen:

• Wissen Sie, ob die FIST Bibliothek Thread-sicher ist?

• Falls nicht, können Sie mir bitte eine thread-sichere (C- oder besser C++ -) Triangulationsbibliothek vorschlagen, um FIST zu ersetzen (möglicherweise mit vergleichbaren Leistungen)?

edit:

Eigentlich weiß ich nicht, wenn „thread-safe“ ist genau das, was ich will: Ich brauche nur eine tringulation Bibliothek in der Lage viele unabhängige Triangulation zur gleichen Zeit berechnen .

Ich denke, dass, wenn die Bibliothek hatte keine globalen Variablen und wenn es eine Klasse ohne static Variablen hat

class triangulation 
{ 
    // no static variables 

    void execute_triangulation(); 
} 

es könnte genug sein. So könnte ich verschiedene Instanzen dieser Klasse verwenden und parallel ihre Methode ausführen.

Answer 1

Sie können wahrscheinlich die 2D triangulation package of CGAL verwenden, um FIST zu ersetzen, und verwenden Sie es dann als die Eingabe dieser Fremdanbieterbibliothek, die Minskowski-Summen ausführt. Die CGAL-Triangulationen sind sehr schnell und zuverlässig. Sie können Polygone und komplexe Formen mit der eingeschränkten Delaunay-Triangulation triangulieren.

Übrigens, welche Minkowsky-Bibliothek verwenden Sie?

Answer 2

Es hängt sehr stark ab, was Sie damit meinen:

Da mein Code parallelizable ist eingeführt ich

Multithreading

Sie benötigen, um genauer zu sein, Hilfe zu erhalten. Was bedeutet es "Sie haben Multithreading eingeführt"? Zum Beispiel haben keine der Bibliotheken, die Sie erwähnen, eine parallele Berechnung von Minkowski-Summen (oder irgendetwas anderes) eingebaut - Sie müssen sie selbst parallelisieren. In Bezug auf Minkowski-Summen ist es möglich, einen Map-Reducce-Ansatz zu verwenden: Teilen Sie den Eingabedatensatz in kleinere Teile, berechnen Sie die Minkowski-Summe für jeden parallel (Karte) und vereinigen Sie die Zwischenergebnisse so, wie sie eingehen unabhängige Arbeiter (reduzieren). Die Anforderungen hierfür sind eine grundlegende Thread-Sicherheitsgarantie (die Ihnen beispielsweise CGAL bietet) mit Nur-Lese-Zugriff auf die Parameter der Berechnung.

Answer 3

Eine mögliche und sofort testbare Lösung besteht darin, einen Mutex um den Code zu platzieren, der die Minkowski-Berechnungen aufruft.Wenn das interessant klingt und Sie nicht wissen, wie es gemacht wird, fügen Sie einen Kommentar hinzu, der die Plattform beschreibt, die Sie verwenden, und ich, oder jemand anderes, wird erklären, wie es geht.

Zumindest wird Ihnen das zeigen, ob Sie das Problem richtig erkannt haben. Wenn die Berechnungen einen kleinen Teil Ihrer Gesamtbandbreite ausmachen, dann könnte es sich als gute Lösung herausstellen - ansonsten nur ein Schritt auf der Straße.