Handritade Voronoi diagram (4 / 9 steg)
Steg 4: Delaunay triangulering
Detta kan vara den svåraste delen av hela processen. Som nämndes tidigare, måste vi ansluta varje nod till sina närmaste grannar, bildar ett nätverk av trianglar.
Ett annat sätt att beskriva "närmaste grannar" är att, på en viss nod, vi vill koppla den till den de två intilliggande noder som utgör en triangel med det minsta området som möjligt. Att göra något annat skulle innebära att andra noder kommer att falla inom våra circumcircle, vilket är fel. Med flest poäng, hitta närmaste grannarna är mycket intuitivt. För dem som inte är så uppenbara, Använd din härskare för att jämföra avstånd mellan andra noder i fråga.
När du börjar att ansluta kommer att noder och form trianglar saker börja få lättare. Sannolikt kommer du att möta scenarier där det finns inga andra alternativ än att ansluta två noder och slutföra en redan delvis bildade triangel. Bara vara säker på att du inte lämnar någon icke triangelformad former mellan noder och inte någonsin passerar en annan linje (trianglar kan inte dela utrymmen).
Jag tror Delaunay diagram ser ganska cool på egen hand, men låt oss hålla igång. Vi vill inte våra gamla kompis Georgy att få svartsjuk.