T: tema · Z: kodu büyüt · S: konuşmacı notları · F: tam ekran · Esc: genel bakış · ⌂ ders haritası
OYUN GEOMETRİSİ VE FİZİĞİ · G10
Üçgenleme ve Voronoi
Çokgeni üçgenlere bölmek, Delaunay üçgenlemesi, Voronoi diyagramı, noktaları düzgün serpiştirmek ve bir zindanın koridorlarını kurmak — “bu noktaları nasıl birbirine bağlarım, haritayı nasıl bölerim?”
PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

  1. Neden üçgen? — ekran kartı ve navmesh yalnızca üçgen tanır; çokgeni “kulak kesme” ile üçgenlere bölmek
  2. Delaunay üçgenlemesi — aynı noktaların en “dolgun” üçgenlemesi; boş çember kuralı; Bowyer–Watson
  3. Voronoi diyagramı — “en yakın kim?” sorusunun haritası; Delaunay’ın ikizi; harita ve bölge üretimi
  4. Düzgün serpiştirmek — Lloyd gevşetmesi ve Poisson disk: rastgele ama kümelenmeyen noktalar
  5. Zindan koridorları — odalar → Delaunay → en küçük yayılan ağaç → birkaç döngü
  6. Her adımda — günlük hayattan bir örnek → elle hesap → adım adım demo → kod (JavaScript / Python) → oyunlarda
🎮 Bu dersin sonunda…

bir oda zeminini üçgenlere bölebilecek, rastgele noktalardan dolgun bir üçgen ağı ve bölge haritası çıkarabilecek, ağaçları ya da kampları kümelenmeden serpiştirebilecek ve bir roguelike zindanının koridorlarını kurabileceksiniz.

🤔 ISINMA: HARİTA KENDİNİ NASIL BÖLER?

Bir strateji oyunu için haritaya rastgele 20 köy serpiştirdiniz. Şimdi iki şey lazım: (1) her köyün çevresindeki toprak, yani ülkenin bölgeleri; (2) köyleri birbirine bağlayan, birbirini kesmeyen yollar. Elle çizmek yok: her yeni haritada otomatik olmalı. Nasıl?

  • “Her toprak parçası en yakın köye ait olsun” dersek bölgeler kendiliğinden çıkar. Bu bölgelere Voronoi diyagramı denir.
  • İki köyün bölgeleri birbirine değiyorsa aralarına yol yap. Bu yollar hiç kesişmez ve dolgun üçgenler oluşturur: Delaunay üçgenlemesi.
  • İkisi aynı bilginin iki yüzü: birini bulan öbürünü de bulmuş olur.
  • Bu sunum bu iki yapıyı, onlara giden yolu (çokgeni üçgenlere bölmek) ve oyunlardaki kullanımlarını adım adım kuruyor.

🎯 Bu konu için bilmeniz gerekenler

Yeşil = gerekli · kesikli = faydalı ama şart değil. Tıklayınca ilgili sunuma gider.

G1 · Geometri Temelleri (çapraz çarpım, yön testi)En Küçük Yayılan Ağaç (Kruskal)Union-Find
G2 · Uzaysal Bölümleme (ızgara)Y9 · NavmeshY15 · Prosedürel Üretim
Neden?Bu sunumdaki her test G1’deki çapraz çarpımın işaretine dayanıyor: “nokta doğrunun solunda mı?”, “üçgen saat yönünde mi?”. Zindan bölümünde MST sunumundaki Kruskal’ı ve Union-Find’ı hazır kullanacağız.
🧰 Kodlamadan korkuyorsanızTek yeni formül “üç noktadan geçen çemberin merkezi”; onu da hazır formül olarak alıp elle bir kez sınayacağız. Gerisi toplama, çarpma ve karşılaştırma.

Mini sözlük

triangulationüçgenlemeBir alanı ya da nokta kümesini, kenarları kesişmeyen üçgenlere bölmek
ear clippingkulak kesmeÇokgenden içi boş, dışbükey köşeli üçgenleri (kulakları) tek tek kesip atma
reflex / convex vertexiçbükey / dışbükey köşeİç açısı 180°’den büyük / küçük olan köşe
circumcircleçevrel çemberBir üçgenin üç köşesinden geçen çember
Delaunay triangulationDelaunay üçgenlemesiHiçbir üçgenin çevrel çemberinin içinde başka nokta olmayan üçgenleme
edge flipkenar çevirmeİki üçgenin ortak kenarını öbür köşegenle değiştirme
Voronoi diagram · siteVoronoi diyagramı · merkezDüzlemi “en yakın merkez”e göre bölgelere ayırma · bölgelerin sahibi olan noktalar
perpendicular bisectordik açıortayİki noktaya eşit uzaklıktaki noktaların doğrusu
Lloyd relaxationLloyd gevşetmesiHer noktayı kendi Voronoi bölgesinin ortasına taşıyıp tekrarlama
Poisson disk samplingPoisson disk örneklemesiHiçbir ikisi belli bir uzaklıktan yakın olmayan rastgele noktalar üretme
LEVEL 0
Neden üçgen?
kulak kesme

Önce günlük hayattan: L biçimli bir odanın zeminini kesmek ✂️

🏠 Kâğıttan bir oda123456iç köşe: kulak olamaz

Elinizde L biçimli bir odanın kâğıttan planı ve bir makas var. Görev: planı yalnızca düz kesiklerle üçgenlere bölmek.

  • Bir köşeyi iki komşusuyla birleştiren düz bir kesik atın: kopan parça bir üçgen.
  • L’nin içe dönük köşesinden (3) kesik atarsanız makas odanın dışına çıkar: olmaz.
  • Kopan üçgenin içinde başka köşe kalırsa da olmaz.
  • Kestikçe plan bir köşe küçülür: 6 köşe → 4 üçgen.
Oyunda bunu kim istiyor?
  • Ekran kartı yalnızca üçgen çizer. Bir sprite’ın çokgen çarpışma şekli, bir harita bölgesi, bir yazı tipindeki harf: hepsi çizilmeden önce üçgenlere bölünür.
  • Navmesh (Y9): yürünebilir alan çokgenlerden kurulur, A* üçgenlerin (ya da dışbükey çokgenlerin) üstünde arar.
  • Fizik motorları içbükey şekilleri dışbükey parçalara böler; çarpışma testleri (G3) dışbükey şekilde çalışır.

Makasla yaptığımız işin adı kulak kesme; kopan her üçgen bir “kulak”.

