Punkt-in-Delaunay-Test von der unverhüllten Punktwolke

Question

Wäre es möglich, bei einem beliebigen Punkt P und der Annahme, dass ich in der Nähe (nicht vermaschte) nach Entfernung sortierte Punkte suchen kann, die drei nahegelegenen Punkte, die das Delaunay-Dreieck bilden welches enthält P? Wenn das so ist, wie?

Answer 1

Ich nehme an, Sie sind in 2D ohne kollineare Punkte. Was ich vorschlage funktioniert auch in 3D. Erstellen Sie einen Kd-Baum, der alle Punkte enthält. Dann suche nach den 2 nächsten Nachbarn von P. Konstruiere den Umkreis.

Betrachten Sie das Zentrum dieses Kreises und suchen Sie danach den nächsten Nachbarn. Wenn der erste Punkt, den Sie finden (ignorieren Sie die Dreieckspunkte), weiter als der Kreisradius ist, dann haben Sie Ihr Dreieck. Andernfalls wird die Eigenschaft des leeren Kreises verletzt und in diesem Fall wissen Sie, dass der Punkt außerhalb des Dreiecks liegt. Sie können jetzt zwei Dreiecke definieren und überprüfen, dass die Eigenschaft des leeren Kreises wie zuvor verifiziert ist (aber wenn Sie einen Punkt im Kreis finden, müssen Sie überprüfen, ob der Punkt innerhalb des Dreiecks liegt). Dann ist es wie eine Delaunay-Triangulation mit allen vier Punkten und allen anderen Punkten innerhalb eines Umkreises.

Für die Implementierung können Sie CGAL zum Beispiel verwendet werden, die Orthogonal_incremental_nearest_neighbor, die has_on_bounded_side Funktion aus der Triangle_2 Klasse und die circumcenter Funktion bereitstellt.

Sie können auch direkt die Delaunay_triangulation_2 Klasse verwenden, die mit den drei ersten Punkten initialisiert wurde, und inkrementelle Punkte einfügen, die die Eigenschaft des leeren Kreises der dreieckigen Flächen ungültig machen.