Geometri Komputasi dengan Python: Dari Teori ke Aplikasi

Ketika orang berpikir geometri komputasi, menurut pengalaman saya, mereka biasanya memikirkan satu dari dua hal:

1. Wow, itu terdengar rumit.
2. Oh ya, lambung cembung.

Dalam posting ini, saya ingin menjelaskan beberapa geometri komputasi, dimulai dengan gambaran singkat tentang subjek sebelum pindah ke beberapa saran praktis berdasarkan pengalaman saya sendiri (lewati dulu jika Anda memiliki pegangan yang baik pada subjek).

Apa semua ribut-ribut tentang?

Sementara algoritma geometri komputasi convex hull biasanya disertakan dalam kursus pengantar algoritma, geometri komputasi adalah subjek yang jauh lebih kaya yang jarang mendapat perhatian yang cukup dari rata-rata pengembang/ilmuwan komputer (kecuali jika Anda membuat game atau semacamnya).

Secara teoritis menarik…

Dari sudut pandang teoretis, pertanyaan dalam geometri komputasi seringkali sangat menarik; jawaban, menarik; dan jalan yang mereka capai, bervariasi. Kualitas-kualitas ini saja membuatnya menjadi bidang yang layak dipelajari, menurut saya.

Misalnya, pertimbangkan Masalah Galeri Seni: Kami memiliki galeri seni dan ingin memasang kamera keamanan untuk menjaga karya seni kami. Namun anggaran kami terbatas, jadi kami ingin menggunakan kamera sesedikit mungkin. Berapa banyak kamera yang kita butuhkan?

Ketika kami menerjemahkan ini ke notasi geometri komputasi, 'denah' galeri hanyalah poligon sederhana. Dan dengan sedikit minyak siku, kita dapat membuktikan bahwa n/3 kamera selalu cukup untuk poligon pada n simpul, tidak peduli seberapa berantakannya itu. Pembuktiannya sendiri menggunakan graf ganda, beberapa teori graf, triangulasi, dan lainnya.

Di sini, kita melihat teknik pembuktian yang cerdas dan hasil yang cukup menarik untuk diapresiasi dengan sendirinya. Tetapi jika relevansi teoretis tidak cukup bagi Anda…

Dan penting dalam praktik

Seperti yang saya sebutkan sebelumnya, pengembangan game sangat bergantung pada penerapan geometri komputasi (misalnya, deteksi tabrakan sering bergantung pada komputasi convex hull dari sekumpulan objek); seperti halnya sistem informasi geografis (SIG), yang digunakan untuk menyimpan dan melakukan perhitungan pada data geografis; dan robotika juga (misalnya, untuk masalah visibilitas dan perencanaan).

Mengapa begitu sulit?

Mari kita ambil masalah geometri komputasi yang cukup sederhana: diberikan titik dan poligon, apakah titik itu terletak di dalam poligon? (Ini disebut masalah titik-dalam-poligon, atau PIP.)

PIP melakukan pekerjaan yang baik untuk menunjukkan mengapa geometri komputasi bisa (menipu) sulit. Bagi mata manusia, ini bukan pertanyaan yang sulit. Kami melihat diagram berikut dan segera jelas bagi kami bahwa intinya ada di poligon:

Bahkan untuk poligon yang relatif rumit, jawabannya tidak luput dari kita selama lebih dari satu atau dua detik. Namun saat kami memasukkan masalah ini ke komputer, komputer mungkin akan melihat hal berikut:

 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)

Apa yang intuitif bagi otak manusia tidak begitu mudah diterjemahkan ke dalam bahasa komputer.

Lebih abstrak (dan mengabaikan kebutuhan untuk merepresentasikan hal-hal ini dalam kode), masalah yang kita lihat dalam disiplin ini sangat sulit untuk ditegaskan ('membuat ketat') dalam algoritma geometri komputasi. Bagaimana kita menggambarkan skenario titik-dalam-poligon tanpa menggunakan bahasa tautologis seperti 'Sebuah titik berada di dalam poligon jika berada di dalam poligon'? Banyak dari sifat-sifat ini sangat mendasar dan sangat mendasar sehingga sulit untuk mendefinisikannya secara konkret.