Fikir: kulağı bul, kes, tekrarla

  • Kulak: art arda üç köşe (önceki, şimdiki, sonraki) öyle ki (1) şimdiki köşe dışbükey (iç açısı 180°’den küçük) ve (2) bu üç köşenin üçgeninin içinde başka köşe yok.
  • Dışbükey mi? G1’deki çapraz çarpım: köşeler saat yönünün tersine sıralıysa cross(önceki, şimdiki, sonraki) > 0.
  • İçinde köşe var mı? Kalan her köşe için “üçgenin içinde mi?” testi (üç çapraz çarpımın hepsi ≥ 0).
  • Kulaksa: üçgeni kaydet, şimdiki köşeyi listeden sil. Değilse: sonraki köşeye geç.
  • Üç köşe kalınca son üçgen. n köşeli çokgen her zaman n − 2 üçgen verir.

Her çokgende en az iki kulak vardır (iki kulak teoremi, 1975); bu yüzden yöntem hiç takılmaz. Basit hâli n² zamanlıdır; oyunlardaki çokgenler için fazlasıyla hızlı.

Elle izleme: L biçimli oda, köşe 3’ten başla
sırabakılan köşedışbükey?içi boş?sonuç
13 (2–3–4)✗ iç köşe—geç
24 (3–4–5)✓✓kes → üçgen 3-4-5
35 (3–5–6)✓✓kes → üçgen 3-5-6
46 (3–6–1)✓✓kes → üçgen 3-6-1
5kalan 1–2–3son üçgen

6 köşe → 4 üçgen = 6 − 2. İç köşe (3) asla kulak olamadı; ama ötekiler kesildikçe onun açısı da küçüldü ve sonunda son üçgenin bir parçası oldu.

🧭 DEMOYU OKUMA KILAVUZU (bir sonraki slayt)
  1. Kalın siyah çizgi: çokgenin kendisi. Mavi kesikli çizgi: henüz kesilmemiş kısım.
  2. Renkli üçgenler: kesilen kulaklar.
  3. Yeşil üçgen: az önce bulunan kulak. Kırmızı üçgen: sınanıp reddedilen köşe; sağdaki günlük nedenini yazar (iç köşe mi, içinde başka köşe mi?).
  4. Gri numaralar: artık listede olmayan (kesilip atılan) köşeler. Tarama bilerek bir iç köşeden başlıyor ki reddedilen köşeleri de görelim.

Canlı: kulak kesme ✂️

  1. “L biçimli oda”da adım adım ilerleyin; sonucu önceki slayttaki tabloyla karşılaştırın.
  2. “U biçimli oda”yı seçin: 3 ve 4 iç köşe olduğu için reddediliyor. 8. köşe ise dışbükey olduğu hâlde reddediliyor: günlükte nedeni ne? Kırmızı üçgenin içinde hangi köşe kalıyor?
  3. “Yıldız”da 10 köşe var: kaç üçgen çıkacağını önceden söyleyin. İlk bakılan içe dönük köşe (2) reddediliyor; bir uç kesildikten sonra komşu iç köşeler neden kulak olabiliyor?
  4. Her çokgende sonunda kaç üçgen çıktı? Köşe sayısıyla ilişkisi ne?
  1. Kalın siyah çizgi: çokgenin kendisi. Mavi kesikli çizgi: henüz kesilmemiş kısım.
  2. Renkli üçgenler: kesilen kulaklar.
  3. Yeşil üçgen: az önce bulunan kulak. Kırmızı üçgen: sınanıp reddedilen köşe; sağdaki günlük nedenini yazar (iç köşe mi, içinde başka köşe mi?).
  4. Gri numaralar: artık listede olmayan (kesilip atılan) köşeler. Tarama bilerek bir iç köşeden başlıyor ki reddedilen köşeleri de görelim.
🔎 DEMODA DENEYİN
  1. “L biçimli oda”da adım adım ilerleyin; sonucu önceki slayttaki tabloyla karşılaştırın.
  2. “U biçimli oda”yı seçin: 3 ve 4 iç köşe olduğu için reddediliyor. 8. köşe ise dışbükey olduğu hâlde reddediliyor: günlükte nedeni ne? Kırmızı üçgenin içinde hangi köşe kalıyor?
  3. “Yıldız”da 10 köşe var: kaç üçgen çıkacağını önceden söyleyin. İlk bakılan içe dönük köşe (2) reddediliyor; bir uç kesildikten sonra komşu iç köşeler neden kulak olabiliyor?
  4. Her çokgende sonunda kaç üçgen çıktı? Köşe sayısıyla ilişkisi ne?

🔗 Başka gözle: etkileşimli anlatımlar ve yazılar

Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.

🔗 Delaunator
Mapbox
Delaunay üçgenlemesi ve Voronoi diyagramının nasıl kurulduğunu gösteren etkileşimli sayfa.
🔴 Voronoi maps tutorial
Red Blob Games (Amit Patel)
Rastgele noktalardan Voronoi bölgelerine, oradan kara-deniz haritasına adım adım; her adımın kodu ve çizimi yan yana.
🔴 Polygonal Map Generation for Games
Amit Patel
Voronoi hücreleriyle ada, nehir, biyom üreten ünlü yazı; çizimleri ve demosuyla.
🔗 Lloyd’s Relaxation
Jason Davies
Lloyd gevşetmesini canlı izleyin: noktalar her adımda kendi Voronoi hücresinin ortasına kayar.
🔗 Visualizing Algorithms
Mike Bostock
Poisson disk örneklemesi dahil birkaç algoritmanın çok güzel hareketli anlatımı; rastgele ve Poisson dağılımı yan yana.

Kod: kulak kesme

🎒 Kodu okuyalım

ifadene demekneden böyle
cross(...) > 0şimdiki köşe dışbükeyköşeler saat yönünün tersine sıralı; içbükey köşede işaret döner
icinde(p, a, b, c)p üçgenin içinde mi (ya da kenarında)üç kenarın hepsinin solunda olmak = içeride olmak (G1)
kalan.splice(i % n, 1)kesilen kulağın ucunu listeden silçokgen bir köşe küçülür; komşular artık birbirine bağlı
bosuna sayacıüst üste kaç köşe reddedildibütün köşeler reddedilirse çokgen bozuk (kendini kesiyor ya da ters sıralı): sonsuz döngüye girme
i % nlistenin sonuna gelince başa dönçokgen bir halka: son köşenin sonraki komşusu ilk köşe

