Python'da Hesaplamalı Geometri: Teoriden Uygulamaya

İnsanlar hesaplamalı geometriyi düşündüklerinde, deneyimlerime göre, genellikle iki şeyden birini düşünürler:

1. Kulağa karmaşık geliyor.
2. Ah evet, dışbükey gövde.

Bu yazıda, kendi deneyimlerime dayanan bazı pratik tavsiyelere geçmeden önce konuya kısa bir genel bakışla başlayarak, hesaplamalı geometriye biraz ışık tutmak istiyorum (konu hakkında iyi bir fikriniz varsa, devam edin).

Bütün bu yaygara ne hakkında?

Dışbükey gövde hesaplamalı geometri algoritmaları tipik olarak bir algoritmaya giriş kursuna dahil edilirken, hesaplamalı geometri çok daha zengin bir konudur ve ortalama geliştirici/bilgisayar bilimcisinden nadiren yeterli ilgi görür (oyun veya başka bir şey yapmıyorsanız).

Teorik olarak ilgi çekici…

Teorik bir bakış açısından, hesaplamalı geometrideki sorular genellikle fazlasıyla ilginçtir; cevaplar, zorlayıcı; ve ulaştıkları yollar çeşitlendi. Bu nitelikler tek başına, bence, onu çalışmaya değer bir alan haline getiriyor.

Örneğin, Sanat Galerisi Problemini ele alalım: Bir sanat galerimiz var ve sanat eserimizi korumak için güvenlik kameraları kurmak istiyoruz. Ancak kısıtlı bir bütçemiz var, bu yüzden mümkün olduğunca az kamera kullanmak istiyoruz. Kaç kameraya ihtiyacımız var?

Bunu hesaplamalı geometrik gösterime çevirdiğimizde, galerinin 'kat planı' sadece basit bir çokgendir. Ve biraz dirsek gresi ile, ne kadar dağınık olursa olsun, n köşedeki bir çokgen için n/3 kameranın her zaman yeterli olduğunu kanıtlayabiliriz. Kanıtın kendisi ikili grafikler, bazı grafik teorisi, üçgenlemeler ve daha fazlasını kullanır.

Burada akıllıca bir ispat tekniği ve başlı başına takdir edilecek kadar merak uyandıran bir sonuç görüyoruz. Ancak teorik alaka düzeyi sizin için yeterli değilse…

Ve önemli uygulama

Daha önce bahsettiğim gibi, oyun geliştirme büyük ölçüde hesaplamalı geometrinin uygulanmasına dayanır (örneğin, çarpışma tespiti genellikle bir dizi nesnenin dışbükey gövdesinin hesaplanmasına dayanır); coğrafi verileri depolamak ve hesaplamak için kullanılan coğrafi bilgi sistemleri (CBS) gibi; ve robotik de (örneğin, görünürlük ve planlama sorunları için).

Neden bu kadar zor?

Oldukça basit bir hesaplamalı geometri problemini ele alalım: bir nokta ve bir çokgen verildiğinde, nokta çokgenin içinde midir? (Buna poligon içinde nokta veya PIP sorunu denir.)

PIP, hesaplama geometrisinin neden (aldatıcı bir şekilde) zor olabileceğini göstermek için harika bir iş çıkarıyor. İnsan gözü için bu zor bir soru değil. Aşağıdaki diyagramı görüyoruz ve noktanın çokgende olduğu hemen anlaşılıyor:

Nispeten karmaşık çokgenler için bile, cevap bir veya iki saniyeden fazla gözümüzden kaçmaz. Ancak bu sorunu bir bilgisayara beslediğimizde aşağıdakileri görebilir:

 poly = Polygon([Point(0, 5), Point(1, 1), Point(3, 0), Point(7, 2), Point(7, 6), Point(2, 7)]) point = Point(5.5, 2.5) poly.contains(point)

İnsan beyni için sezgisel olan şey, bilgisayar diline o kadar kolay çevrilmez.

Daha soyut olarak (ve bunları kodda temsil etme ihtiyacını göz ardı ederek), bu disiplinde gördüğümüz problemlerin bir hesaplamalı geometri algoritmasında kesinleştirilmesi ('kesin hale getirilmesi') çok zordur. Çokgen içinde nokta senaryosunu, 'Bir nokta çokgenin içindeyse çokgenin içindedir' gibi totolojik bir dil kullanmadan nasıl tanımlarız? Bu özelliklerin birçoğu o kadar temel ve o kadar temeldir ki, bunları somut olarak tanımlamak zordur.