Sulit, tapi bukan tidak mungkin. Misalnya, Anda dapat memperketat titik-dalam-poligon dengan definisi berikut:

• Suatu titik berada di dalam poligon jika ada sinar tak hingga yang dimulai pada titik tersebut berpotongan dengan jumlah sisi poligon yang ganjil (dikenal sebagai aturan genap-ganjil).
• Sebuah titik berada di dalam poligon jika memiliki bilangan belitan bukan nol (didefinisikan sebagai berapa kali kurva yang mendefinisikan poligon bergerak di sekitar titik).

Kecuali jika Anda memiliki pengalaman dengan geometri komputasi, definisi ini mungkin tidak akan menjadi bagian dari kosakata Anda yang ada. Dan mungkin itulah simbol bagaimana geometri komputasional dapat mendorong Anda untuk berpikir secara berbeda .

Memperkenalkan CCW

Sekarang kita memiliki pemahaman tentang pentingnya dan kesulitan masalah geometri komputasi, saatnya untuk mendapatkan tangan kita basah.

Di tulang punggung subjek adalah operasi primitif menipu kuat: berlawanan arah jarum jam, atau 'CCW' untuk jangka pendek. (Saya akan memperingatkan Anda sekarang: CCW akan muncul lagi dan lagi.)

CCW mengambil tiga titik A, B, dan C sebagai argumen dan bertanya: apakah ketiga titik ini membentuk putaran berlawanan arah jarum jam (vs putaran searah jarum jam)? Dengan kata lain, apakah A -> B -> C merupakan sudut berlawanan arah jarum jam?

Misalnya, titik hijau adalah CCW, sedangkan titik merah tidak:

Mengapa CCW Penting?

CCW memberi kita operasi primitif yang dapat kita bangun. Ini memberi kita tempat untuk mulai memperketat dan memecahkan masalah geometri komputasi.

Untuk memberi Anda gambaran tentang kekuatannya, mari pertimbangkan dua contoh.

Menentukan Konveksitas

Yang pertama: diberi poligon, dapatkah Anda menentukan apakah itu cembung? Kecembungan adalah properti yang tak ternilai: mengetahui bahwa poligon Anda cembung sering kali memungkinkan Anda meningkatkan kinerja berdasarkan urutan besarnya. Sebagai contoh konkret: ada algoritma PIP yang cukup sederhana yang berjalan dalam waktu Log(n) untuk poligon cembung, tetapi gagal untuk banyak poligon cekung.

Secara intuitif, celah ini masuk akal: bentuk cembung 'bagus', sedangkan bentuk cekung bisa memiliki tepi tajam yang menonjol keluar-masuk—mereka hanya tidak mengikuti aturan yang sama.

Algoritma geometri komputasi sederhana (tetapi tidak jelas) untuk menentukan konveksitas adalah dengan memeriksa bahwa setiap triplet dari simpul berurutan adalah CCW. Ini hanya membutuhkan beberapa baris kode geometri Python (dengan asumsi bahwa points diberikan dalam urutan berlawanan arah jarum jam—jika points berada dalam urutan searah jarum jam, Anda ingin semua kembar tiga searah jarum jam):

 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

Coba ini di atas kertas dengan beberapa contoh. Anda bahkan dapat menggunakan hasil ini untuk menentukan konveksitas. (Untuk membuat segalanya lebih intuitif, perhatikan bahwa kurva CCW dari A -> B -> C sesuai dengan sudut kurang dari 180, yang merupakan cara yang diajarkan secara luas untuk mendefinisikan kecembungan.)

Persimpangan Garis

Sebagai contoh kedua, pertimbangkan persimpangan segmen garis, yang juga dapat diselesaikan dengan menggunakan CCW saja:

 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)

Mengapa demikian? Perpotongan ruas garis juga dapat dinyatakan sebagai: diberikan ruas dengan titik ujung A dan B, apakah titik ujung C dan D dari ruas lain terletak pada sisi yang sama dari AB? Dengan kata lain, jika belokan dari A -> B -> C dan A -> B -> D searah, ruas-ruas tersebut tidak dapat berpotongan. Ketika kami menggunakan jenis bahasa ini, menjadi jelas bahwa masalah seperti itu adalah roti dan mentega CCW.