Oyunlarda: motorlar ve kütüphaneler

  • Godot: Geometry2D.triangulate_polygon() kulak kesme; Polygon2D ve çarpışma çokgenleri bununla çizilir.
  • three.js: ShapeUtils.triangulateShape, Mapbox’ın earcut kütüphanesini kullanır (delikli çokgenler, binlerce köşe; haritalar ve yazılar).
  • Unity: PolygonCollider2D ve SpriteShape içbükey şekilleri parçalara ayırır.
  • Recast (Unreal ve pek çok oyunun navmesh kütüphanesi): yürünebilir alanı önce çokgenlere, sonra ayrıntı ağı için üçgenlere böler.
Pratikte dikkat
  • Köşelerin sırası: saat yönünde verilirse bütün köşeler “içbükey” görünür. Önce alanın işaretine bakın (G1, ayakkabı bağı) ve gerekirse ters çevirin.
  • Delikli çokgen (ortasında sütun olan oda): deliği ince bir “köprü” kenarıyla dış sınıra bağlayıp tek çokgene çevirmek gerekir (earcut bunu yapar).
  • Kendini kesen çokgen üçgenlenemez; çizim aracında engelleyin.
  • Kulak kesme ince üçgenler üretebilir. Görüntü için sorun değil; navmesh ve arazi için sorun: sonraki bölüm.

🎬 Ara: kulak kesme, çizimlerle

Polygon Triangulation [1] – Overview of Ear Clipping
Two-Bit Coding · 14 dk 10 sn · YouTube’da aç

Az önce elle yaptığımız işin yavaş ve çizimli anlatımı: dışbükey/içbükey köşe, “içinde nokta var mı?” testi ve neden her zaman bir kulak bulunduğu. İkinci bölümde (Kaynaklar) aynı algoritmanın kodu yazılıyor.

🤔 İzlerkenVideoda “kulak” nasıl tanımlanıyor; bizim iki koşulumuzla aynı mı? Köşeler ters sırada verilirse ne oluyor? n köşeden neden tam n − 2 üçgen çıkıyor?
Quiz 1 · kulak kesme
Bir seviye editöründe 12 köşeli bir oda çizdiniz ve kulak kesme ile üçgenlediniz. Kaç üçgen çıkar?
n köşeli basit bir çokgen her zaman n − 2 üçgen verir: her kesik bir köşeyi ve bir üçgeni götürür; son üç köşe son üçgeni oluşturur. 12 − 2 = 10. Biçim yalnızca hangi üçgenlerin çıkacağını değiştirir, sayısını değil.
LEVEL 1
Delaunay üçgenlemesi
boş çember kuralı

Problem: aynı noktalar, çok sayıda üçgenleme

🎮 Noktalardan ağ
  • Bir arazinin yükseklik ölçümleri (rastgele dağılmış noktalar), bir haritadaki köyler, zindandaki odaların merkezleri: elimizde çokgen değil, noktalar var.
  • Onları kenarları kesişmeyen üçgenlerle birbirine bağlamak istiyoruz: arazi ağı, yol ağı, “kim kimin komşusu?”
  • Ama aynı noktalar pek çok farklı biçimde üçgenlenebilir. Dört nokta için bile iki seçenek var: hangi köşegeni çizeceğiz?
İnce üçgen neden kötü?
  • Arazi: uzun ince üçgenler yükseklikte sivri “bıçak sırtları” ve gölgelemede çizgiler bırakır.
  • Navmesh: ince üçgenin ortasından geçen yol zikzak çizer; karakter duvara sürtünür.
  • Komşuluk: ince üçgen birbirinden uzak iki noktayı “komşu” yapar; köyler arasına saçma yollar çekilir.
  • Sayısal hata: çok dar açılı üçgenlerde kayan nokta hataları büyür.

Hedef: üçgenleri olabildiğince dolgun (eşkenara yakın) yapmak; yani en dar açıyı en büyük tutmak.

Çizimle: aynı dört nokta, iki köşegen

AC köşegeni: ABC ve ACDen dar açı 26,6° ✗merkez (4, 5), r = 5D çemberin içinde ✗A (0, 2)B (4, 0)C (8, 2)D (4, 4)BD köşegeni: ABD ve BCDen dar açı 53,1° ✓merkez (2,5; 2), r = 2,5C dışarıda ✓A (0, 2)B (4, 0)C (8, 2)D (4, 4)

Solda AC köşegeni: ABC üçgeninin açıları 26,6°, 126,9°, 26,6°; ince. Bu üçgenin çevrel çemberi (merkez (4, 5), yarıçap 5) dördüncü noktayı, D’yi içine alıyor. Sağda BD köşegeni: ABD’nin açıları 53,1°, 63,4°, 63,4°; dolgun. Çevrel çemberi C’yi dışarıda bırakıyor. Kural: çember başka bir noktayı içine alıyorsa köşegeni çevir.

Fikir: boş çember kuralı ve kenar çevirme

  • Delaunay üçgenlemesi: hiçbir üçgenin çevrel çemberinin içinde başka nokta bulunmayan üçgenleme. (Boris Delaunay, 1934.)
  • Aynı noktaların bütün üçgenlemeleri içinde en dar açıyı en büyük yapan budur: dolgun üçgenler kendiliğinden gelir.
  • Kenar çevirme: bir köşegenin iki yanındaki üçgenlerden birinin çemberi karşıdaki noktayı içine alıyorsa köşegeni öbürüyle değiştir. Çevrilecek kenar kalmayınca üçgenleme Delaunay’dır.
  • Çemberin merkezi formülle bulunur (bir sonraki laboratuvarda yazacaksınız); “içinde mi?” sorusu merkeze uzaklığın kareyle karşılaştırılmasıdır.

Noktaların dördü aynı çemberin üstündeyse (kare gibi) iki köşegen de geçerlidir: Delaunay tek değildir. Kodlarda bu eşitlik durumu için küçük bir tolerans bırakılır.

Elle hesap: A(0, 2), B(4, 0), C(8, 2), D(4, 4)
soruhesapsonuç
ABC’nin çember merkeziA ile B’ye eşit uzak, x = 4: 16 + (y − 2)² = y²(4, 5), r = 5
D çemberin içinde mi?|D − (4, 5)| = 11 < 5 → içinde ✗
ABD’nin çember merkeziB ile D’ye eşit uzak, y = 2: x² = (x − 4)² + 4(2,5; 2), r = 2,5
C çemberin içinde mi?|C − (2,5; 2)| = 5,55,5 > 2,5 → dışarıda ✓
en dar açıABC: 26,6° · ABD: 53,1°çevirme dar açıyı iki katına çıkardı