Zor ama imkansız değil. Örneğin, poligondaki noktayı aşağıdaki tanımlarla kesinleştirebilirsiniz:

• Noktadan başlayan herhangi bir sonsuz ışın tek sayıda çokgen kenarıyla kesişiyorsa (çift-tek kuralı olarak bilinir) bir nokta çokgenin içindedir.
• Bir nokta, sıfır olmayan bir sarma numarasına sahipse (çokgeni tanımlayan eğrinin nokta etrafında dolaşma sayısı olarak tanımlanır) çokgenin içindedir.

Hesaplamalı geometri ile biraz deneyiminiz olmadıkça, bu tanımlar muhtemelen mevcut kelime dağarcığınızın bir parçası olmayacaktır. Ve belki de bu, hesaplamalı geometrinin sizi nasıl farklı düşünmeye itebileceğinin simgesidir.

CCW ile tanışın

Artık hesaplamalı geometri problemlerinin önemini ve zorluğunu anladığımıza göre, ellerimizi ıslatmanın zamanı geldi.

Konunun omurgasında aldatıcı derecede güçlü bir ilkel işlem var: saat yönünün tersine veya kısaca 'CCW'. (Sizi şimdi uyaracağım: CCW tekrar tekrar açılacaktır.)

CCW, A, B ve C noktalarını argüman olarak alır ve sorar: Bu üç nokta saat yönünün tersine bir dönüş mü oluşturuyor (saat yönünde bir dönüşe karşı)? Başka bir deyişle, A -> B -> C saat yönünün tersine bir açı mı?

Örneğin, yeşil noktalar CCW'dir, kırmızı noktalar ise:

CCW Neden Önemlidir?

CCW bize üzerine inşa edebileceğimiz ilkel bir işlem sunar. Bize hesaplamalı geometri problemlerini titizleştirmeye ve çözmeye başlamak için bir yer verir.

Gücünü anlamanız için iki örneği ele alalım.

Dışbükeyliğin Belirlenmesi

Birincisi: Bir çokgen verildiğinde, dışbükey olup olmadığını belirleyebilir misiniz? Dışbükeylik paha biçilmez bir özelliktir: Çokgenlerinizin dışbükey olduğunu bilmek, genellikle performansınızı büyüklük sıralarına göre artırmanıza olanak tanır. Somut bir örnek olarak: dışbükey çokgenler için Log(n) zamanında çalışan, ancak birçok içbükey çokgen için başarısız olan oldukça basit bir PIP algoritması vardır.

Sezgisel olarak, bu boşluk mantıklıdır: dışbükey şekiller 'güzel' iken, içbükey şekiller içeri ve dışarı çıkıntı yapan keskin kenarlara sahip olabilir - sadece aynı kurallara uymazlar.

Dışbükeyliği belirlemek için basit (ancak açık olmayan) bir hesaplamalı geometri algoritması, ardışık köşelerin her üçlüsünün CCW olduğunu kontrol etmektir. Bu, sadece birkaç satır Python geometri kodu alır ( points saat yönünün tersine verildiğini varsayarsak - points saat yönündeyse, tüm üçlülerin saat yönünde olmasını istersiniz):

 class Polygon(object): ... def isConvex(self): for i in range(self.n): # Check every triplet of points A = self.points[i % self.n] B = self.points[(i + 1) % self.n] C = self.points[(i + 2) % self.n] if not ccw(A, B, C): return False return True

Bunu birkaç örnekle kağıt üzerinde deneyin. Bu sonucu dışbükeyliği tanımlamak için bile kullanabilirsiniz. (İşleri daha sezgisel hale getirmek için, A -> B -> C'den bir CCW eğrisinin, dışbükeyliği tanımlamanın yaygın olarak öğretilen bir yolu olan 180'den küçük bir açıya karşılık geldiğini unutmayın.)

Hat Kavşağı