Definisi yang Ketat

Sekarang setelah kita merasakan pentingnya CCW, mari kita lihat bagaimana penghitungannya. Diketahui titik A, B, dan C:

 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)

Untuk memahami dari mana definisi ini berasal, pertimbangkan vektor AB dan BC. Jika kita ambil hasil kali silangnya, AB x BC, ini akan menjadi vektor sepanjang sumbu z. Tapi ke arah mana (yaitu, +z atau -z)? Ternyata, jika produk silangnya positif, belokannya berlawanan arah jarum jam; jika tidak, itu searah jarum jam.

Definisi ini akan tampak tidak intuitif kecuali Anda memiliki pemahaman yang sangat baik tentang aljabar linier, aturan tangan kanan, dll. Tapi itulah mengapa kami memiliki abstraksi—bila Anda memikirkan CCW, pikirkan saja definisi intuitifnya daripada perhitungannya. Nilai akan segera jelas.

Penyelaman Saya Ke Geometri Komputasi dan Pemrograman Menggunakan Python

Selama sebulan terakhir, saya telah bekerja untuk mengimplementasikan beberapa algoritma geometri komputasi dengan Python. Karena saya akan menggambarnya di beberapa bagian berikutnya, saya akan meluangkan waktu sejenak untuk menjelaskan aplikasi geometri komputasi saya, yang dapat ditemukan di GitHub.

Catatan: Pengalaman saya memang terbatas. Karena saya telah mengerjakan hal ini selama berbulan-bulan, bukan bertahun-tahun, ikuti saran saya dengan sebutir garam. Yang mengatakan, saya belajar banyak dalam beberapa bulan itu, jadi saya harap tips ini terbukti bermanfaat.

Algoritma Kirkpatrick

Inti dari pekerjaan saya adalah implementasi Algoritma Kirkpatrick untuk lokasi titik. Pernyataan masalah akan menjadi seperti: diberikan subdivisi planar (sekelompok poligon yang tidak tumpang tindih di pesawat) dan titik P, poligon mana yang berisi P? Pikirkan titik-dalam-poligon pada steroid—alih-alih satu poligon, Anda memiliki satu bidang penuh.

Sebagai kasus penggunaan, pertimbangkan halaman web. Ketika pengguna mengklik mouse, halaman web perlu mencari tahu apa yang diklik pengguna secepat mungkin. Apakah itu Tombol A? Apakah itu Link B? Halaman web terdiri dari poligon yang tidak tumpang tindih, sehingga Algoritma Kirkpatrick akan diposisikan dengan baik untuk membantu.

Meskipun saya tidak akan membahas algoritme secara mendalam, Anda dapat mempelajari lebih lanjut di sini.

Segitiga Batas Minimum

Sebagai subtugas, saya juga menerapkan algoritme O'Rourke untuk menghitung segitiga pembatas/pembatas minimum (yaitu, menemukan segitiga terkecil yang membungkus sekumpulan titik cembung) dalam waktu linier.

Catatan: Menghitung segitiga pembatas minimum tidak membantu atau merusak kinerja asimtotik Algoritma Kirkpatrick karena perhitungan itu sendiri adalah waktu-linear—tetapi berguna untuk tujuan estetika.

Saran Praktis, Aplikasi, dan Kekhawatiran

Bagian sebelumnya berfokus pada mengapa geometri komputasi bisa sulit untuk dipikirkan secara ketat.

Dalam praktiknya, kita harus berurusan dengan sejumlah masalah baru.

Ingat CCW? Sebagai segue yang bagus, mari kita lihat satu lagi kualitas hebatnya: ini melindungi kita dari bahaya kesalahan floating-point.

Kesalahan Floating-Point: Mengapa CCW adalah Raja