Fikir: Bowyer–Watson, noktaları tek tek ekleyerek

  • Bütün noktaları içine alan dev bir üçgenle başla.
  • Noktaları birer birer ekle. Her yeni nokta için:
  • ① Çevrel çemberi yeni noktayı içine alan bütün üçgenleri bul: bunlar artık geçersiz (“kötü” üçgenler).
  • ② Onları sil. Geriye bir oyuk kalır; oyuğun sınırı, yalnızca tek bir kötü üçgende geçen kenarlardır.
  • ③ Oyuğun her sınır kenarını yeni noktaya bağla: yelpaze gibi yeni üçgenler.
  • Bütün noktalar eklenince dev üçgenin köşelerine değen üçgenleri at.
Neden doğru?

Kötü üçgenler tam olarak yeni noktanın “boş çember” kuralını bozduğu üçgenlerdir. Onları silip yeni noktaya bağlayınca oluşan üçgenlerin çemberleri yine boştur. Her adımın sonunda üçgenleme Delaunay kalır.

  • Basit hâli: her eklemede bütün üçgenlere bakılır → n² civarı. 1.000 nokta için yeterince hızlı.
  • Hızlı kütüphaneler (Mapbox delaunator, d3-delaunay) başka bir yöntemle (süpürme) 100.000 noktayı saniyenin onda birinde üçgenler.
🧭 DEMOYU OKUMA KILAVUZU (bir sonraki slayt)
  1. Turuncu büyük nokta: az önce eklenen nokta. Gri noktalar henüz eklenmemiş.
  2. 1. adım (kırmızı): çevrel çemberi yeni noktayı içine alan üçgenler ve çemberleri (kesikli). Bunlar silinecek.
  3. 2. adım (yeşil): oyuğun kenarlarından yeni noktaya çekilen yeni üçgenler.
  4. Sağdaki günlük her adımı yazar ve o anki en dar açıyı gösterir.
  5. Alana tıklarsanız yeni bir nokta eklenir ve onun adımları gösterilir. “Rastgele 12 nokta” baştan başlar.

Canlı: Bowyer–Watson adım adım 🔺

  1. İlk üç noktayı ekleyin: neden kırmızı üçgen yok? (Hepsi görünmeyen dev üçgeni bölüyor.)
  2. 5. nokta eklenirken kaç üçgen bozuluyor? Kesikli çemberlerin hepsinin turuncu noktayı içine aldığını görün.
  3. Bütün noktalar eklenince mavi çemberlere bakın: içinde nokta olan tek bir çember bulabiliyor musunuz?
  4. Mevcut bir üçgenin çemberinin içine tıklayın: o üçgen bozuluyor mu? Çemberin dışına tıklayın: kaç üçgen bozuldu?
  1. Turuncu büyük nokta: az önce eklenen nokta. Gri noktalar henüz eklenmemiş.
  2. 1. adım (kırmızı): çevrel çemberi yeni noktayı içine alan üçgenler ve çemberleri (kesikli). Bunlar silinecek.
  3. 2. adım (yeşil): oyuğun kenarlarından yeni noktaya çekilen yeni üçgenler.
  4. Sağdaki günlük her adımı yazar ve o anki en dar açıyı gösterir.
  5. Alana tıklarsanız yeni bir nokta eklenir ve onun adımları gösterilir. “Rastgele 12 nokta” baştan başlar.
🔎 DEMODA DENEYİN
  1. İlk üç noktayı ekleyin: neden kırmızı üçgen yok? (Hepsi görünmeyen dev üçgeni bölüyor.)
  2. 5. nokta eklenirken kaç üçgen bozuluyor? Kesikli çemberlerin hepsinin turuncu noktayı içine aldığını görün.
  3. Bütün noktalar eklenince mavi çemberlere bakın: içinde nokta olan tek bir çember bulabiliyor musunuz?
  4. Mevcut bir üçgenin çemberinin içine tıklayın: o üçgen bozuluyor mu? Çemberin dışına tıklayın: kaç üçgen bozuldu?

Kod: Bowyer–Watson (1/2)

Kod: Bowyer–Watson (2/2)

🎒 Kodu okuyalım

ifadene demekneden böyle
M = 1e5 dev üçgenbütün noktaları içine alacak kadar büyük bir başlangıçilk nokta eklenirken de bölünecek bir üçgen olsun
(p − merkez)² < r²p çemberin içindekarekök almadan karşılaştır (Y0); eşitlik (tam çemberin üstü) içeride sayılmaz
kenarlar.spliceiki kötü üçgende geçen kenarı siliki kötü üçgenin ortak kenarı oyuğun içinde kalır; sınırda değildir
yap(a, b, n)sınır kenarı + yeni nokta = yeni üçgenoyuk, yeni noktanın çevresinde yelpaze gibi dolar
every(i => i >= 3)dev üçgenin köşelerine değeni atilk üç indeks dev üçgenin; gerçek noktalar 3’ten başlıyor

🎬 Ara: Delaunay, üç dakikada

Delaunay Triangulation
SCIco · 3 dk 24 sn · YouTube’da aç

Boş çember kuralının ve kenar çevirmenin hareketli bir özeti. Kısa olduğu için derste izleyip “hangi slaytta görmüştük?” diye eşleştirebilirsiniz.

🤔 İzlerkenVideoda kenar ne zaman çevriliyor? Gösterilen ince üçgen ile bizim eşkenar dörtgendeki ABC üçgeni arasında ne ortak? Delaunay’ın en dar açıyla ilişkisi videoda nasıl anlatılıyor?
Quiz 2 · Delaunay
Bowyer–Watson ile bir nokta eklediniz. Yeni noktanın hemen yanındaki ABC üçgeninin çevrel çemberi yeni noktayı içine alıyor, ama yeni nokta ABC’nin içinde değil. Ne olur?
Ölçüt “nokta üçgenin içinde mi?” değil, “nokta üçgenin çevrel çemberinin içinde mi?”. Çember içindeyse boş çember kuralı bozulmuştur; üçgen kötüdür ve silinir. Sık yapılan hata yalnızca noktanın içine düştüğü üçgeni bölmek: sonuç bir üçgenlemedir ama Delaunay değildir.
LEVEL 2
Voronoi diyagramı
“en yakın kim?” sorusunun haritası

Önce günlük hayattan: en yakın eczane, en yakın kuyu 🚰

Şehirde altı nöbetçi eczane var. Her mahalle en yakın eczaneye gider. Haritayı “bu mahalle hangi eczaneye gider?” diye boyarsanız şehir kendiliğinden bölgelere ayrılır. İki bölgenin sınırında oturan biri iki eczaneye eşit uzaklıktadır.

