Çokgen üçgenleme - Polygon triangulation

çokgen üçgenleme

Olarak hesaplama geometri , poligon nirengi bir ayrışmasıdır çokgen alanı ( basit bir çokgen ) P bir dizi içine üçgenler çiftli kesişmeyen iç ile üçgen bir kümesini bulma, yani kaynama olan p .

Üçgenlemeler, düzlemsel düz çizgi grafiklerinin özel durumları olarak görülebilir . Delik veya eklenen nokta olmadığında, üçgenler maksimum dış düzlem grafikleri oluşturur .

Ekstra köşeler olmadan çokgen üçgenleme

Zamanla, bir çokgeni üçgenlemek için bir dizi algoritma önerilmiştir.

Özel durumlar

Bir dışbükey yedigen (7 kenarlı dışbükey çokgen) için 42 olası üçgenleme . Bu sayı 5. Katalan numarası ile verilmektedir .

Herhangi bir üçgen için önemsiz olan dışbükey çokgen olarak lineer zaman bir içine fan nirengi diğer köşe bir tepe noktasından köşegenleri ekleyerek.

Bir dışbükey n -gon'u kesişmeyen köşegenlerle üçgenlemenin toplam yolu , ( n −2)nd Katalan sayısıdır , bu sayıya eşittir.

{\frac {n(n+1)...(2n-4)}{(n-2)!}}

,

Leonhard Euler tarafından bulunan bir formül .

Bir monoton çokgen algoritması ile ya lineer zamanda üçgen olabilir A. Fournier ve DY Montuno veya algoritması Godfried Toussaint .

Kulak kırpma yöntemi

çokgen kulak

Basit bir çokgeni üçgenlemenin bir yolu, iki kulak teoremine dayanır , çünkü deliksiz en az 4 köşesi olan herhangi bir basit çokgenin en az iki ' kulağı ' vardır; bunlar, iki kenarı çokgenin kenarları olan üçgenlerdir ve üçüncüsü tamamen onun içinde. Algoritma daha sonra böyle bir kulak bulmaktan, onu çokgenden çıkarmaktan (bu, koşulları karşılayan yeni bir çokgenle sonuçlanır) ve yalnızca bir üçgen kalana kadar tekrar etmekten oluşur.

Bu algoritmanın uygulanması kolaydır, ancak diğer bazı algoritmalardan daha yavaştır ve yalnızca deliksiz çokgenler üzerinde çalışır. Dışbükey ve içbükey köşelerin ayrı listelerini tutan bir uygulama $O(n 2)$ zamanında çalışacaktır . Bu yöntem kulak kesme ve bazen kulak kesme olarak bilinir . Hossam ElGindy, Hazel Everett ve Godfried Toussaint , kulakları kesmek için etkili bir algoritma keşfetti .

Monoton çokgen üçgenleme

Bir çokgeni monoton çokgenlere bölme

Basit bir çokgen, $L$ çizgisine göre monotondur , eğer $L'ye$ dik herhangi bir çizgi çokgenle en fazla iki kez kesişirse. Monoton bir çokgen iki monoton zincire bölünebilir . Y eksenine göre monoton olan bir çokgene y-monoton denir . $n$ köşesi olan monoton bir çokgen $O(n)$ zamanında üçgenlenebilir. Belirli bir çokgenin y-monoton olduğunu varsayarsak, açgözlü algoritma , çokgenin bir zincirinde yukarıdan aşağıya doğru yürüyerek ve mümkün olduğunda köşegenler ekleyerek başlar. Algoritmanın herhangi bir monoton çokgene uygulanabileceğini görmek kolaydır.

Monoton olmayan bir çokgeni üçgenleme

Bir çokgen monoton değilse, bir tarama çizgisi yaklaşımı kullanılarak $O(n log n)$ zamanında monoton alt poligonlara bölünebilir . Algoritma çokgenin basit olmasını gerektirmez, bu nedenle delikli çokgenlere uygulanabilir. Genel olarak, bu algoritma bir düzlemsel alt bölümü üçgen olabilir $, n$ bir köşe $O ($ $n$ $log$ $n$ $)$ defasında $O ($ $n$ $)$ alanı.

Bir üçgenlemenin ikili grafiği

Genellikle bir çokgen $P'nin$ üçgenlenmesiyle ilişkilendirilen kullanışlı bir grafik , ikili grafiktir . Bir nirengi verilen $T P$ arasında $P$ , bir tanımlar grafik $G (T P)$ tepe seti üçgenler grafik olarak $T P$ bir çapraz paylaşan bitişik, ancak ve ancak olmak üzere iki köşe (üçgenler). Gözlemlemek kolaydır $G (T P)$ a, ağaç maksimum derecede 3 ile uyarılmıştır.

hesaplama karmaşıklığı

1988 yılına kadar basit bir çokgenin $O(n log n)$ zamanından daha hızlı üçgenlenip açılamayacağı, hesaplamalı geometride açık bir problemdi. Daha sonra, Tarjan ve Van Wyk (1988) , daha sonra Kirkpatrick, Klawe & Tarjan (1992) tarafından basitleştirilmiş, üçgenleme için bir $O(n log log n)$ -zaman algoritması keşfetti . Bunu $O($ $n$ $log$ $*$ $n$ $)$ karmaşıklığına sahip birkaç geliştirilmiş yöntem (pratikte, doğrusal zamandan ayırt edilemez ) izledi.

Bernard Chazelle 1991'de önerilen algoritma çok karmaşık olmasına rağmen herhangi bir basit çokgenin doğrusal zamanda üçgenlenebileceğini gösterdi. Doğrusal beklenen zamana sahip daha basit bir rastgele algoritma da bilinmektedir.

Seidel'in ayrıştırma algoritması ve Chazelle'in üçgenleme yöntemi Li & Klette (2011)' de detaylı olarak tartışılmıştır .

Zaman karmaşıklığı bir nirengi arasında $N$ -vertex çokgen olan deliklerin bir sahiptir $(w n log n)$ bağlı düşük cebirsel olarak, hesaplama ağaç hesaplama modelleri. Dinamik programlama kullanarak polinom zamanında basit bir çokgenin farklı nirengilerinin sayısını hesaplamak ve (bu sayma algoritmasına dayanarak) polinom zamanında tek tip rastgele nirengiler oluşturmak mümkündür . Bununla birlikte, delikli bir çokgenin üçgenlemelerini saymak #P- tamamlıdır, bu da polinom zamanında yapılması pek olası değildir.

İlgili nesneler ve sorunlar

Her iki üçgenleme problemi de üçgenlemenin (geometri) özel bir durumu ve çokgen bölmenin özel bir durumudur .
Minimum ağırlıklı üçgenleme , amacın toplam kenar uzunluğunu en aza indirmek olduğu bir üçgenlemedir.
Bir noktadan grubu nirengi noktaları kümesi konveks gövdenin bir poligon nirengi olup. Bir Delaunay üçgenlemesi , bir dizi noktaya dayalı bir üçgenleme oluşturmanın başka bir yoludur.
Associahedron olan noktaların bir konveks çokgen nirengi tekabül politop olup.
Üçgenlerin üst üste gelebileceği çokgen üçgen kaplama .
Hedefin tüm düzlemi önceden belirlenmiş şekillerdeki çokgenlerle kaplamak olduğu çokgenlerle döşeme .

Ayrıca bakınız

Referanslar

Dış bağlantılar

Flash swf , A Sweep Line algoritması olarak demo .
Song Ho'nun OpenGL GLU mozaikleyici açıklaması

Languages

In other projects