Dalam kursus geometri komputasi saya, Bernard Chazelle, seorang profesor terhormat yang menerbitkan lebih banyak makalah daripada yang dapat saya hitung, membuat aturan bahwa kami tidak dapat menyebutkan sudut ketika mencoba menggambarkan suatu algoritme atau solusi.

Mengapa? Sudutnya berantakan. Sudut adalah "kotor". Ketika Anda harus menghitung sudut, Anda perlu membagi, atau menggunakan beberapa pendekatan (apa pun yang melibatkan Pi, misalnya) atau beberapa fungsi trigonometri.

Saat Anda harus menghitung sudut dalam kode , Anda hampir selalu mendekati. Anda akan kehilangan beberapa tingkat presisi floating point kecil—yang penting saat Anda menguji kesetaraan. Anda dapat memecahkan beberapa titik di pesawat melalui dua metode yang berbeda dan, tentu saja, mengharapkan p1.x == p2.x and p1.y == p2.y . Namun, pada kenyataannya, pemeriksaan ini akan sering gagal. Selanjutnya (dan cukup jelas), titik-titik ini kemudian akan memiliki hash yang berbeda.

Lebih buruk lagi, tingkat kesalahan Anda akan meningkat saat perbedaan kecil Anda menyebar melalui perhitungan Anda. (Untuk beberapa contoh yang lebih ilmiah, makalah ini membahas apa yang bisa salah saat menghitung lambung cembung atau triangulasi Delaunay.)

Jadi, apa yang bisa kita lakukan tentang ini?

hampir sama

Bagian dari masalah geometri komputasi Python adalah bahwa kita membutuhkan ketepatan di dunia di mana hal-hal jarang tepat. Ini akan menjadi masalah lebih sering daripada saat menangani sudut. Pertimbangkan hal berikut:

 # 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!

Bahkan, kode ini akan mencetak "Error!" kira-kira 70% dari waktu (secara empiris). Kami dapat mengatasi masalah ini dengan sedikit lebih lunak dengan definisi kesetaraan kami; yaitu, dengan mengorbankan tingkat akurasi.

Salah satu pendekatan yang saya gunakan (dan terlihat di, misalnya, beberapa modul OpenCV) adalah untuk mendefinisikan dua angka sebagai sama jika mereka berbeda hanya dengan beberapa epsilon nilai kecil. Dengan Python, Anda mungkin memiliki:

 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))

Dalam praktiknya, ini sangat membantu. Jarang, jika pernah, Anda akan menghitung dua titik yang berbeda kurang dari 1e-5 yang sebenarnya dimaksudkan sebagai titik yang berbeda. Saya sangat merekomendasikan menerapkan jenis penggantian ini. Metode serupa dapat digunakan untuk garis, misalnya:

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

Solusi yang lebih maju telah diusulkan, tentu saja. Misalnya, aliran pemikiran 'komputasi geometris eksak' (dijelaskan dalam makalah ini) bertujuan agar semua jalur keputusan dalam suatu program hanya bergantung pada tanda beberapa komputasi, daripada nilai numerik eksaknya, menghilangkan banyak kekhawatiran terkait untuk perhitungan floating-point. Pendekatan hampir setara kami hanya menggores permukaan, tetapi seringkali cukup dalam praktiknya.

CCW adalah Raja

Pada tingkat yang lebih tinggi, (bisa dibilang) bermasalah bahwa kami bahkan mendefinisikan solusi kami dalam hal jumlah komputasi yang tepat seperti sudut atau koordinat titik. Daripada mengatasi gejalanya saja (yaitu, menghilangkan kesalahan floating-point dengan almostEqual ), mengapa tidak mengatasi penyebabnya? Solusinya: alih-alih berpikir dari sudut pandang, pikirkan dalam CCW , yang akan membantu menghilangkan masalah yang terkait dengan komputasi floating-point.

Berikut adalah contoh konkretnya: katakanlah Anda memiliki beberapa poligon cembung P , sebuah simpul v , dan beberapa titik u di luar poligon. Bagaimana Anda bisa mengetahui jika garis uv memotong P di atas atau di bawah v , atau tidak sama sekali, dalam waktu yang tetap?