John Snow’un 1854 kolera haritası
1854, Londra. John Snow kolera ölümlerini (siyah çubuklar) haritaya işledi; neredeyse hepsi Broad Street pompasına en yakın evlerdeydi. Pompanın kolu söküldü, salgın söndü: Voronoi diyagramının en ünlü örneği.
Görsel: John Snow (1854), Wikimedia Commons, kamu malı

Matematikteki adı: Voronoi diyagramı (Georgy Voronoi, 1908). Her bölgenin sahibi olan noktaya merkez denir.

🎮 Oyunda aynı soru
  • Bölge ve etki: “Bu toprak hangi kaleye ait?” Strateji oyunlarının sınırları, bir RTS’de hangi üssün hangi kaynağa yakın olduğu (Y12 etki haritaları).
  • Harita üretimi: rastgele noktalar → Voronoi bölgeleri → her bölge bir arazi parçası: deniz, kara, dağ, biyom.
  • En yakın tesis: “En yakın sağlık kutusu / doğma noktası hangisi?” sorusunu her kare hesaplamak yerine haritayı önceden bölmek.
  • Kırılma efektleri: camı ya da kayayı Voronoi hücrelerine bölüp parçaları ayrı ayrı uçurmak (Blender ve Houdini’nin kırılma araçları).

Çizimle: üç kuyu, üç bölge

köşe (2, 2)üçüne de √8 ≈ 2,83A (0, 0)B (4, 0)C (0, 4)(1, 3) → Cx = 2y = 2y = x

Kuyular A(0, 0), B(4, 0) ve C(0, 4)’te.

  • A ile B’ye eşit uzak noktalar: aralarındaki parçanın dik açıortayı, x = 2.
  • A ile C arası: y = 2. B ile C arası: y = x.
  • Üç sınır tek noktada buluşur: (2, 2). Bu nokta üç kuyuya da eşit uzaktır (√8 ≈ 2,83): yani ABC üçgeninin çevrel çemberinin merkezi.
  • (1, 3) noktası: A’ya √10 ≈ 3,16, C’ye √2 ≈ 1,41 → C’nin bölgesinde.

İkizlik: Voronoi köşeleri = Delaunay üçgenlerinin çember merkezleri; iki bölge komşuysa merkezleri arasında bir Delaunay kenarı vardır. Birini bulan öbürünü de bulmuş olur.

🧭 DEMOYU OKUMA KILAVUZU (bir sonraki slayt)
  1. Her rengi bir kuyunun (simge) bölgesi: o renkteki her nokta en yakın o kuyuya.
  2. Koyu noktalı çizgiler: bölge sınırları. Sınırdaki her nokta iki kuyuya eşit uzak.
  3. Fare = siz. Kalın çizgi en yakın kuyuya, kesikli çizgi ikinci en yakına. Günlükte iki uzaklık ve aralarındaki fark yazar.
  4. Kuyuları sürükleyebilirsiniz.
  5. “Delaunay’i üstüne çiz”: kesikli çizgiler Delaunay kenarları, kırmızı noktalar Voronoi köşeleri.

Canlı: en yakın kuyu 🗺️

  1. Fareyi bir sınırın üstüne getirin: “fark” kaç oluyor?
  2. Bir kuyuyu öbürlerinin ortasına sürükleyin: komşu bölgeler nasıl küçülüyor? Bir kuyuyu kenara sürükleyin: bölgesi neden sonsuza (çerçevenin dışına) taşıyor?
  3. “Delaunay’i üstüne çiz”i açın: her kesikli kenar iki komşu bölgenin merkezlerini bağlıyor mu? Kırmızı noktalar bölge köşelerine mi düşüyor?
  4. Uzaklığı “ızgarada yürüme”ye çevirin: sınırlar neden kırıldı? Bir ızgara oyununda hangisi doğru cevaptır?
  1. Her rengi bir kuyunun (simge) bölgesi: o renkteki her nokta en yakın o kuyuya.
  2. Koyu noktalı çizgiler: bölge sınırları. Sınırdaki her nokta iki kuyuya eşit uzak.
  3. Fare = siz. Kalın çizgi en yakın kuyuya, kesikli çizgi ikinci en yakına. Günlükte iki uzaklık ve aralarındaki fark yazar.
  4. Kuyuları sürükleyebilirsiniz.
  5. “Delaunay’i üstüne çiz”: kesikli çizgiler Delaunay kenarları, kırmızı noktalar Voronoi köşeleri.
🔎 DEMODA DENEYİN
  1. Fareyi bir sınırın üstüne getirin: “fark” kaç oluyor?
  2. Bir kuyuyu öbürlerinin ortasına sürükleyin: komşu bölgeler nasıl küçülüyor? Bir kuyuyu kenara sürükleyin: bölgesi neden sonsuza (çerçevenin dışına) taşıyor?
  3. “Delaunay’i üstüne çiz”i açın: her kesikli kenar iki komşu bölgenin merkezlerini bağlıyor mu? Kırmızı noktalar bölge köşelerine mi düşüyor?
  4. Uzaklığı “ızgarada yürüme”ye çevirin: sınırlar neden kırıldı? Bir ızgara oyununda hangisi doğru cevaptır?

Kod: Voronoi’nin en kısa hâli

  • Her piksel için bütün merkezlere bak, en yakınının rengini al. Hepsi bu.
  • Maliyet: piksel × merkez = 400 · 300 · 12 = 1,44 milyon uzaklık. Tek seferlik bir harita için yeter; her karede değil.
  • Karekök almıyoruz: en yakını bulmak için uzaklığın karesini karşılaştırmak yeter (Y0).
  • “Gerçek” Voronoi (kenarlar ve köşeler hâlinde) için iki yol: Delaunay’ı kurup her üçgenin çember merkezini komşu üçgeninkiyle birleştirmek (ikizlik) ya da Fortune’un süpürme algoritması.
  • Ekran kartında: her merkez için bir koni çizip derinlik testine “en yakını” buldurmak; binlerce merkez bir karede.

Oyunlarda: Voronoi’den harita

