Ich arbeite an meiner gEDA-Gabel und möchte die bestehenden einfachen loswerden Fliese-basiertes System 1 zugunsten eines realen räumlichen Index 2 .
Ein Algorithmus, der Punkte effizient findet, ist nicht genug: Ich muss Objekte mit einem Umfang ungleich null finden. Denke in Bezug auf Objekte mit umlaufenden Rechtecken, die ziemlich genau die Detailtiefe erfassen, die ich im Index benötige. Bei einem Suchrechteck muss ich effizient alle Objekte finden können, deren Begrenzungsrechtecke innerhalb des Suchrechtecks liegen oder sich überschneiden.
Der Index kann nicht schreibgeschützt sein: gschem ist ein Schaltplan-Capture-Programm, und der Sinn des Ganzen liegt darin, Dinge im Schaltplan zu bewegen. Also werden sich die Dinge ändern. Während ich es mir leisten kann, die Einblendung etwas teurer zu machen als das Suchen, kann es auch nicht viel teurer sein, und das Löschen muss auch möglich und ziemlich billig sein. Aber die wichtigste Voraussetzung ist das asymptotische Verhalten: Suchen sollte O (log n) sein, wenn es nicht O (1) sein kann. Die Insertion / Deletion sollte vorzugsweise O (log n) sein, aber O (n) wäre in Ordnung. Ich will definitiv nichts & gt; O (n) (pro Aktion; offensichtlich wird O (n log n) für eine Operation mit allen Objekten erwartet).
Was sind meine Möglichkeiten? Ich bin nicht klug genug, die verschiedenen Optionen auszuwerten. Idealerweise würde es eine C-Bibliothek geben, die all die cleveren Sachen für mich erledigen würde, aber ich werde mechanisch einen Algorithmus implementieren, den ich vielleicht nicht vollständig verstehe, wenn ich muss. gEDA verwendet übrigens glib, wenn das hilft, eine Empfehlung zu geben.
Fußnoten:
1 Standard gEDA unterteilt ein schematisches Diagramm in eine feste Anzahl (derzeit 100) von "Kacheln", die dazu dienen, die Suche nach Objekten in einem Begrenzungsrechteck zu beschleunigen. Dies ist offensichtlich gut genug, um die meisten Schaltpläne schnell genug zu durchsuchen, aber die Art und Weise, wie es gemacht wird, verursacht andere Probleme: Viel zu viele Funktionen erfordern einen Zeiger auf ein de-facto globales Objekt. Die Geometrie der Kacheln ist ebenfalls festgelegt: Es wäre möglich, dieses Kachel-System ganz einfach durch Schwenken (und möglicherweise Zoomen) auf einen Bereich zu bezwingen, der nur von einer Kachel abgedeckt wird.
2 Eine legitime Antwort wäre, Elemente des Tiling-Systems beizubehalten, aber seine Schwächen zu beheben: es zu lehren, den gesamten Raum zu überspannen und sich bei Bedarf zu unterteilen. Aber ich möchte, dass andere ihre zwei Cent addieren, bevor ich autokratisch beschließe, dass dies der beste Weg ist.
Eine schöne Datenstruktur für eine Mischung von Punkten und Linien wäre ein R-Baum oder eine seiner Ableitungen (z. B. R * -Tree oder ein Hilbert R-Tree). Angesichts der Tatsache, dass dieser Index dynamisch und serialisierbar sein soll, wäre die Verwendung von SQLite R * -Tree-Modul ein vernünftiger Ansatz.
Wenn Sie C ++ tolerieren können, hat libspatialindex eine ausgereifte und flexible R-Tree-Implementierung, die dynamische Einfügungen / Löschungen und Serialisierung unterstützt.
Ihre Anforderungen ähneln denen, die in Kollisionserkennungsalgorithmen für Spiele- und Physiksimulationen verwendet werden. Es gibt mehrere Open-Source-C ++ - Bibliotheken, die dies in 2-D (Box2D) oder 3-D (Kugelphysik) . Obwohl Ihre Frage für C ist, können Sie ihre Dokumentation und Implementierungen nützlich finden.
Normalerweise wird dies in eine zwei Phasen aufgeteilt:
Physik-Engines verwenden ebenfalls räumliche Kohärenz, um die verglichenen Objektpaare weiter zu reduzieren, aber diese Optimierung wird Ihrer Anwendung wahrscheinlich nicht helfen.
Die Breitphase wird normalerweise mit einem O (N log N) -Algorithmus wie Sweep and Prune implementiert. Sie können dies möglicherweise beschleunigen, indem Sie es in Verbindung mit dem aktuellen Kachel-Ansatz verwenden ( eines von Nvidias GPUGems ) beschreibt diesen hybriden Ansatz). Die enge Phase ist ziemlich kostspielig für jedes Paar und kann für Ihre Bedürfnisse übertrieben sein. Der GJK-Algorithmus wird jedoch häufig für konvexe Objekte in diesem Schritt verwendet Für speziellere Fälle gibt es schnellere Algorithmen (zB: Box / Circle und Box / Sphere Kollisionen).
Das hört sich nach einer Anwendung an, die für einen Quadtree gut geeignet ist (vorausgesetzt, Sie interessieren sich nur für 2D.) Der quadtree ist hierarchisch (gut für die Suche) und es ist räumliche Auflösung ist dynamisch (ermöglicht höhere Auflösung in Bereichen, die es brauchen).
Ich habe immer meine eigenen Quadtrees gerollt, aber hier ist eine Bibliothek, die vernünftig erscheint: Ссылка
Es ist leicht zu machen. Es ist schwer, schnell zu machen. Klingt wie ein Problem, an dem ich gearbeitet habe, wo es eine riesige Liste von Min-, Max-Werten gab und einen Wert gab, den es zurückgeben musste, wie viele Min-, Max-Paare diesen Wert überlappten. Sie haben es nur in zwei Dimensionen. Du machst es also mit zwei Bäumen für jede Richtung. Machen Sie dann eine Kreuzung auf den Ergebnissen. Das ist wirklich schnell.
%Vor%Die Extents-Testdatei hatte 1,5 MB:
%Vor%Die Zahlen-Datei war wie folgt:
%Vor%Selbst beim Lesen der zwei Dateien von der Festplatte, waren die Extents 1,5 MB groß und die Nummern waren 780 KB und die wirklich große Anzahl von Werten und Suchvorgängen, dies läuft in einem Bruchteil einer Sekunde ab. Wenn es im Speicher wäre, würde es blitzschnell werden.