Solusi brute force (selain waktu linier, bukan konstan) akan bermasalah karena Anda harus menghitung beberapa titik persimpangan garis yang tepat.

Satu pendekatan waktu-konstan yang pernah saya lihat melibatkan:

• Menghitung beberapa sudut menggunakan arctan2 .
• Mengubah sudut-sudut ini menjadi derajat dengan mengalikannya dengan 180/Pi.
• Meneliti hubungan antara berbagai sudut ini.

Untungnya, penulis menggunakan teknik almostEqual di atas untuk menghaluskan kesalahan floating-point.

Menurut pendapat saya, akan lebih baik untuk menghindari masalah kesalahan floating-point sepenuhnya. Jika Anda meluangkan beberapa menit untuk melihat masalah di atas kertas, Anda bisa mendapatkan solusi yang sepenuhnya didasarkan pada CCW. Intuisi: jika simpul yang berdekatan dengan v berada di sisi yang sama dari uv , maka garis tidak berpotongan; jika tidak, lihat apakah u dan v berada pada sisi yang sama dari garis antara simpul yang berdekatan dan, bergantung pada hasilnya, bandingkan ketinggiannya.

Berikut kode Python untuk menguji persimpangan di atas v (persimpangan di bawah hanya membalikkan arah perbandingan):

 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

Solusinya tidak langsung terlihat dengan mata telanjang, tetapi dalam bahasa algoritme geometri komputasional: 'sisi garis yang sama' adalah elemen klasik dari algoritme tepercaya itu.

Selesai Lebih Baik dari Sempurna

Dalam literatur geometri komputasi, seringkali ada cukup banyak sihir yang terlibat dalam operasi yang tampaknya sederhana. Ini memberi Anda pilihan: Anda dapat melakukan hal-hal dengan cara yang sulit, mengikuti beberapa makalah yang mendefinisikan solusi yang sangat canggih untuk masalah yang tidak terlalu canggih—atau Anda dapat melakukan hal-hal dengan cara yang mudah dengan sedikit kekerasan.

Sekali lagi, saya akan menggunakan contoh: mengambil sampel titik interior acak dari poligon arbitrer. Dengan kata lain, saya memberi Anda beberapa poligon sederhana, dan Anda memberi saya titik acak di dalamnya (terdistribusi merata di seluruh poligon).

Seringkali, poin interior diperlukan untuk pengujian. Dalam hal ini, Anda tidak memiliki persyaratan runtime khusus pada algoritme geometri komputasi yang menghasilkannya (dengan alasan). Solusi cepat dan kotor, yang membutuhkan waktu ~2 menit untuk diterapkan, adalah dengan memilih titik acak di dalam kotak yang berisi poligon dan melihat apakah titik itu sendiri berada di dalam poligon.

Misalnya, kami mungkin melewatkan dua kali dan menemukan sampel yang valid hanya pada poin ketiga:

Berikut kodenya:

 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

Ini dikenal sebagai pengambilan sampel penolakan : ambil poin acak sampai salah satu memenuhi kriteria Anda. Meskipun mungkin memerlukan beberapa sampel untuk menemukan titik yang memenuhi kriteria Anda, dalam praktiknya, perbedaannya dapat diabaikan untuk rangkaian pengujian Anda. Jadi mengapa bekerja lebih keras? Ringkasnya: jangan takut untuk mengambil jalan kotor ketika ada kesempatan.

Omong-omong: jika Anda menginginkan algoritme yang tepat untuk pengambilan sampel acak, ada yang pintar di sini yang telah saya terapkan di bawah ini. Intinya:

1. Triangulasi poligon Anda (yaitu, pecah menjadi segitiga).
2. Pilih segitiga dengan probabilitas sebanding dengan luasnya.
3. Ambil titik acak dari dalam segitiga yang dipilih (operasi waktu konstan).

Perhatikan bahwa algoritme ini mengharuskan Anda untuk melakukan triangulasi poligon Anda, yang segera memberlakukan runtime yang berbeda terikat pada algoritme, serta kebutuhan bahwa Anda memiliki perpustakaan untuk melakukan triangulasi poligon arbitrer (saya menggunakan poly2tri dengan binding Python).

 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()