İkinci bir örnek olarak, yalnızca CCW kullanılarak da çözülebilen çizgi parçası kesişimini düşünün:

 def intersect(a1, b1, a2, b2): """Returns True if line segments a1b1 and a2b2 intersect.""" return ccw(a1, b1, a2) != ccw(a1, b1, b2) and ccw(a2, b2, a1) != ccw(a2, b2, b1)

Bu neden böyle? Doğru parçası kesişimi şu şekilde de ifade edilebilir: A ve B uç noktalarına sahip bir doğru parçası verildiğinde, başka bir parçanın C ve D uç noktaları AB'nin aynı tarafında mı? Başka bir deyişle, A -> B -> C ve A -> B -> D'den gelen dönüşler aynı yöndeyse, segmentler kesişemez. Bu tür bir dili kullandığımızda, böyle bir sorunun CCW'nin ekmek ve tereyağı olduğu ortaya çıkıyor.

Titiz Bir Tanım

Artık CCW'nin önemini anladığımıza göre, nasıl hesaplandığına bir bakalım. Verilen A, B ve C noktaları:

 def ccw(A, B, C): """Tests whether the turn formed by A, B, and C is ccw""" return (Bx - Ax) * (Cy - Ay) > (By - Ay) * (Cx - Ax)

Bu tanımın nereden geldiğini anlamak için AB ve BC vektörlerini göz önünde bulundurun. Çapraz çarpımlarını alırsak, AB x BC, bu z ekseni boyunca bir vektör olacaktır. Ama hangi yönde (yani, +z veya -z)? Görünüşe göre, çapraz çarpım pozitifse, dönüş saat yönünün tersinedir; aksi halde saat yönündedir.

Doğrusal cebir, sağ el kuralı vb. hakkında gerçekten iyi bir anlayışa sahip değilseniz, bu tanım sezgisel görünmeyecektir. Ama işte bu yüzden soyutlamaya sahibiz - CCW'yi düşündüğünüzde, hesaplamadan ziyade sezgisel tanımını düşünün. Değer hemen temizlenecektir.

Python Kullanarak Hesaplamalı Geometri ve Programlamaya Dalışım

Geçen ay Python'da birkaç hesaplamalı geometri algoritması uygulamak için çalışıyorum. Önümüzdeki birkaç bölüm boyunca üzerlerinde çizim yapacağım için, GitHub'da bulunabilecek hesaplamalı geometri uygulamalarımı açıklamak için biraz zaman ayıracağım.

Not: Deneyimim kuşkusuz sınırlıdır. Bu konu üzerinde yıllardır değil aylardır çalıştığım için tavsiyeme birazcık kulak verin. Bununla birlikte, o birkaç ayda çok şey öğrendim, umarım bu ipuçları faydalı olur.

Kirkpatrick Algoritması

Çalışmamın merkezinde, nokta konumu için Kirkpatrick Algoritmasının bir uygulaması vardı. Problem ifadesi şuna benzer olacaktır: düzlemsel bir alt bölüm (düzlemde örtüşmeyen bir grup çokgen) ve bir P noktası verildiğinde, hangi çokgen P içerir? Steroidler üzerinde çokgen nokta düşünün - tek bir çokgen yerine, onlardan bir uçak dolusu var.

Kullanım durumu olarak, bir web sayfası düşünün. Bir kullanıcı fareye tıkladığında, web sayfasının kullanıcının neyi tıkladığını olabildiğince çabuk bulması gerekir. Düğme A mıydı? B Bağlantısı mıydı? Web sayfası örtüşmeyen çokgenlerden oluşur, bu nedenle Kirkpatrick'in Algoritması yardımcı olmak için iyi bir konumda olacaktır.

Algoritmayı derinlemesine tartışmayacak olsam da, buradan daha fazlasını öğrenebilirsiniz.

Minimum Sınır Üçgeni

Bir alt görev olarak, O'Rourke'nin doğrusal zamanda minimum çevreleyen/sınırlayıcı üçgeni (yani, dışbükey bir noktayı çevreleyen en küçük üçgeni bulmak) hesaplamak için algoritmasını da uyguladım.

Not: Minimum sınırlayıcı üçgeni hesaplamak, Kirkpatrick Algoritmasının asimptotik performansına yardımcı olmaz veya zarar vermez, çünkü hesaplamanın kendisi doğrusal-zamandır - ancak estetik amaçlar için faydalıdır.

