Geometrie computațională în Python: de la teorie la aplicare

Când oamenii se gândesc la geometria computațională, din experiența mea, ei gândesc de obicei unul dintre două lucruri:

1. Wow, asta sună complicat.
2. Da, carcasă convexă.

În această postare, aș dori să arunc puțină lumină asupra geometriei computaționale, pornind cu o scurtă prezentare generală a subiectului înainte de a trece la câteva sfaturi practice bazate pe propriile mele experiențe (sări înainte dacă te pricepi bine la subiect).

Despre ce e toată agitația?

În timp ce algoritmii de geometrie computațională cu carcasă convexă sunt de obicei incluși într-un curs introductiv de algoritmi, geometria computațională este un subiect mult mai bogat, care rareori primește suficientă atenție din partea dezvoltatorului/informaticianului obișnuit (cu excepția cazului în care faci jocuri sau așa ceva).

Teoretic intrigant...

Din punct de vedere teoretic, întrebările din geometria computațională sunt adesea extrem de interesante; răspunsurile, convingătoare; iar căile prin care se ajunge la ei, variate. Numai aceste calități îl fac un domeniu care merită studiat, după părerea mea.

De exemplu, luați în considerare problema galeriei de artă: deținem o galerie de artă și dorim să instalăm camere de securitate pentru a ne păzi opera de artă. Dar avem un buget restrâns, așa că vrem să folosim cât mai puține camere posibil. De câte camere avem nevoie?

Când traducem acest lucru în notație geometrică computațională, „planul de etaj” al galeriei este doar un simplu poligon. Și cu puțină grăsime, putem demonstra că n/3 camere sunt întotdeauna suficiente pentru un poligon pe n vârfuri, indiferent cât de dezordonat ar fi. Dovada în sine folosește grafice duale, unele teorii ale graficelor, triangulații și multe altele.

Aici, vedem o tehnică inteligentă de probă și un rezultat suficient de curios pentru a fi apreciat de la sine. Dar dacă relevanța teoretică nu este suficientă pentru tine...

Și important în practică

După cum am menționat mai devreme, dezvoltarea jocului se bazează în mare măsură pe aplicarea geometriei computaționale (de exemplu, detectarea coliziunilor se bazează adesea pe calcularea carcasei convexe a unui set de obiecte); la fel ca și sistemele de informații geografice (GIS), care sunt utilizate pentru stocarea și efectuarea de calcule pe date geografice; și robotică, de asemenea (de exemplu, pentru probleme de vizibilitate și planificare).

De ce este atât de dur?

Să luăm o problemă de geometrie computațională destul de simplă: având în vedere un punct și un poligon, punctul se află în interiorul poligonului? (Aceasta se numește problema punct-în-poligon sau PIP.)

PIP face o treabă grozavă de a demonstra de ce geometria computațională poate fi (înșelător) dură. Pentru ochiul uman, aceasta nu este o întrebare dificilă. Vedem următoarea diagramă și ne este imediat evident că punctul se află în poligon:

Chiar și pentru poligoane relativ complicate, răspunsul nu ne scapă mai mult de o secundă sau două. Dar când transmitem această problemă la un computer, este posibil să vadă următoarele:

 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)

Ceea ce este intuitiv pentru creierul uman nu se traduce atât de ușor în limbajul computerului.

Mai abstract (și ignorând necesitatea de a reprezenta aceste lucruri în cod), problemele pe care le vedem în această disciplină sunt foarte greu de riguros („a face riguros”) într-un algoritm de geometrie computațională. Cum am descrie scenariul punct-în-poligon fără a folosi un limbaj tautologic precum „Un punct este în interiorul unui poligon dacă este în interiorul poligonului”? Multe dintre aceste proprietăți sunt atât de fundamentale și atât de elementare încât este dificil să le definim concret.

Greu, dar nu imposibil. De exemplu, ați putea rigori punctul-în-poligon cu următoarele definiții:

• Un punct se află în interiorul unui poligon dacă orice rază infinită care începe în punct se intersectează cu un număr impar de muchii de poligon (cunoscută sub numele de regula par-impar).
• Un punct este în interiorul unui poligon dacă are un număr de înfășurare diferit de zero (definit ca numărul de ori în care curba care definește poligonul se deplasează în jurul punctului).

Dacă nu ai avut ceva experiență cu geometria computațională, probabil că aceste definiții nu vor face parte din vocabularul tău existent. Și poate că acesta este emblematic pentru modul în care geometria computațională vă poate împinge să gândiți diferit .