🗺️ Amit Patel: Polygonal Map Generation (2010)
  • Rastgele noktalar → Lloyd gevşetmesiyle düzgünleştirme (sonraki bölüm) → Voronoi bölgeleri.
  • Kenardan uzaklığa ve gürültüye göre her bölge kara ya da deniz.
  • Yükseklik kıyıdan uzaklaştıkça artar; nehirler Delaunay kenarları boyunca yokuş aşağı akar.
  • Nem ve yükseklikten biyom: çöl, orman, tundra. Bölgeler arası komşuluk, yol ve nehir ağını kendiliğinden verir.
  • Red Blob Games’te etkileşimli anlatımı ve 2022’deki adım adım Voronoi harita eğitimi var (Kaynaklar).
Başka kullanımlar
  • Etki haritası (Y12): her birim bir merkez; düşman ile dostun bölgeleri arasındaki sınır cephe hattıdır.
  • Bölge kontrolü: bir parti oyununda “boyanan alan” ya da bir strateji oyununda kalelerin topraklarını hesaplamak.
  • Kırılma: çarpma noktasının çevresine sık, uzağına seyrek merkezler serpip Voronoi hücrelerini parça olarak ayırmak; cam ve kaya kırılmaları gerçekçi görünür.
  • Doku: “hücresel gürültü” (Worley gürültüsü) her pikselin en yakın merkeze uzaklığıdır; taş döşeme, deri, su yansıması dokuları.

🎬 Ara: Voronoi ile harita üretimi

Voronoi Diagrams and Procedural Map Generation
MAN OF EERIE LETTERS · 15 dk 36 sn · YouTube’da aç

Voronoi bölgelerinden bir oyun haritasına giden yol: noktaları serpiştirmek, bölgeleri kara ve denize ayırmak, yükseklik ve biyom vermek. Amit Patel’in yazısındaki adımların görsel anlatımı.

🤔 İzlerkenVideoda noktalar neden tamamen rastgele bırakılmıyor? Kıyı çizgisi nasıl belirleniyor? Delaunay kenarları haritada neye dönüşüyor?
LEVEL 3
Düzgün serpiştirmek
Lloyd gevşetmesi ve Poisson disk

Problem ve fikir: rastgele noktalar kümelenir

Tamamen rastgele = kötü dağılım
  • random() ile 100 ağaç dikin: bazıları iç içe geçer, bazı yerler çıplak kalır. Göz bunu hemen “yapay” bulur.
  • Voronoi haritasında küçücük ve dev bölgeler yan yana çıkar; bir ülke bir köy, öbürü bir kıta olur.
  • Düzenli ızgara da kötü: ağaçlar asker gibi dizilir, yine yapay görünür.
  • İstenen: rastgele görünen ama kümelenmeyen noktalar. Doğada da böyledir: ağaçlar birbirinin ışığını keser, aralarında kendiliğinden boşluk kalır.
İki çözüm
  • Lloyd gevşetmesi: rastgele başla; her noktayı kendi Voronoi bölgesinin ağırlık merkezine taşı; tekrarla. Kalabalık yerdeki noktalar küçük bölgelerinden dışarı itilir, boş yerlere yayılır. 2–3 adım yeter.
  • Poisson disk (Bridson, 2007): baştan kural koy: “hiçbir iki nokta r’den yakın olmasın.” Mevcut bir noktanın çevresindeki r … 2r halkasına aday at; kurala uyuyorsa kabul et. Kontrol için G2’deki ızgara: hücre boyu r / √2, her hücrede en fazla bir nokta; yalnızca çevredeki 5 × 5 hücreye bakılır.
  • Lloyd’un bölgeleri daha eşit boyludur (harita için); Poisson disk daha hızlıdır ve uzaklık garantisi verir (ağaç, taş, düşman kampı için).

Canlı: Lloyd gevşetmesi 🌀

  1. “1 Lloyd adımı”na birkaç kez basın; kırmızı çizgiler (noktanın gittiği yol) her adımda kısalıyor mu?
  2. Günlükteki “en yakın iki nokta arası” her adımda nasıl değişiyor?
  3. 10 adımdan sonra bölgelerin boyları birbirine yaklaştı mı? Noktalar düzenli bir ızgaraya dönüştü mü?
🔎 DEMODA DENEYİN
  1. “1 Lloyd adımı”na birkaç kez basın; kırmızı çizgiler (noktanın gittiği yol) her adımda kısalıyor mu?
  2. Günlükteki “en yakın iki nokta arası” her adımda nasıl değişiyor?
  3. 10 adımdan sonra bölgelerin boyları birbirine yaklaştı mı? Noktalar düzenli bir ızgaraya dönüştü mü?

Canlı: Poisson disk ile orman 🌲

  1. “Tamamen rastgele”yi seçin: 46’dan yakın kaç ağaç çifti var?
  2. “Poisson disk”e dönüp adım adım ilerleyin: turuncu halka, aktif noktanın aday attığı bölge. Yeşil çizgi kabul edilen aday.
  3. “Sonuna kadar”: kaç ağaç dikildi, 46’dan yakın çift kaldı mı? Boş kalan büyük bir delik var mı?
  4. Rastgele 120 ağaç vs Poisson diskteki sayı: hangisi “daha dolu” görünüyor? Neden?
🔎 DEMODA DENEYİN
  1. “Tamamen rastgele”yi seçin: 46’dan yakın kaç ağaç çifti var?
  2. “Poisson disk”e dönüp adım adım ilerleyin: turuncu halka, aktif noktanın aday attığı bölge. Yeşil çizgi kabul edilen aday.
  3. “Sonuna kadar”: kaç ağaç dikildi, 46’dan yakın çift kaldı mı? Boş kalan büyük bir delik var mı?
  4. Rastgele 120 ağaç vs Poisson diskteki sayı: hangisi “daha dolu” görünüyor? Neden?

Kod: Poisson disk (Bridson) (1/2)

Kod: Poisson disk (Bridson) (2/2)

🎬 Ara: nesneleri doğal serpiştirmek

[Unity] Procedural Object Placement (E01: Poisson Disc Sampling)
Sebastian Lague · 18 dk 34 sn · YouTube’da aç

Az önceki algoritmanın Unity’de sıfırdan yazılışı: halkaya aday atmak, ızgarayla komşu aramak, aktif liste. Sebastian Lague’ın her adımı çizerek anlatan üslubu bu konu için çok uygun.