Pratik Tavsiyeler, Uygulamalar ve Endişeler

Önceki bölümler, hesaplama geometrisinin neden titiz bir şekilde akıl yürütmenin zor olabileceğine odaklandı.

Uygulamada, yepyeni bir dizi endişeyle uğraşmak zorundayız.

CCW'yi hatırlıyor musun? Güzel bir segue olarak, harika özelliklerinden bir tanesine daha bakalım: bizi kayan nokta hatalarının tehlikelerine karşı korur.

Kayan Nokta Hataları: CCW Neden Kraldır?

Hesaplamalı geometri dersimde, sayamayacağım kadar çok makale yayınlayan saygın bir profesör olan Bernard Chazelle, bir algoritmayı veya bir çözümü tanımlamaya çalışırken açılardan bahsedemeyeceğimizi bir kural haline getirdi.

Niye ya? Köşeler dağınık. Açılar “kirli”. Bir açıyı hesaplamanız gerektiğinde, bölmeniz veya bazı yaklaşımlar (örneğin Pi içeren herhangi bir şey) veya bazı trigonometrik işlevler kullanmanız gerekir.

Kodda bir açıyı hesaplamanız gerektiğinde, neredeyse her zaman yaklaşık olacaksınız. Küçük bir kayan nokta kesinliği derecesinden uzaklaşacaksınız - bu, eşitliği test ederken önemlidir. Düzlemdeki bir noktayı iki farklı yöntemle p1.x == p2.x and p1.y == p2.y bekleyebilirsiniz. Ancak gerçekte, bu kontrol sıklıkla başarısız olur. Ayrıca (ve oldukça açık bir şekilde), bu noktaların farklı karmaları olacaktır.

Daha da kötüsü, küçük farklarınız hesaplamalarınız boyunca yayıldıkça hata dereceniz artacaktır. (Bazı daha bilimsel örnekler için, bu makale dışbükey gövde veya Delaunay üçgenlemesi hesaplanırken neyin yanlış gidebileceğini anlatıyor.)

Peki, bu konuda ne yapabiliriz?

neredeyse eşit

Python hesaplamalı geometri probleminin bir kısmı, şeylerin nadiren kesin olduğu bir dünyada kesinliğe ihtiyaç duymamızdır. Bu, açıları kullanırken olduğundan daha sık bir sorun haline gelecektir. Aşağıdakileri göz önünde bulundur:

 # Define two random points p1 = RandomPoint() p2 = RandomPoint() # Take the line through them l1 = Line(p1, p2) # Shift both points up by sqrt(2) p1.y += sqrt(2) p2.y += sqrt(2) l2 = Line(p1, p2) # Slope 'should' be the same? if abs(l1.slope - l2.slope) > 0: print "Error!" # Error!

Aslında, bu kod “Hata!” Yazacaktır. kabaca zamanın %70'i (ampirik olarak). Eşitlik tanımımızda biraz daha hoşgörülü davranarak bu endişeyi giderebiliriz; yani, bir doğruluk derecesinden ödün vererek.

Kullandığım (ve örneğin bazı OpenCV modüllerinde gördüğüm) bir yaklaşım, yalnızca küçük bir epsilon değeriyle farklılık gösteren iki sayıyı eşit olarak tanımlamaktır. Python'da şunlara sahip olabilirsiniz:

 def almostEqual(x, y, EPSILON=1e-5): return abs(x - y) < EPSILON class Point(object): ... def __eq__(self, that): return (almostEqual(self.x, that.x) and almostEqual(self.y, that.y))

Uygulamada, bu çok yardımcı olur. Nadiren, eğer öyleyse, gerçekte farklı noktalar olması gereken 1e-5'ten daha az farklılık gösteren iki nokta hesaplar mıydınız? Bu tür bir geçersiz kılma uygulamanızı şiddetle tavsiye ederim. Çizgiler için benzer yöntemler kullanılabilir, örneğin:

 class Line(object): ... def __eq__(self, that): return (almostEqual(self.slope, that.slope) and almostEqual(self.intercept, that.intercept))