Vă prezentăm CCW

Acum că avem o idee despre importanța și dificultatea problemelor de geometrie computațională, este timpul să ne udăm mâinile.

La coloana vertebrală a subiectului se află o operație primitivă înșelător de puternică: în sens invers acelor de ceasornic, sau pe scurt „CCW”. (O să vă avertizez acum: CCW va apărea din nou și din nou.)

CCW ia trei puncte A, B și C drept argumente și întreabă: aceste trei puncte compun o rotație în sens invers acelor de ceasornic (vs. o rotație în sensul acelor de ceasornic)? Cu alte cuvinte, este A -> B -> C un unghi în sens invers acelor de ceasornic?

De exemplu, punctele verzi sunt CCW, în timp ce punctele roșii nu sunt:

De ce contează CCW

CCW ne oferă o operație primitivă pe care ne putem construi. Ne oferă un loc pentru a începe rigoarea și rezolvarea problemelor de geometrie computațională.

Pentru a vă da un simț al puterii sale, să luăm în considerare două exemple.

Determinarea convexității

Primul: dat fiind un poligon, poți determina dacă este convex? Convexitatea este o proprietate de neprețuit: știind că poligoanele dvs. sunt convexe, vă permite adesea să îmbunătățiți performanța cu ordine de mărime. Ca exemplu concret: există un algoritm PIP destul de simplu care rulează în timp Log(n) pentru poligoane convexe, dar nu reușește pentru multe poligoane concave.

Intuitiv, acest decalaj are sens: formele convexe sunt „drăguțe”, în timp ce formele concave pot avea margini ascuțite ieșind în interior și în afară – pur și simplu nu urmează aceleași reguli.

Un algoritm de geometrie computațională simplu (dar neevident) pentru determinarea convexității este de a verifica dacă fiecare triplet de vârfuri consecutive este CCW. Aceasta necesită doar câteva linii de cod de geometrie Python (presupunând că points sunt furnizate în sens invers acelor de ceasornic - dacă points sunt în ordinea acelor de ceasornic, veți dori ca toate tripletele să fie în sensul acelor de ceasornic):

 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

Încercați acest lucru pe hârtie cu câteva exemple. Puteți chiar folosi acest rezultat pentru a defini convexitatea. (Pentru a face lucrurile mai intuitive, rețineți că o curbă CCW de la A -> B -> C corespunde unui unghi mai mic de 180, care este un mod larg predat de a defini convexitatea.)

Intersecția liniei

Ca un al doilea exemplu, luați în considerare intersecția segmentului de linie, care poate fi rezolvată și folosind numai CCW:

 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)

De ce este acesta cazul? Intersecția segmentului de linie poate fi formulată și astfel: dat un segment cu punctele de capăt A și B, punctele de capăt C și D ale unui alt segment se află pe aceeași parte a lui AB? Cu alte cuvinte, dacă turele de la A -> B -> C și A -> B -> D sunt în aceeași direcție, segmentele nu se pot intersecta. Când folosim acest tip de limbaj, devine clar că o astfel de problemă este pâinea și untul CCW.

O definiție riguroasă

Acum că avem un gust pentru importanța CCW, să vedem cum este calculată. Datele punctele A, B și 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)

Pentru a înțelege de unde vine această definiție, luați în considerare vectorii AB și BC. Dacă luăm produsul lor încrucișat, AB x BC, acesta va fi un vector de-a lungul axei z. Dar în ce direcție (adică +z sau -z)? După cum se dovedește, dacă produsul încrucișat este pozitiv, întoarcerea este în sens invers acelor de ceasornic; altfel, este in sensul acelor de ceasornic.

Această definiție va părea neintuitivă, cu excepția cazului în care aveți o înțelegere foarte bună a algebrei liniare, a regulii mâinii drepte etc. Dar de aceea avem abstractizare - când vă gândiți CCW, gândiți-vă la definiția intuitivă, mai degrabă decât la calculul său. Valoarea va fi imediat clară.

Scufundarea mea în geometria computațională și programarea folosind Python

În ultima lună, am lucrat la implementarea mai multor algoritmi de geometrie computațională în Python. Pe măsură ce voi folosi ele în următoarele câteva secțiuni, voi lua o secundă pentru a descrie aplicațiile mele de geometrie computațională, care pot fi găsite pe GitHub.