🤔 İzlerkenIzgara hücresinin boyu neden r / √2 seçiliyor? Bir hücrede neden en fazla bir nokta olabiliyor? Videodaki “aday sayısı” (k) büyüyünce sonuç nasıl değişiyor?
Quiz 3 · serpiştirme
Açık dünya oyununuzda ağaçlar r = 4 metre aralıkla Poisson disk ile dikiliyor. Kontrol ızgarasının hücre boyu neden r / √2 ≈ 2,83 metre?
Kenarı r / √2 olan karenin köşegeni tam r’dir. Aynı hücredeki iki nokta arası en çok köşegen kadar olabilir, yani r’den kısa: kural bunu yasakladığı için her hücrede en fazla bir nokta bulunur. Böylece ızgara basit bir dizi olur ve komşu kontrolü yalnızca çevredeki 5 × 5 hücreye bakar.
LEVEL 4
Zindan koridorları
Delaunay + en küçük yayılan ağaç

Problem ve fikir: odaları nasıl bağlamalı?

🎮 Roguelike zindanı
  • Odalar rastgele yerleşti. Şimdi koridorlar: her odaya ulaşılabilmeli, koridorlar birbirini kesmemeli, uzak odalar arasına saçma uzun koridor çekilmemeli.
  • Ama zindan tek bir uzun zincir de olmamalı: oyuncu hep geri dönmek zorunda kalır, keşif sıkıcılaşır. Biraz döngü (kestirme) iyidir.
  • Herkesi herkese bağlamak: n oda için n(n−1)/2 koridor; kesişen, iç içe geçen bir yumak.
Beş aşama (TinyKeep, 2013)
aşamane yaparhangi sunum?
1 · odalarrastgele yerleştir, çakışanları atG3 (AABB)
2 · Delaunayoda merkezlerini üçgenle: kim kimin doğal komşusu?bu sunum
3 · MSTDelaunay kenarlarından en kısa toplamla herkesi bağlaMST (Kruskal), Union-Find
4 · döngüağaçta olmayan kenarların ~%15’ini geri ekle—
5 · koridorher kenarı L biçimli bir koridora çevir—

Neden önce Delaunay? MST’yi bütün n² çift üzerinde de kurabilirdik; ama Delaunay yalnızca ~3n kenar verir (çok daha hızlı) ve MST her zaman Delaunay kenarlarının içindedir: hiçbir şey kaybetmeyiz.

Canlı: beş aşamada zindan 🏰

  1. Aşamaları tek tek ilerleyin. 3. aşamada (MST) kenar sayısı oda sayısından kaç eksik? Neden?
  2. 4. aşamada geri eklenen turuncu kenarlar hangi odalar arasında bir kestirme açtı?
  3. “Yeni zindan”a birkaç kez basın: Delaunay kenarları hiç birbirini kesiyor mu? Çok uzak iki oda arasında kenar var mı?
  4. Geri ekleme oranı %0 olsaydı ve %100 olsaydı zindanda dolaşmak nasıl olurdu?
🔎 DEMODA DENEYİN
  1. Aşamaları tek tek ilerleyin. 3. aşamada (MST) kenar sayısı oda sayısından kaç eksik? Neden?
  2. 4. aşamada geri eklenen turuncu kenarlar hangi odalar arasında bir kestirme açtı?
  3. “Yeni zindan”a birkaç kez basın: Delaunay kenarları hiç birbirini kesiyor mu? Çok uzak iki oda arasında kenar var mı?
  4. Geri ekleme oranı %0 olsaydı ve %100 olsaydı zindanda dolaşmak nasıl olurdu?

Kod: zindanı bağlamak

  • delaunay() az önceki Bowyer–Watson; kok() Union-Find sunumundaki yol sıkıştırmalı bulma.
  • Kruskal: kenarları kısadan uzuna sırala; iki ucu farklı kümedeyse ağaca al, aynı kümedeyse “artan” listesine koy.
  • Artan kenarların bir kısmı geri eklenir: döngü ve kestirmeler.
  • Koridoru çizmek ayrı iş: L biçimli (önce yatay, sonra dikey) ya da A* ile (Y8) engellerin etrafından.

🎬 Ara: Delaunay ve MST ile 3B zindan

Procedurally Generated 3D Dungeons
Vazgriz · 9 dk 42 sn · YouTube’da aç

Az önceki beş aşamanın üç boyutlu hâli: odalar, Delaunay (bu kez dört yüzlülerle), en küçük yayılan ağaç, geri eklenen kenarlar ve koridorlar için A*. TinyKeep yönteminin oyun geliştirici gözüyle uygulanışı.

🤔 İzlerkenVideoda geri eklenen kenar oranı kaç? 3B’de koridorlar merdivenleri nasıl çözüyor? Bizim demodaki L biçimli koridorların yerine ne kullanılıyor?
LEVEL 5
Hepsi bir arada
laboratuvarlar, araçlar, kapanış

🌱 Isınma kodu: çevrel çemberin merkezi

Başlangıç kodu merkezi iki kat uzağa koyuyor: d’nin başındaki 2 çarpanı unutulmuş. Önce elle sınayın: A(0, 0), B(4, 0), C(0, 4) için merkez (2, 2) olmalı (“Çizimle: üç kuyu” slaytı). Düzeltince testlerin hepsi geçmeli.

🐍 Laboratuvar: nokta çemberin içinde mi?

Bowyer–Watson’ın kalbi bu fonksiyon: “kötü üçgen” tam olarak cemberin_icinde(...) True dönen üçgendir. Karekök almadan kareleri karşılaştırın; eşitlikte (nokta tam çemberin üstünde) False dönün. Eşkenar dörtgen örneğiyle sınayın: A(0, 2), B(4, 0), C(8, 2) ve D(4, 4) → True.

🧰 Motorlarda ve kütüphanelerde

GodotGeometry2D.triangulate_polygon (kulak kesme) · Geometry2D.triangulate_delaunay · Geometry2D.convex_hull2B çokgen ve nokta işlerinin hepsi hazır; navmesh için NavigationServer
JavaScriptdelaunator (Mapbox; çok hızlı Delaunay) · d3-delaunay (Delaunay + Voronoi) · earcut (delikli çokgen üçgenleme)p5.js projelerinde doğrudan kullanılabilir
Pythonscipy.spatial.Delaunay, scipy.spatial.Voronoi · shapely (çokgen işlemleri)Harita üreticisi prototipi için ideal
C++ / UnityCGAL (kapsamlı hesaplamalı geometri) · Unity için açık kaynak Delaunay/Voronoi paketleri · Recast (navmesh)Hazır kütüphane varken kendi Delaunay’ınızı yalnızca öğrenmek için yazın
KırılmaBlender “Cell Fracture”, Houdini Voronoi FractureParçaları önceden kesip oyunda fizik nesnesi olarak kullanmak

