Ich habe einen Satz von 2d Punkten, die zufällig verteilt sind. Ich muss eine zeitintensive Operation an einer kleinen Teilmenge dieser Punkte ausführen, aber ich muss zuerst herausfinden, an welchen Punkten ich diese zeitintensive Operation ausführen muss. Um zu bestimmen, welche Punkte ich benötige, müssen sie eine Reihe von geometrischen Kriterien erfüllen.

Die grundlegendsten Kriterien sind, dass sie sich innerhalb eines bestimmten Abstands von einem bestimmten Punkt befinden. Das zweitwichtigste Kriterium ist, ob sie in einem Kreissektor (einem 2-D-Kegel) enthalten sind, der sich von diesem bestimmten Punkt aus erstreckt. (Bearbeiten: Diese Operation wird regelmäßig mit jeweils einem anderen bestimmten Punkt aufgerufen, jedoch mit demselben Satz von 2D-Punkten.)

Mein erster Gedanke war, ein Gitter zu erstellen, das die 2d-Punkte enthält, und dann entlang der Kegelrasterquadrate zu iterieren, die es schneidet. Abhängig von der Größe des Gitters würde die überwiegende Mehrheit der nicht benötigten 2D-Punkte herausgefiltert. Leider ist das eingebettete System, auf dem ich arbeite, stark speicherbeschränkt, so dass ein großes (nach unseren Maßstäben nicht jeder andere) 2D-Array zu speicherintensiv wäre.

Ich habe versucht, mithilfe von KD-Bäumen die Berechnung zu beschleunigen, aber ich konnte keinen Algorithmus finden, der Kreissektoren und KD-Bäume in Beziehung setzt.

Gibt es einen effizienten Algorithmus, um herauszufinden, welche 2D-Punkte in einem Kreissektor liegen?

Nur eine Anmerkung: Unser spezielles System ist sowohl in der Gleitkomma-Mathematik als auch in der Trigonometrie langsam, sodass eine Lösung, die weniger davon beinhaltet, überlegen ist und viel davon erfordert.