Notă: Experiența mea este, desigur, limitată. Deoarece lucrez la aceste lucruri de luni de zile, mai degrabă decât de ani, luați-mi sfatul cu puțină sare. Acestea fiind spuse, am învățat multe în acele câteva luni, așa că sper că aceste sfaturi se vor dovedi utile.

Algoritmul lui Kirkpatrick

În centrul muncii mele a fost o implementare a algoritmului lui Kirkpatrick pentru localizarea punctelor. Enunțul problemei ar fi ceva de genul: având în vedere o subdiviziune plană (o grămadă de poligoane care nu se suprapun în plan) și un punct P, care poligon conține P? Gândiți-vă la un punct în poligon pe steroizi - în loc de un singur poligon, aveți un plan plin de ei.

Ca caz de utilizare, luați în considerare o pagină web. Când un utilizator dă clic pe mouse, pagina web trebuie să-și dea seama cât mai repede posibil pe ce a făcut clic utilizatorul. A fost butonul A? A fost Link B? Pagina web este compusă din poligoane care nu se suprapun, astfel încât algoritmul lui Kirkpatrick ar fi bine poziționat pentru a ajuta.

Deși nu voi discuta în profunzime despre algoritm, puteți afla mai multe aici.

Triunghi limită minim

Ca o sarcină secundară, am implementat, de asemenea, algoritmul lui O'Rourke pentru a calcula un triunghi minim de încadrare/delimitare (adică găsirea celui mai mic triunghi care înglobează un set de puncte convexe) în timp liniar.

Notă: Calcularea triunghiului de mărginire minimă nu ajută și nu dăunează performanței asimptotice a algoritmului lui Kirkpatrick, deoarece calculul în sine este în timp liniar, dar este util în scopuri estetice.

Sfaturi practice, aplicații și preocupări

Secțiunile anterioare s-au concentrat pe motivul pentru care geometria computațională poate fi dificil de raționat riguros.

În practică, trebuie să ne confruntăm cu o serie complet nouă de preocupări.

Îți amintești CCW? Ca o continuare frumoasă, să vedem încă una dintre marile sale calități: ne protejează împotriva pericolelor erorilor în virgulă mobilă.

Erori în virgulă mobilă: de ce CCW este regele

În cursul meu de geometrie computațională, Bernard Chazelle, un stimabil profesor care a publicat mai multe lucrări decât pot număra eu, a făcut o regulă că nu putem menționa unghiurile atunci când încercăm să descriem un algoritm sau o soluție.

De ce? Unghiurile sunt dezordonate. Unghiurile sunt „murdare”. Când trebuie să calculați un unghi, trebuie să împărțiți sau să utilizați o aproximare (orice ce implică Pi, de exemplu) sau o funcție trigonometrică.

Când trebuie să calculați un unghi în cod , aproape întotdeauna veți aproxima. Veți avea un grad mic de precizie în virgulă mobilă, ceea ce contează atunci când testați egalitatea. Puteți rezolva pentru un anumit punct din plan prin două metode diferite și, desigur, vă așteptați ca p1.x == p2.x and p1.y == p2.y . Dar, în realitate, această verificare va eșua adesea . În plus (și destul de evident), aceste puncte vor avea apoi hashuri diferite.

Pentru a înrăutăți lucrurile, gradul de eroare va crește pe măsură ce micile tale diferențe se propagă prin calculele tale. (Pentru câteva exemple mai științifice, această lucrare analizează ce poate merge prost atunci când se calculează corpul convex sau triangulația Delaunay.)

Deci, ce putem face în privința asta?

aproape Egale

O parte din problema geometriei computaționale Python este că avem nevoie de exactitate într-o lume în care lucrurile sunt rareori exacte. Aceasta va deveni o problemă mai des decât la manipularea unghiurilor. Luați în considerare următoarele:

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

De fapt, acest cod va tipări „Eroare!” aproximativ 70% din timp (empiric). Putem aborda această preocupare fiind puțin mai îngăduitori cu definiția noastră a egalității; adică prin sacrificarea unui grad de precizie.

O abordare pe care am folosit-o (și am văzut-o, de exemplu, în unele module OpenCV) este de a defini două numere ca fiind egale dacă diferă doar printr-o valoare mică de epsilon. În Python, este posibil să aveți:

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

În practică, acest lucru este foarte util. Rareori, sau vreodată, ați calcula două puncte care diferă cu mai puțin de 1e-5 care sunt de fapt menite să fie puncte diferite. Recomand cu caldura implementarea acestui tip de override. Metode similare pot fi utilizate pentru linii, de exemplu:

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

S-au propus, desigur, soluții mai avansate. De exemplu, școala de gândire „calcul geometric exact” (descrisă în această lucrare) își propune ca toate căile de decizie dintr-un program să depindă doar de semnul unor calcule, mai degrabă decât de valoarea sa numerică exactă, eliminând multe dintre preocupările legate de la calcule în virgulă mobilă. Abordarea noastră aproape de egalitate doar zgârie suprafața, dar va fi adesea suficientă în practică.

CCW este regele

La un nivel superior, este (probabil) problematic să ne definim chiar și soluțiile în termeni de mărimi exacte de calcul precum unghiurile sau coordonatele punctului. În loc să abordăm singur simptomele (adică, spălarea erorilor în virgulă mobilă cu almostEqual ), de ce să nu abordăm cauza? Soluția: în loc să gândiți în termeni de unghiuri, gândiți-vă în termeni CCW , ceea ce va ajuta la îndepărtarea preocupărilor asociate cu calculul în virgulă mobilă.

Iată un exemplu concret: să presupunem că aveți un poligon convex P , un vârf v și un punct u în afara poligonului. Cum vă puteți da seama dacă linia uv intersectează P deasupra sau sub v , sau deloc, în timp constant?

Soluția de forță brută (pe lângă faptul că este liniară în timp, mai degrabă decât constantă) ar fi problematică, deoarece ar trebui să calculați niște puncte exacte de intersecție a liniilor.

O abordare constantă pe care am văzut-o implică:

• Calcularea unor unghiuri folosind arctan2 .
• Conversia acestor unghiuri în grade prin înmulțirea cu 180/Pi.
• Examinând relațiile dintre aceste diferite unghiuri.

Din fericire, autorul a folosit tehnica almostEqual de mai sus pentru a netezi erorile în virgulă mobilă.

În opinia mea, ar fi mai bine să evităm în întregime problema erorilor în virgulă mobilă. Dacă vă acordați câteva minute pentru a examina problema pe hârtie, puteți obține o soluție bazată în întregime pe CCW. Intuiția: dacă vârfurile adiacente v sunt de aceeași parte a uv , atunci linia nu se intersectează; altfel, vedeți dacă u și v sunt de aceeași parte a liniei dintre vârfurile adiacente și, în funcție de rezultat, comparați înălțimile lor.

Iată codul Python pentru testarea intersecției de deasupra v (intersecția de mai jos doar inversează direcția comparațiilor):

 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

Soluția nu este imediat evidentă cu ochiul liber, dar este în limbajul unui algoritm de geometrie computațională: „aceeași parte a liniei” este un element clasic al acelui algoritm de încredere.

Terminat este mai bine decât perfect

În literatura geometrică computațională, există adesea o cantitate destul de mare de vrăjitorie implicată în operațiuni aparent simple. Acest lucru vă oferă o alegere: puteți face lucrurile pe calea grea, urmând o lucrare care definește o soluție incredibil de avansată pentru o problemă nu atât de avansată - sau puteți face lucrurile pe cale ușoară, cu puțină forță brută.

Din nou, voi folosi un exemplu: eșantionarea unui punct interior aleatoriu dintr-un poligon arbitrar. Cu alte cuvinte, vă dau un poligon simplu și îmi oferiți un punct aleatoriu în interiorul acestuia (distribuit uniform pe poligon).

Adesea, punctele interioare sunt necesare pentru testare. În acest caz, nu aveți cerințe specifice de rulare pentru algoritmul de geometrie computațională care le produce (în limita rațiunii). Soluția rapidă și murdară, care durează aproximativ 2 minute pentru a fi implementată, ar fi să alegeți un punct aleatoriu într-o cutie care conține poligonul și să vedeți dacă punctul însuși se află în poligon.

De exemplu, putem rata de două ori și găsim un eșantion valid doar la al treilea punct:

Iată codul:

 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

Acest lucru este cunoscut sub numele de eșantionare de respingere : luați puncte aleatoriu până când unul vă satisface criteriile. Deși poate fi nevoie de mai multe mostre pentru a găsi un punct care îndeplinește criteriile dvs., în practică, diferența va fi neglijabilă pentru suita dvs. de teste. Deci de ce să muncești mai mult? Pe scurt: nu-ți fie teamă să iei drumul murdar atunci când ocazie o cere.

