Bipartite Grafik für inkrementelle Konvexe Hülle erstellen

Question

Ich versuche, einige Klassen zu erstellen, um eine 3D Konvexe Hülle einer Wolke von Punkten in O (N * logN) zu erstellen.

Ich habe bereits das naive Problem gelöst, das eine Komplexität von O (N²) hat, wobei N die Anzahl der Punkte ist. Es funktioniert so:

Ich habe eine Std :: Liste der Punkte. Diese Punkte entsprechen einer Klasse, die ich erstellt habe. Ich randomize die Liste und extrahiere nacheinander alle Punkte aus der Liste. Für jeden Punkt überprüfe ich, welche Facetten von diesem Punkt aus sichtbar sind. Also, die Komplexität ist zu hoch, weil Facetten O (N) sind (mehr als 6 * N)

Dann mache ich einige Operationen, um sichtbare Facetten zu löschen, Horizont zu finden und den Punkt mit Horizont zu verbinden. Informationen über diese Operation helfen nicht, mein Problem zu lösen.

Was ich brauche, ist ein Beispiel für die Erstellung und Behandlung eines zweiteiligen Graphen, die schnell hinzufügen und Knoten entfernen wird.

Ich habe versucht, meine eigenen Klassen zu erstellen, aber ich scheiterte, weil mein Diagramm zu langsam war. Aber vor einigen Tagen fand ich, dass die Boost-Bibliothek die Lösung hat: this.

Aber ich bin mit dem Erstellen meiner einfachen Grafik mit all diesen Optionen fest, ich verstehe nicht, wie man es erstellt. Ich habe so viele Male diese Dokumentation lesen ...

Nun, die Frage ist: wie kann ich einen zweiteiligen Graphen mit boost bauen?

es muss sein:

• bidirektional;
• bipartite: eine Art von Knoten wird Pointd der andere Typ wird Dcel :: Face sein;
• Die Punktknoten müssen alle Facetten verknüpfen, die der Punkt sehen kann;
• Die Dcel :: Face-Methode muss alle Punkte verknüpfen, die sie sehen können.
• schnell entfernen und hinzufügen Operationen.

Ich interessiere mich nicht für Speicherverbrauch. Ich brauche es nur, um schnell zu sein.

Dies ist meine erste Frage, also weiß ich nicht, ob es klar ist oder nicht. Wenn jemand so freundlich sein wird, mir ein Beispiel zu geben, wie ich ein Diagramm mit diesen Eigenschaften, die ich Ihnen gegeben habe, erstellen kann, wird es großartig. Wenn Sie einen anderen Weg kennen, um es leicht zu erstellen, wird es auch gut sein.

Answer 1

Wenn Sie bidirektional sagen, nehme ich an, Sie meinen ungerichtet.Wenn es heißt, wollen Sie Ihr Diagramm gerichtet werden, sondern den Zugang zu haben, in und außerhalb Kanten einer Ecke, dann ersetzen Sie einfach boost::undirectedS mit boost::bidirectionalS In Bezug auf seine Schöpfung, hier ist das, was Sie tun können:

#include <cstdint> 
#include <boost/graph/adjacency_list.hpp> 

enum class vertex_kind : std::uint8_t { 
    POINTD, 
    DCEL_FACE, 
    UNKNOWN 
}; 

struct pointd_property { /* Whatever is needed */ }; 
struct dcel_face_property { /* Whatever is needed */}; 

struct vertex_property { 
    vertex_kind kind; 
    union { 
     pointd_property pointd; 
     dcel_face_property dcel_face; 
    }; 
    vertex_property() : kind(vertex_kind::UNKNOWN) {} 
    vertex_property(pointd_property const& pprop) : kind(vertex_kind::POINTD) { new (&pointd) pointd_property(pprop); } 
    vertex_property(dcel_face_property const& fprop) : kind(vertex_kind::DCEL_FACE) { new (&dcel_face) dcel_face_property(fprop); } 
}; 

typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, vertex_property> graph_type; 

Jetzt die Grafik bevölkern ist ganz einfach:

auto graph = []() { 
    graph_type g; 
    auto a = boost::add_vertex({pointd_property()}, g); 
    auto b = boost::add_vertex({dcel_face_property()}, g); 
    boost::add_edge(a, b, g); 
    return g; 
}(); 
// Do whatever you please with g. 

natürlich ist der Inhalt des Scheitels Eigenschaft in Zeile aus dem BGL Sie beabsichtigen, zu verwenden, um mit der Anforderung des Algorithmus sein sollte. Wenn es irgendwelche Anforderungen gibt, lass es mich wissen, damit ich meine Antwort bearbeiten kann.