Elbette daha gelişmiş çözümler önerildi. Örneğin, 'tam geometrik hesaplama' düşünce okulu (bu yazıda açıklanan), bir programdaki tüm karar yollarının, ilgili endişelerin çoğunu ortadan kaldırarak, kesin sayısal değerinden ziyade yalnızca bazı hesaplamaların işaretine bağlı olmasını amaçlar. kayan noktalı hesaplamalara Neredeyse eşitliğe yaklaşımımız sadece yüzeyi çiziyor, ancak pratikte çoğu zaman yeterli olacaktır.

CCW Kraldır

Daha yüksek bir düzeyde, çözümlerimizi açılar veya nokta koordinatları gibi kesin hesaplama miktarları cinsinden tanımlamamız bile (tartışmalı) sorunludur. Semptomları tek başına ele almak yerine (yani, neredeyseEqual ile kayan nokta hatalarını almostEqual ), neden nedeni ele almıyorsunuz? Çözüm: açılar açısından düşünmek yerine, kayan nokta hesaplamasıyla ilgili endişeleri soyutlamaya yardımcı olacak CCW açısından düşünün .

İşte somut bir örnek: Diyelim ki bir dışbükey çokgen P , bir köşe v ve poligonun dışında bir nokta u var. uv doğrusunun, sabit zamanda, v'nin üstünde veya altında P ile kesişip kesişmediğini veya hiç kesişmediğini nasıl anlayabilirsiniz?

Kaba kuvvet çözümü (sabit değil, doğrusal zaman olmasının yanı sıra), bazı kesin çizgi kesişme noktalarını hesaplamanız gerekeceğinden sorunlu olacaktır.

Gördüğüm bir sabit zamanlı yaklaşım şunları içerir:

• arctan2 kullanarak bazı açıları hesaplama.
• Bu açıları 180/Pi ile çarparak dereceye çevirmek.
• Bu çeşitli açılar arasındaki ilişkilerin incelenmesi.

Neyse ki, yazar kayan nokta hatalarını düzeltmek için yukarıdaki almostEqual tekniğini kullandı.

Bence kayan nokta hatalarından tamamen kaçınmak daha iyi olur. Soruna kağıt üzerinde bakmak için birkaç dakikanızı ayırırsanız, tamamen CCW'ye dayalı bir çözüm elde edebilirsiniz. Sezgi: v'ye bitişik köşeler uv'nin aynı tarafındaysa, çizgi kesişmez; yoksa, u ve v'nin bitişik köşeler arasındaki çizginin aynı tarafında olup olmadığına bakın ve sonuca bağlı olarak yüksekliklerini karşılaştırın.

İşte v üzerindeki kesişimi test etmek için Python kodu (aşağıdaki kesişme sadece karşılaştırmaların yönünü tersine çevirir):

 def intersectsAbove(verts, v, u): """ Returns True if uv intersects the polygon defined by 'verts' above v. Assumes v is the index of a vertex in 'verts', and u is outside of the polygon. """ n = len(verts) # Test if two adjacent vertices are on same side of line (implies # tangency) if ccw(u, verts[v], verts[(v - 1) % n]) == ccw(u, verts[v], verts[(v + 1) % n]): return False # Test if u and v are on same side of line from adjacent # vertices if ccw(verts[(v - 1) % n], verts[(v + 1) % n], u) == ccw(verts[(v - 1) % n], verts[(v + 1) % n], verts[v]): return uy > verts[v].y else: return uy < verts[v].y

Çözüm, çıplak gözle hemen açık değildir, ancak bir hesaplamalı geometri algoritmasının dilindedir : 'çizginin aynı tarafı', bu güvenilir algoritmanın klasik bir öğesidir.

Mükemmel olacağına tamamlanmış olsun

Hesaplamalı geometrik literatürde, görünüşte basit işlemlerle ilgili genellikle makul miktarda sihirbazlık vardır. Bu size bir seçenek sunar: o kadar da gelişmiş olmayan bir soruna inanılmaz derecede gelişmiş bir çözüm tanımlayan bazı makaleleri izleyerek işleri zor yoldan yapabilirsiniz ya da biraz kaba kuvvetle işleri kolay yoldan yapabilirsiniz.

Yine bir örnek kullanacağım: rastgele bir çokgenden rastgele bir iç nokta örnekleme. Başka bir deyişle, ben size basit bir çokgen veriyorum ve siz bana onun içinde rastgele bir nokta veriyorsunuz (çokgen boyunca düzgün bir şekilde dağılmış).