Mudah-mudahan, upaya ekstra terbukti dari kode. Ingat: seperti yang mereka katakan di Facebook, "selesai lebih baik dari sempurna". Hal yang sama berlaku untuk masalah geometri komputasi.

Pengujian Visual dan Otomatis

Karena banyak masalah yang Anda kerjakan dalam geometri komputasi didefinisikan dalam hal kualitas atau kuantitas yang mudah divisualisasikan, pengujian visual sangat penting — meskipun tidak cukup dengan sendirinya. Rangkaian pengujian yang ideal akan memiliki kombinasi pengujian otomatis visual dan acak.

Sekali lagi, kami melanjutkan dengan contoh. Pertimbangkan untuk menguji implementasi Algoritma Kirkpatrick kami. Pada satu langkah, algoritme perlu mengikat poligon yang diberikan dengan segitiga dan membuat segitiga daerah antara poligon dan segitiga luar. Berikut adalah contoh visual, di mana garis hijau solid mendefinisikan poligon awal, dan garis putus-putus mendefinisikan wilayah segitiga:

Mengkonfirmasi bahwa triangulasi ini telah dieksekusi dengan benar sangat sulit untuk diverifikasi melalui kode, tetapi langsung terlihat oleh mata manusia. Catatan: Saya sangat menyarankan menggunakan Matplotlib untuk membantu pengujian visual Anda—ada panduan yang bagus di sini.

Kemudian, kami ingin memverifikasi bahwa algoritme menempatkan titik dengan benar. Pendekatan otomatis dan acak akan menghasilkan sekelompok titik interior untuk setiap poligon dan memastikan bahwa kita mengembalikan poligon yang diinginkan. Dalam kode:

 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))

Kami kemudian dapat menggunakan metode runLocator pada set poligon yang berbeda, memberi kami rangkaian pengujian yang terdiversifikasi dengan baik.

Solusi Sumber Terbuka

Geometri komputasional memiliki rangkaian pustaka sumber terbuka yang bagus dan solusi yang tersedia terlepas dari bahasa pemrograman pilihan Anda (walaupun pustaka C++ tampaknya menghasilkan jumlah yang tidak proporsional).

Manfaat menggunakan solusi sumber terbuka yang ada (seperti halnya komputasi ilmiah dengan Python) sudah terkenal dan telah dibahas secara luas, jadi saya tidak akan membahasnya di sini. Tapi saya pikir saya akan menyebutkan beberapa sumber daya Python-centric yang menurut saya berguna:

• poly2tri: perpustakaan besar untuk triangulasi cepat poligon. Juga mendukung (dan ini sering penting) poligon dengan lubang di dalamnya. Ditulis dalam C++, poly2tri juga memiliki binding Python dan cukup mudah untuk dijalankan. Lihat metode triangulate saya di atas untuk merasakan panggilan fungsi.
• scipy.spatial: termasuk fungsi untuk menghitung convex hulls, Delaunay Triangulations, dan banyak lagi. Cepat (seperti biasa), andal, dll. Catatan: Saya merasa berguna untuk menggunakan tipe data Point saya sendiri dengan metode toNumpy : def np(self): return [self.x, self.y] . Kemudian, saya dapat dengan mudah memanggil metode scipy.spatial, misalnya: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV: perpustakaan visi komputer sumber terbuka memiliki beberapa modul geometri komputasi mandiri yang bagus. Secara khusus, saya menggunakan fungsi segitiga penutup minimum untuk sementara waktu sebelum menerapkannya sendiri.

Kesimpulan

Saya harap posting ini memberi Anda rasa akan keindahan geometri komputasi sebagai pengembang Python, subjek yang kaya dengan masalah yang menarik dan aplikasi yang sama-sama menarik.

Dalam praktiknya, implementasi geometri komputasional menghadirkan tantangan unik yang akan mendorong Anda untuk melatih keterampilan pemecahan masalah yang baru dan menarik.

Jika Anda tertarik untuk mempelajari lebih lanjut atau memiliki pertanyaan untuk saya, saya dapat dihubungi di [email protected].