如何將點變成三角形？

Question

我試圖以編程方式使三角形的圖像都粘在一起。我認爲我會解決這個問題的方式是隨機選擇一些點數，然後「連接」它們來製作三角形。問題是我無法想出連接它們的好方法。

我要做的一件事是選擇一個隨機點開始（點1），然後找到最近的點（點2），然後「連接」它們。然後，通過選擇距離點1和點2的組合距離最小的那個，我會找到最近的第三個點。這會給我一個三角形。我可以重複這個，直到我有一堆三角形。這裏的問題是三角形是分開的（它們不會被連接）。

我是不是在想這個？有沒有更簡單的方法來做到這一點？

Answer 1

你在找什麼是Delaunay triangulation！

它基本上做的是將三個點組合在一個三角形中，如果通過它們的圓不包含任何其他點，並且它有效地做到了。在一行上會出現特殊情況，或者在同一個圓上超過3個點。

Answer 2

我認爲你在正確的軌道上開始，將第一步想象爲創建3條邊，然後將每條邊都做成一個新的三角形，並在每條邊上增加一個點。理論上，每條邊應該有2個三角形。