Çoğu zaman, test için iç noktalar gereklidir. Bu durumda, bunları üreten hesaplamalı geometri algoritması üzerinde (sebep dahilinde) herhangi bir özel çalışma zamanı gereksiniminiz yoktur. Uygulanması ~2 dakika süren hızlı ve kirli çözüm, poligonu içeren bir kutu içinde rastgele bir nokta seçmek ve noktanın kendisinin çokgenin içinde olup olmadığına bakmak olacaktır.

Örneğin, iki kez ıskalayabilir ve yalnızca üçüncü noktada geçerli bir örnek bulabiliriz:

İşte kod:

 class Polygon(object): ... def interiorPoint(self): """Returns a random point interior point""" min_x = min([px for p in self.points]) max_x = max([px for p in self.points]) min_y = min([py for p in self.points]) max_y = max([py for p in self.points]) def x(): return min_x + random() * (max_x - min_x) def y(): return min_y + random() * (max_y - min_y) p = Point(x(), y()) while not self.contains(p): p = Point(x(), y()) return p def contains(self, p): for i in range(self.n): p1 = self.points[i] p2 = self.points[(i + 1) % self.n] p3 = self.points[(i + 2) % self.n] if not ccw(p1, p2, p3): return False return True

Bu, reddetme örneklemesi olarak bilinir: Kriterlerinizi karşılayana kadar rastgele puanlar alın. Kriterlerinizi karşılayan bir noktayı bulmak için birkaç örnek gerektirebilirken, pratikte fark, test takımınız için önemsiz olacaktır . Öyleyse neden daha fazla çalışayım? Özetle: Durum gerektirdiğinde kirli rotayı kullanmaktan korkmayın.

Bu arada: rastgele örnekleme için kesin bir algoritma istiyorsanız, aşağıda uyguladığım akıllıca bir algoritma var. İşin özü:

1. Çokgeninizi üçgenleyin (yani üçgenlere bölün).
2. Alanıyla orantılı olasılığı olan bir üçgen seçin.
3. Seçilen üçgenin içinden rastgele bir nokta alın (sabit zamanlı bir işlem).

Bu algoritmanın, algoritmaya hemen farklı bir çalışma zamanı sınırı uygulayan poligonunuzu üçgenlemenizi gerektirdiğini ve ayrıca isteğe bağlı çokgenleri üçgenlemek için bir kitaplığınızın olması gerekliliğini unutmayın (Python bağlamaları ile poly2tri kullandım).

 from p2t import CDT class Triangle(object): ... def area(self): return abs((Bx * Ay - Ax * By) + (Cx * By - Bx * Cy) + (Ax * Cy - Cx * Ay)) / 2 def interiorPoint(self): r1 = random() r2 = random() # From http://www.cs.princeton.edu/~funk/tog02.pdf return (1 - sqrt(r1)) * A + sqrt(r1) * (1 - r2) * B + r2 * sqrt(r1) * C class Polygon(object): ... def triangulate(self): # Triangulate poly with hole cdt = CDT(poly.points) triangles = cdt.triangulate() def convert(t): A = Point(tax, tay) B = Point(tbx, tby) C = Point(tcx, tcy) return Triangle(A, B, C) return map(convert, triangles) def interiorPoint(self): # Triangulate polygon triangles = self.triangulate() areas = [t.area() for t in triangles] total = sum(areas) # Calculate normalized areas probabilities = [area / total for area in areas] weighted_triangles = zip(triangles, probabilities) # Sample triangles according to area r = random() count = 0 for (triangle, prob) in weighted_triangles: count += prob # Take random point from chosen triangle if count > r: return triangle.interiorPoint()

Umarım, ekstra çaba koddan açıktır. Unutmayın: Facebook'ta dedikleri gibi, "Yapılanlar mükemmelden daha iyidir". Aynı şey hesaplamalı geometri problemleri için de geçerlidir.

Görsel ve Otomatik Test

Hesaplamalı geometride üzerinde çalıştığınız problemlerin çoğu kolayca görselleştirilebilir nitelikler veya nicelikler olarak tanımlandığından, görsel testler tek başına yetersiz olsa da özellikle önemlidir. İdeal test paketi, görsel ve rastgele otomatik testlerin bir kombinasyonuna sahip olacaktır.

Yine örnek üzerinden ilerliyoruz. Kirkpatrick Algoritması uygulamamızı test etmeyi düşünün. Bir adımda, algoritmanın verilen çokgeni bir üçgenle sınırlandırması ve çokgen ile dış üçgen arasındaki bölgeyi üçgenlemesi gerekir. İşte, düz yeşil çizginin ilk çokgeni ve kesik çizgilerin üçgen bölgeyi tanımladığı görsel bir örnek:

Bu üçgenlemenin doğru bir şekilde yürütüldüğünü doğrulamak, kod aracılığıyla doğrulamak çok zordur, ancak insan gözüyle hemen görülür. Not: Görsel testinize yardımcı olması için Matplotlib'i kullanmanızı şiddetle tavsiye ederim - burada güzel bir rehber var.

Daha sonra, algoritmanın noktaları doğru bir şekilde yerleştirdiğini doğrulamak isteyeceğiz. Rastgele, otomatik bir yaklaşım, her çokgen için bir grup iç nokta oluşturmak ve istenen çokgeni döndürdüğümüzden emin olmak olacaktır. Kodda:

 class TestLocator(unittest.TestCase): ... def runLocator(self, polygons): # Pre-process regions l = Locator(polygons) # Ensure correctness for polygon in polygons: # Test 100 random interior points per region for k in range(100): target = polygon.interiorPoint() target_polygon = l.locate(target) self.assertEqual(polygon, target_polygon) self.assertTrue(target_polygon.contains(target))

Daha sonra farklı çokgen kümelerinde runLocator yöntemini kullanabiliriz, bu da bize iyi çeşitlendirilmiş bir test takımı verir.

Açık Kaynak Çözümleri

Hesaplamalı geometri, seçtiğiniz programlama dili ne olursa olsun, güzel bir açık kaynaklı kitaplık ve çözümler paketine sahiptir (C++ kitaplıkları orantısız bir miktarda kırpılmış gibi görünse de).

Mevcut açık kaynak çözümlerini kullanmanın faydaları (Python'daki bilimsel hesaplamada olduğu gibi) iyi bilinmektedir ve kapsamlı bir şekilde tartışılmıştır, bu yüzden burada devam etmeyeceğim. Ancak faydalı bulduğum birkaç Python merkezli kaynaktan bahsetmeyi düşündüm:

• poly2tri: Çokgenlerin hızlı nirengileri için harika bir kitaplık. Ayrıca, içlerinde delik bulunan çokgenleri de destekler (ve bu genellikle çok önemlidir). C++ ile yazılmış poly2tri, Python bağlamalarına da sahiptir ve çalıştırması oldukça kolaydı. İşlev çağrılarının tadına bakmak için yukarıdaki triangulate yöntemime bakın.
• scipy.spatial: dışbükey gövdeleri, Delaunay Üçgenlerini ve daha fazlasını hesaplamaya yönelik işlevleri içerir. Hızlı (her zamanki gibi), güvenilir vb. Not: Kendi Point veri toNumpy yöntemiyle kullanmayı faydalı buldum: def np(self): return [self.x, self.y] . Ardından, scipy.spatial yöntemlerini kolayca çağırabilirim, örneğin: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV: açık kaynaklı bilgisayarlı görü kitaplığı, bazı güzel bağımsız hesaplamalı geometri modüllerine sahiptir. Özellikle, minimum çevreleyen üçgen işlevini kendim uygulamadan önce bir süre kullandım.

Çözüm

Umarım bu yazı, büyüleyici problemler ve aynı derecede büyüleyici uygulamalarla zengin bir konu olan bir Python geliştiricisi olarak hesaplamalı geometrinin güzelliğinin tadına varmanızı sağlamıştır.

Pratikte, hesaplamalı geometrik uygulamalar, sizi yeni ve heyecan verici problem çözme becerileri geliştirmeye itecek benzersiz zorluklar sunar.

Daha fazla bilgi edinmekle ilgileniyorsanız veya benim için herhangi bir sorunuz varsa, [email protected] adresinden bana ulaşabilirsiniz.