Ich weiß, dass kd-Bäume traditionell zum Speichern von Punkten verwendet werden, aber ich möchte stattdessen Zeilen speichern. Wäre es am besten, die Linie an jeder Kreuzung mit der Aufspaltung des kd-Baums zu teilen? oder würden nur die Endpunkte in kd gespeichert werden, um den nächsten Nachbarn zu finden?
Der kd-Baum selbst ist für Punkt Objekte vorgesehen. Nicht einmal für Schachteln, Kugeln oder ähnliches. Ich glaube, dass Sie irgendwie einen 6d-Baum verwenden können, der minx, maxx, miny, maxy, minz, maxz speichert; aber ich bin mir nicht sicher, wie ich es richtig abfragen soll.
Der R * -Baum (Wikipedia) könnte hier eine bessere Wahl sein. Es ist wirklich für Objekte mit einer räumlichen Ausdehnung konzipiert. Wenn Sie die verwandten Publikationen nachschlagen, experimentierten sie sogar mit verschiedenen Approximationen komplexer Objekte; Zum Beispiel, ob es sich auszahlt, sie zu triangularisieren, eine Circumsphere, eine Bounding Box und interessanterweise IIRC zu verwenden, das 5-Eck-Polygon bot in einigen Fällen die beste Leistung.
Wie auch immer, die R * -Baumfamilie könnte eine interessante Wahl sein.
Nun, Sie müssen Linien an Kreuzungen teilen, sonst bekommen Sie Schwierigkeiten mit den Gewichten der Blätter des Baumes.
Wenn Sie andererseits SAH oder einen anderen Algorithmus zum Durchqueren des Baumes nicht verwenden, können Sie mit der ursprünglichen Idee des kd-Baums machen, was Sie wollen. Aber wenn Sie an einige traditionelle Algorithmen gebunden sind, können Sie Zeilen teilen. Sie müssen es tun, nur weil jedes Blatt des Baumes ein Gewicht hat (ich denke in Ihrem Fall hängt es von der Länge der Linien darin ab).
Und wenn Sie keine Linien teilen, bekommen Sie auch falsche Gewichte der Blätter. Nein, wenn Sie keine Zeilen teilen, sollten Sie sie in beide Blätter kopieren, zu denen die Zeile gehört.
Tags und Links data-structures kdtree raytracing ray