Pratik kural: önce hata ayıklama çizimini yapın (üçgenler, çemberler, bölgeler). Bu sunumdaki demoların hepsi ilk gün yalnızca o çizimlerdi.

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin
  • Köşelerin sırası ters: kulak kesme hiç kulak bulamaz.
  • Bowyer–Watson’da yalnızca noktanın içine düştüğü üçgeni bölmek (çember yerine üçgen testi): sonuç Delaunay olmaz.
  • Ortak kenarı yalnızca bir yönde aramak: iç kenarlar oyukta kalır, üçgenler üst üste biner.
  • Dev üçgen yeterince büyük değil: kenardaki üçgenler eksik çıkar.
  • Dört nokta aynı çember üstündeyken eşitlik hatası; ya da üç nokta aynı doğrudayken sıfıra bölme.
  • Voronoi’yi her kare yeniden hesaplamak.
İyi bir istek (prompt) örneği

“p5.js, kütüphane yok. (1) delaunay(noktalar): Bowyer–Watson; dev başlangıç üçgeni; kötü üçgen = çevrel çemberi yeni noktayı (eşitlik hariç) içine alan; oyuk sınırı = tek bir kötü üçgende geçen kenarlar (iki yön de kontrol edilecek). (2) Hata ayıklama çizimi: her üçgenin çevrel çemberi ince çizgiyle. (3) Test: rastgele 200 nokta için hiçbir çemberin içinde nokta kalmadığını sayan bir fonksiyon. (4) Delaunay’dan Voronoi kenarları: komşu üçgenlerin çember merkezlerini birleştir.”

Neden iyi: algoritmanın adı, kenar durumları ve kendini sınayan bir test isteniyor.

💬 Tartışma soruları

Yanınızdakiyle 2 dakika konuşun, sonra sınıfça tartışalım
  1. Bir strateji oyununda ülke sınırlarını Voronoi ile çizdiniz. Oyuncular “sınırlar dümdüz, yapay görünüyor” diyor. Ne yapabilirsiniz? (İpucu: kenarları gürültüyle kıvırmak, nehirleri ve dağları sınır yapmak.)
  2. Zindan üretirken geri eklenen kenar oranı oyunun türüne göre değişmeli mi? Korku oyunu, aksiyon roguelike’ı ve keşif oyunu için ne seçerdiniz?
  3. Lloyd gevşetmesi noktaları “fazla düzgün” yapabilir. Kaç adımda durmalı? Bir harita için “doğal” görünmeyi nasıl ölçersiniz?
  4. Ormana Poisson disk ile ağaç dikerken farklı boylardaki ağaçlar için tek bir r yeter mi? Büyük ağaç ile küçük çalı arasındaki uzaklık ne olmalı?
  5. Bir Voronoi kırılmasında parça sayısı ve dağılımı çarpmanın şiddetine göre nasıl ayarlanmalı? Oyuncu “her cam aynı kırılıyor” derse?

🚀 Proje ve araştırma önerileri

  1. [kolay] Bölge haritası — Örnek sayfadaki kodu genişletin: 30 köy, Voronoi bölgeleri, her bölgeyi köyün rengine boyayın; fareyle tıklanan bölgenin komşularını (Delaunay kenarları) vurgulayın.
  2. [kolay] Orman serpiştirici — Poisson disk ile üç katman: büyük ağaçlar (r = 60), küçük ağaçlar (r = 30, büyüklere 40’tan yakın değil), çalılar. Sonucu tamamen rastgele dağılımla yan yana gösterin.
  3. [orta] Zindan üreticisi — Demodaki beş aşamayı oynanabilir hâle getirin: koridorları A* ile (Y8) engel etrafından çizin, başlangıç ve çıkış odasını en uzak iki oda seçin (BFS), geri ekleme oranı için sürgü.
  4. [orta] Delikli oda üçgenleme — Kulak kesmeyi delikli çokgene genişletin: deliği en yakın dış köşeye bir “köprü” ile bağlayıp tek çokgene çevirin. Ortasında sütun olan bir odayla sınayın.
  5. [zor] Polygonal Map Generation — Amit Patel’in yazısını adım adım uygulayın: Lloyd, Voronoi, kara/deniz, yükseklik, nehirler, biyomlar. Her adımı ayrı bir düğmeyle gösterin.
  6. [araştırma] Kırılma — Bir dikdörtgeni çarpma noktasının çevresinde sıklaşan Voronoi hücrelerine bölün ve parçaları basit bir fizikle (G5) uçurun. Merkez sayısı ve dağılımının görünüşe etkisini karşılaştırın.

Neler öğrendik? 🎒

  • Kulak kesme: dışbükey ve içi boş köşeyi bul, kes, tekrarla. n köşe → n − 2 üçgen. Köşe sırasına dikkat.
  • Delaunay: hiçbir çevrel çemberin içinde başka nokta yok. En dar açıyı en büyük tutar: dolgun üçgenler, mantıklı komşuluk.
  • Bowyer–Watson: dev üçgenle başla; her yeni nokta için çemberi onu içine alan üçgenleri sil, oyuğu yeni noktaya bağla.
  • Voronoi: her yer en yakın merkeze ait. Sınırlar dik açıortaylar, köşeler Delaunay üçgenlerinin çember merkezleri.
  • Düzgün serpiştirme: Lloyd (bölgenin ortasına taşı, tekrarla) ya da Poisson disk (r’den yakın olmasın; ızgarayla hızlı).
  • Zindan: odalar → Delaunay → MST → birkaç kenar geri → koridor.
  • Sonraki: Bölüm 7: oyunlarda yapay zekâ. İlk sunum Hazırlık: vektörler, oyun döngüsü ve karar veren karakterler.

Kaynaklar: videolar 🎬

Polygon Triangulation [1] – Overview of Ear Clipping
Two-Bit Coding Polygon Triangulation [2] – Ear Clipping Implementation in Code
Two-Bit Coding Every Polygon can be Triangulated Into Exactly n-2 Triangles
Think Twice Delaunay Triangulation
SCIco Voronoi Diagrams and Procedural Map Generation
MAN OF EERIE LETTERS Coding Challenge 181: Weighted Voronoi Stippling
The Coding Train Procedural Object Placement (Poisson Disc Sampling)
Sebastian Lague Procedurally Generated 3D Dungeons
Vazgriz

Kaynaklar: yazılar, kütüphaneler ve belgeler 📚

NEXT LEVEL ▶
Oyunlarda Yapay Zekâ: Hazırlık
Bölüm 7 başlıyor: vektörler, oyun döngüsü ve karar veren karakterler
SONRAKİ SUNUM ▶