Apropo: dacă doriți un algoritm exact pentru eșantionarea aleatorie, există unul inteligent aici pe care l-am implementat mai jos. Esenta acesteia:

1. Triangulați-vă poligonul (adică, împărțiți-l în triunghiuri).
2. Alegeți un triunghi cu probabilitate proporțională cu aria lui.
3. Luați un punct aleatoriu din triunghiul ales (o operație în timp constant).

Rețineți că acest algoritm vă cere să triangulați poligonul, ceea ce impune imediat un alt timp de rulare legat de algoritm, precum și necesitatea de a avea o bibliotecă pentru triangularea poligoanelor arbitrare (am folosit poly2tri cu legături 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()

Sperăm că efortul suplimentar este evident din cod. Amintiți-vă: așa cum se spune la Facebook, „finit este mai bine decât perfect”. Același lucru este valabil și pentru problemele de geometrie computațională.

Testare vizuală și automată

Deoarece multe dintre problemele la care lucrați în geometria computațională sunt definite în termeni de calități sau cantități ușor de vizualizat, testarea vizuală este deosebit de importantă, deși insuficientă în sine. Suita de teste ideală va avea o combinație de testare automată vizuală și randomizată.

Din nou, procedăm prin exemplu. Luați în considerare testarea implementării noastre a algoritmului lui Kirkpatrick. La un pas, algoritmul trebuie să limiteze poligonul dat de un triunghi și să triunghiuleze regiunea dintre poligon și triunghiul exterior. Iată un exemplu vizual, în care linia verde continuă definește poligonul inițial, iar liniile întrerupte definesc regiunea triangulată:

Confirmarea că această triangulare a fost executată corect este foarte dificil de verificat prin cod, dar este imediat evidentă pentru ochiul uman. Notă: vă sugerez cu căldură să utilizați Matplotlib pentru a vă ajuta la testarea vizuală - există un ghid frumos aici.

Mai târziu, vom dori să verificăm dacă algoritmul localizează corect punctele. O abordare randomizată, automată, ar fi să generezi o grămadă de puncte interioare pentru fiecare poligon și să ne asigurăm că returnăm poligonul dorit. În cod:

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

Am putea apoi folosi metoda runLocator pe diferite seturi de poligoane, oferindu-ne o suită de teste bine diversificată.

Soluții open-source

Geometria computațională are o suită frumoasă de biblioteci și soluții open-source disponibile, indiferent de limbajul de programare ales (deși bibliotecile C++ par să apară o cantitate disproporționată).

Beneficiile utilizării soluțiilor open-source existente (ca și în cazul calculului științific în Python) sunt binecunoscute și au fost discutate pe larg, așa că nu voi continua aici. Dar m-am gândit să menționez câteva resurse centrate pe Python pe care le-am găsit utile:

• poly2tri: o bibliotecă excelentă pentru triangularea rapidă a poligoanelor. De asemenea, susține (și acest lucru este adesea crucial) poligoane cu găuri în ele. Scris în C++, poly2tri are, de asemenea, legături Python și a fost destul de ușor de pus în funcțiune. A se vedea metoda mea triangulate de mai sus pentru un gust pentru apelurile de funcție.
• scipy.spatial: include funcții pentru calcularea carcaselor convexe, triangulațiilor Delaunay și multe altele. Rapid (ca întotdeauna), de încredere etc. Notă: Mi s-a părut util să folosesc propriul meu tip de date Point cu o metodă toNumpy : def np(self): return [self.x, self.y] . Apoi, aș putea apela cu ușurință metode scipy.spatial, de exemplu: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV: biblioteca open-source de viziune pe computer are câteva module de geometrie computațională de sine stătătoare. În special, am folosit funcția de triunghi de închidere minimă pentru o perioadă înainte de a o implementa eu.

Concluzie

Sper că această postare v-a dat un gust pentru frumusețea geometriei computaționale ca dezvoltator Python, un subiect bogat cu probleme fascinante și aplicații la fel de fascinante.

În practică, implementările geometrice computaționale prezintă provocări unice care vă vor împinge să vă exercitați abilități noi și interesante de rezolvare a problemelor.

Dacă sunteți interesat să aflați mai multe sau aveți întrebări pentru mine, pot fi contactat la [email protected].