Erzeugen von Dreiecken aus einer zufälligen Menge von Punkten

Question

Ich habe zufällig einige Punkte auf einem JavaScript-Canvas generiert Ich habe mich gefragt, was die effizienteste Methode wäre, Dreiecke zu zeichnen, die die Punkte in einer einheitlichen Art und Weise verbinden. Das Ziel besteht darin, dass die Dreiecke die gesamte Leinwand ausfüllen, ohne sich zu überlappen.

---

Für eine visuelle Darstellung, hier ist ein Bild der Punkte, die ich zufällig über eine Leinwand generiert habe. Wie Sie sehen können, muss ich möglicherweise die Art ändern, in der ich die Punkte zufällig auf die Leinwand lege.

Und so möchte ich die Dreiecke zeichnen.

Answer 1

Dank & @GabeRogan für den Hinweis mich in die richtige Richtung @Phorgz. Delaunay Triangulation war definitiv der Weg zu gehen und es endete sehr schnell, auch wenn die Leinwand als Animation aktualisiert wurde.

Ich habe am Ende mit dem npm-Paket faster-delaunay, die den Divide and Conquer-Algorithmus verwendet, um die zufällig erzeugten Punkte zu triangulieren. Hier

ist ein Ergebnis dessen, was ich auf der Leinwand gezogen haben, die Updates wie die Punkte um die Ebene bewegen: