Kui inimesed arvavad arvutusgeomeetriat, siis minu kogemuse kohaselt mõtlevad nad tavaliselt ühte kahest asjast:

1. Vot, see kõlab keeruliselt.
2. Oh jah kumer kere .

Selles postituses tahaksin valgustada arvutuslikku geomeetriat, alustades lühikesest ülevaatest teemast, enne kui asun oma kogemustele tuginevate praktiliste nõuannete juurde ( jäta vahele kui teil on sellel teemal hea käepide).

tutvumissaidid kasutajate arvu järgi

Milles see kära on?

Kui kumer kere arvutusgeomeetria algoritmid on tavaliselt lisatud algoritmide sissejuhatav kursus , arvutusgeomeetria on palju rikkam teema, millele keskmine arendaja / arvutiteadlane harva piisavalt tähelepanu pöörab (kui te just mänge ei tee).

Teoreetiliselt intrigeeriv…

Teoreetiliselt on arvutusgeomeetria küsimused sageli ülimalt huvitavad; vastused, veenvad; ja teed, kuhu nad on jõudnud, olid erinevad. Ainuüksi need omadused muudavad selle minu meelest õppimist väärivaks alaks.

Näiteks kaaluge Kunstigalerii probleem : Meil ​​on kunstigalerii ja soovime oma kunstiteoste valvamiseks paigaldada turvakaamerad. Kuid meil on kitsas eelarve, seega tahame kasutada võimalikult vähe kaameraid. Mitu kaamerat vajame?

Kui tõlgime selle arvutuslikuks geomeetriliseks tähistuseks, on galerii ‘korruseplaan’ lihtsalt lihtne hulknurk. Ja mõne küünarnuki määrdega saame seda tõestada n / 3 kaameratest piisab alati polügooni sisselülitamiseks n tipud, ükskõik kui segane see ka pole. The tõestus ise kasutab topeltgraafikuid, mõnda graafiteooriat, triangulatsioone ja palju muud.

Siin näeme nutikat tõestustehnikat ja tulemust, mis on piisavalt uudishimulik, et seda saaks iseseisvalt hinnata. Kuid kui teoreetiline asjakohasus pole teie jaoks piisav ...

Ja praktikas oluline

Nagu ma varem mainisin, sõltub mängude arendamine suuresti arvutusliku geomeetria rakendamisest (näiteks kokkupõrke tuvastamine tugineb sageli objektide komplekti kumera kere arvutamisele); nagu ka geograafilised infosüsteemid (GIS) , mida kasutatakse geograafiliste andmete arvutuste salvestamiseks ja teostamiseks; ja ka robootika (nt nähtavuse ja planeerimisprobleemide jaoks).

Miks see nii karm on?

Võtame üsna sirgjoonelise arvutusgeomeetria ülesande: kui punkt ja hulknurk on antud, siis kas punkt asub polügooni sees? (Seda nimetatakse punkt-polügoon või PIP-probleem .)

PIP teeb suurepärast tööd, näidates, miks arvutusgeomeetria võib olla (petlikult) karm. Inimesele pole see keeruline küsimus. Näeme järgmist skeemi ja ongi kohe meile ilmselge, et punkt on hulknurgas:

Isegi suhteliselt keerukate hulknurkade puhul ei välista vastus meid rohkem kui sekund või kaks. Kuid kui edastame selle probleemi arvutisse, võib see näha järgmist:

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)

See, mis on inimese aju jaoks intuitiivne, ei tõlgi nii lihtsalt arvutikeelde.

Abstraktsemalt (ja ignoreerides vajadust neid asju koodis esindada) on probleeme, mida selles distsipliinis näeme, arvutusliku geomeetria algoritmis väga raske täpsustada (‘muuta rangeks’). Kuidas kirjeldaksime punkt-polügoonis stsenaariumi, kasutamata sellist tautoloogilist keelt nagu ‘Punkt on hulknurga sees, kui see on polügooni sees’? Paljud neist omadustest on nii fundamentaalsed ja nii põhilised, et neid on raske konkreetselt määratleda.

Kuidas kirjeldaksime punkt-polügoonis stsenaariumi, ilma et kasutaksime sellist tautoloogilist keelt nagu 'see on polügooni sees, kui see on polügooni sees'?

Raske, kuid mitte võimatu. Näiteks võite täpsustada polügooni punktides järgmiste määratlustega:

• Punkt on hulknurga sees, kui mis tahes punktist algav lõpmatu kiir ristub paaritu arvuga hulknurga servadega (tuntud kui paaris-paaritu reegel ).
• Punkt on hulknurga sees, kui sellel on nullist erinev mähisnumber (määratletud kui mitu korda hulknurka määrav kõver liigub ümber punkti).

Kui teil pole arvutusgeomeetriaga kogemusi, ei kuulu need määratlused tõenäoliselt teie olemasoleva sõnavara juurde. Ja võib-olla on see sümboolne, kuidas arvutusgeomeetria võib teid tõugata mõtle teisiti .

CCW tutvustamine

Nüüd, kui oleme mõistnud arvutusliku geomeetria probleemide olulisust ja raskusi, on aeg käed märjaks teha.

Objekti selgrool on petlikult võimas primitiivne operatsioon: vastupäeva või lühidalt ‘CCW’. (Hoiatan teid nüüd: CCW ilmub ikka ja jälle.)

CCW võtab argumendina kolm punkti A, B ja C ning küsib: kas need kolm punkti moodustavad vastupäeva (võrreldes päripäeva)? Teisisõnu, kas A -> B -> C on vastupäeva?

Näiteks roheline punktid on CCW, samas kui võrk punktid ei ole:

Miks CCW loeb

CCW annab meile a ürgne operatsiooni, millele saame üles ehitada. See annab meile koha, kus alustada arvutusliku geomeetria ülesannete täpsustamist ja lahendamist.

Mõelgem kahe näite kohta, et mõista selle võimsust.

Kumeruse määramine

Esimene: antud hulknurk, kas saate kindlaks teha, kas see on kumer? Kumerus on hindamatu omadus: teadmine, et teie hulknurgad on kumerad, võimaldab teil jõudlust sageli suurendada suurusjärkude võrra. Konkreetse näitena: siin on a üsna sirgjooneline PIP-algoritm mis kulgeb kumerate hulknurkade log (n) ajas, kuid paljude nõgusate hulknurkade korral ebaõnnestub.

Intuitiivselt on see vahe mõttekas: kumerad kujundid on ‘kenad’, samas kui nõgusatel kujunditel võivad teravad servad sisse ja välja sirguda - need ei järgi lihtsalt samu reegleid.

Kumeruse määramiseks on lihtne (kuid mitte ilmne) arvutusgeomeetria algoritm kontrollimaks, et järjestikuste tippude iga kolmik oleks CCW. Selleks kulub vaid mõni rida Pythoni geomeetriakoodi (eeldades, et points on esitatud vastupäeva - kui points on päripäeva, soovite, et kõik kolmikud oleksid päripäeva):

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

Proovige seda mõne näite abil paberil. Seda tulemust saate isegi kasutada määratlema kumerus. (Asjade intuitiivsemaks muutmiseks pange tähele, et CCW kõver A -> B -> C vastab nurkale alla 180º, mida on laialt õpetatud viis kumeruse määratlemiseks .)

Liinide ristmik

Teise näitena käsitleme joone lõigu ristmikku, mis võib ka olla lahendada ainult CCW abil :

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)

Miks see nii on? Liinisegmendi ristumiskoha võib sõnastada ka järgmiselt: kui anda punkt, mille lõpp-punktid on A ja B, kas teise lõigu otspunktid C ja D asuvad AB samal küljel? Teisisõnu, kui pöörded punktidest A -> B -> C ja A -> B -> D on samas suunas, ei saa segmendid ristuda. Seda tüüpi keelt kasutades selgub, et selline probleem on CCW leib ja või.

Range määratlus

Nüüd, kui me tunneme CCW olulisust, vaatame, kuidas see arvutatakse. Arvestades punkte A, B ja C:

def ccw(A, B, C): '''Tests whether the turn formed by A, B, and C is ccw''' return (B.x - A.x) * (C.y - A.y) > (B.y - A.y) * (C.x - A.x)

Selleks, et mõista, kust see määratlus pärineb, kaaluge vektoreid AB ja BC. Kui võtta nende ristprodukt AB x BC, on see vektor piki z-telge. Kuid mis suunas (st + z või -z)? Nagu selgub, kui ristprodukt on positiivne, on pööre vastupäeva; muidu on päripäeva.

See määratlus näib ebaloomulik, kui teil pole lineaarsest algebrast, parempoolse reegli jms mõistmist väga hea. Kuid seetõttu on meil abstraktsioon - kui mõelda CCW-le, mõelge lihtsalt selle intuitiivsele määratlusele, mitte arvutamisele. Väärtus saab kohe selgeks.

Minu sukeldumine arvutusgeomeetriasse ja programmeerimine Pythoni abil

Viimase kuu jooksul olen töötanud Pythonis mitme arvutusliku geomeetria algoritmi juurutamise kallal. Kuna ma joonistan neile järgnevates jaotistes, kirjeldan sekundit oma arvutusliku geomeetria rakendusi, mille leiate GitHub .

Märkus: minu kogemus on tõepoolest piiratud. Kuna olen selle kraamiga tegelenud juba kuid, mitte aastaid, võtke minu nõu soolateraga. See tähendab, et õppisin selle paari kuuga palju, seega loodan, et need näpunäited osutuvad kasulikuks.

Kirkpatricku algoritm

Minu töö keskmes oli programmi rakendamine Kirkpatricku algoritm eest punkti asukoht . Probleemilause oleks umbes selline: antud tasapinnaline alajaotus (hunnik kattuvaid hulknurki tasapinnas) ja punkt P, milline hulknurk sisaldab P? Mõelge steroididel punkt-polügoonis - ühe hulknurga asemel saate neid lennukiga.

milline on kogu adresseeritav turg

Kasutusjuhuks kaaluge veebisaiti. Kui kasutaja klõpsab hiirt, peab veebileht sellest aru saama mida kasutaja klõpsas võimalikult kiiresti. Kas see oli nupp A? Kas see oli link B? Veebileht koosneb mittekattuvatest hulknurkadest, nii et Kirkpatricki algoritm oleks hädavajalik.

Kuigi ma ei hakka algoritmi põhjalikult arutama, saate lisateavet siin .

Minimaalne piirav kolmnurk

Alaülesandena rakendasin ka O’Rourke'i algoritm minimaalse ümbritseva / piirava kolmnurga (see tähendab väikseima kolmnurga leidmiseks, mis ümbritseb punktide kogumit) arvutamiseks lineaarajaga.

Märkus. Minimaalse piirneva kolmnurga arvutamine ei aita ega kahjusta Kirkpatricki algoritmi asümptootilist toimivust, kuna arvutus ise on lineaarne, kuid see on kasulik esteetilistel eesmärkidel.

Praktilised nõuanded, rakendused ja mured

Eelmistes jaotistes keskenduti sellele, miks arvutuslikku geomeetriat võib olla raske täpselt mõista.

Praktikas peame tegelema täiesti uue hulga muredega.

Kas mäletate CCW-d? Kena seguna näeme veel ühte selle suurepärast omadust: see kaitseb meid ujukoma vigade ohtude eest.

Ujuva punkti vead: miks CCW on kuningas

Minu arvutusliku geomeetria kursusel Bernard Chazelle , lugupeetud professor, kes on avaldas rohkem artikleid kui ma oskan arvestada, tegi selle reegliks, et me ei saa algoritmi või lahenduse kirjeldamisel nurki mainida.

Sellest sai reegel, mida me isegi ei suutnud mainida nurgad. Miks? Nurgad on segased - nurgad on „määrdunud“.

Miks? Nurgad on segased. Nurgad on “määrdunud”. Kui peate arvutama nurga, peate jagama või kasutama mõnda lähendust (näiteks kõike, mis hõlmab näiteks Pi) või mõnda trigonomeetrilist funktsiooni.

Kui peate arvutama nurga koodis , saate peaaegu alati olema ligilähedane. Teil on mõni väike ujukoma täpsusaste - see on oluline, kui proovite võrdsust. Võite lahendada mõne tasapinna punkti kahe erineva meetodi abil ja muidugi eeldada, et p1.x == p2.x and p1.y == p2.y Kuid tegelikult see kontroll ebaõnnestub sageli . Edasi (ja üsna ilmselgelt) on neil punktidel siis erinevad räsid.

Asja teeb veelgi hullemaks see, et teie veaaste suureneb, kui teie pisikesed erinevused levivad arvutustes. (Mõnede teaduslike näidete jaoks see paber läbib selle, mis võib kumera kere või Delaunay triangulatsiooni arvutamisel valesti minna.)

Mida me saame selle vastu teha?

peaaegu võrdne

Üks osa Pythoni arvutusgeomeetria probleemist on see, mida me vajame täpsus maailmas, kus asjad on harva täpne. See muutub probleemiks sagedamini kui nurkade käsitlemisel. Mõelge järgmisele:

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

Tegelikult trükitakse sellest koodist „Error!” umbes 70% ajast (empiiriliselt). Selle mure saame lahendada, olles võrdsuse määratluse suhtes veidi leebem; see tähendab teatud täpsuse ohverdamisega.

Ühte lähenemist, mida olen kasutanud (ja näinud näiteks mõnes OpenCV moodulid) on defineerida kaks arvu võrdsetena, kui need erinevad ainult mõne väikese väärtusega epsiloni poolest. Pythonis võib teil olla:

def almostEqual(x, y, EPSILON=1e-5): return abs(x - y)

Praktikas on sellest palju abi. Harva, kui kunagi, arvutaksite kaks punkti, mis erinevad vähem kui 1e-5 ja mis on tegelikult mõeldud erinevateks punktideks. Soovitan tungivalt seda tüüpi alistamisi rakendada. Sarnaseid meetodeid saab kasutada liinide jaoks, näiteks:

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

Muidugi on pakutud täpsemaid lahendusi. Näiteks 'täpse geomeetrilise arvutuse' mõttekool (kirjeldatud artiklis see paber ) eesmärk on, et kõik programmi otsusteed sõltuksid ainult programmist märk mõne arvutuse asemel selle täpse arvulise väärtuse, eemaldades paljud ujukomaarvutustega seotud probleemid. Meie peaaegu võrdsus lähenemine lihtsalt kriimustab pinda, kuid on praktikas sageli piisav.

CCW on kuningas

Kõrgemal tasemel on (vaieldamatult) problemaatiline, et me isegi määratlema meie lahendused selliste täpsete arvutuslike suuruste osas nagu nurgad või punktkoordinaadid. Selle asemel, et tegeleda ainult sümptomitega (s.t ujukoma vigade pesemine almostEqual -ga), miks mitte tegeleda selle põhjustega? Lahendus: nurkade asemel mõtlemise asemel mõtle CCW mõistes , mis aitab hõlbustada ujukomaarvutamisega seotud probleeme.

Siin on konkreetne näide: oletame, et teil on mõni kumer hulknurk P , tipp v ja mingil hetkel u väljaspool hulknurka. Kuidas saate aru, kas joon uv ristub P ülal või all v või üldse mitte pidevas ajas?

Toore jõu lahendus (lisaks sellele, et see on pigem lineaarne kui konstantne), oleks problemaatiline, kuna peate arvutama mõned täpsed sirgete lõikepunktid.

Üks pideva aja lähenemine, mida olen näinud, hõlmab järgmist:

• Mõne nurga arvutamine, kasutades arctan2
• Nende nurkade teisendamine kraadidesse, korrutades 180 / Pi-ga.
• Nende erinevate nurkade vaheliste seoste uurimine.

Õnneks kasutas autor almostEqual ülaltoodud tehnika ujukoma vigade silumiseks.

Minu arvates oleks parem ujukombe vigade probleemi täielikult vältida. Kui võtate mõne minuti probleemi paberil vaatamiseks, võite saada lahenduse, mis põhineb täielikult CCW-l. Intuitsioon: kui tipud külgnevad v asuvad samal küljel uv , siis joon ei ristu; muul juhul vaadake, kas u ja v asuvad külgnevate tippude vahelise joone samal küljel ja võrdlevad sõltuvalt tulemusest nende kõrgusi.

Siin on ülaltoodud ristmiku testimiseks Pythoni kood v (allpool asuv ristmik muudab võrdluste suuna lihtsalt vastupidiseks):

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 u.y > verts[v].y else: return u.y

Lahendus ei ole palja silmaga kohe ilmne, kuid siiski keel arvutusliku geomeetria algoritmi kohta: ‘joone sama külg’ on selle usaldusväärse algoritmi klassikaline element.

Valmis on parem kui täiuslik

Arvutusgeomeetrilises kirjanduses on pealtnäha lihtsate toimingutega seotud üsna palju võlureid. See annab teile valiku: võite teha asju raskemini, järgides mõnda paberit, mis määratleb uskumatult arenenud lahenduse mitte nii kaugele arenenud probleemile, või võite teha asju lihtsa viisi natuke toore jõuga.

Jällegi kasutan näidet: suvalise polügooni juhusliku sisepunkti valimine. Teisisõnu, ma annan teile mõne lihtsa hulknurga ja teie annate mulle selle sees juhusliku punkti (jaotatud ühtlaselt kogu hulknurga ulatuses).

Sageli on testimiseks vaja sisepunkte. Sellisel juhul pole teil arvutusliku geomeetria algoritmi jaoks (mõistlikkuse piires) mingeid konkreetseid käitamisnõudeid. Kiire ja määrdunud lahendus, mille rakendamiseks kulub ~ 2 minutit, oleks valida hulknurka sisaldavasse kasti juhuslik punkt ja vaadata, kas punkt ise asub polügoonis.

Näiteks võime kaks korda vahele jätta ja leida kehtiva valimi ainult kolmandast punktist:

Siin on kood:

class Polygon(object): ... def interiorPoint(self): '''Returns a random point interior point''' min_x = min([p.x for p in self.points]) max_x = max([p.x for p in self.points]) min_y = min([p.y for p in self.points]) max_y = max([p.y 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

Seda tuntakse kui tagasilükkamise proovide võtmine : võtke juhuslikke punkte, kuni üks vastab teie kriteeriumidele. Ehkki teie kriteeriumidele vastava punkti leidmiseks võib vaja minna mitu näidist, on tegelikkuses erinevus on tühine teie testipaketi jaoks. Miks siis rohkem vaeva näha? Kokkuvõtteks: ärge kartke minna räpast teed, kui juhus seda nõuab.

Muide: kui soovite täpne Juhusliku valimi moodustamise algoritm on nutikas siin mille olen allpool rakendanud. Selle põhisisu:

1. Kolmnurkne oma hulknurk (st. murra see kolmnurkadeks).
2. Valige kolmnurk, mille tõenäosus on proportsionaalne selle pindalaga.
3. Võtke juhuslik punkt valitud kolmnurga seest (konstantse ajaga operatsioon).

Pange tähele, et see algoritm nõuab kolmnurga all oma hulknurka, mis paneb algoritmile koheselt siduma teistsuguse tööaja ning vajaduse omama raamatukogu suvaliste hulknurkade triangulatsiooniks (kasutasin poly2tri Pythoni köidetega).

from p2t import CDT class Triangle(object): ... def area(self): return abs((B.x * A.y - A.x * B.y) + (C.x * B.y - B.x * C.y) + (A.x * C.y - C.x * A.y)) / 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(t.a.x, t.a.y) B = Point(t.b.x, t.b.y) C = Point(t.c.x, t.c.y) 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()

Loodetavasti ilmneb lisapingutus koodist. Pidage meeles: nagu öeldakse Facebookis, 'Tehtud on parem kui täiuslik' . Sama kehtib arvutusliku geomeetria probleemide kohta.

Visuaalne ja automatiseeritud testimine

Kuna paljud probleemid, millega arvutusgeomeetrias tegelete, on määratletud hõlpsasti visualiseeritavate omaduste või suuruste järgi, on visuaalne testimine eriti oluline - kuigi iseenesest ebapiisav. Ideaalseks testikomplektiks on visuaalse ja juhusliku valiku automatiseeritud testide kombinatsioon.

Ideaalseks testikomplektiks on visuaalse ja juhusliku valiku automatiseeritud testide kombinatsioon.

Jällegi jätkame eeskujuga. Kaaluge Kirkpatricki algoritmi rakendamise testimist. Ühes etapis peab algoritm siduma etteantud hulknurga kolmnurgaga ja kolmnurga all hulknurga ja välimise kolmnurga vahel. Siin on visuaalne näide, kus pidev roheline joon määratleb esialgse hulknurga ja katkendjooned kolmnurkse piirkonna.

Kinnitada, et see triangulatsioon on õigesti täidetud, on koodi abil väga raske kontrollida, kuid see on inimsilmale kohe ilmne. Märkus: soovitan tungivalt kasutada Matplotlib visuaalse testimise hõlbustamiseks - seal on kena juhend siin .

Hiljem soovime kontrollida, kas algoritm otsib punkte õigesti. Randomiseeritud, automatiseeritud lähenemine oleks luua hulk sisepunkte igale polügoonile ja veenduda, et tagastame soovitud hulknurga. Koodis:

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

Seejärel saaksime kasutada runLocator meetodit erinevatel hulknurkade komplektidel, andes meile hästi mitmekesise testipaketi.

Avatud lähtekoodiga lahendused

Arvutusgeomeetrial on kena avatud lähtekoodiga teekide ja lahenduste pakett, mis on saadaval olenemata teie valitud programmeerimiskeelest (kuigi C ++ teegid näivad koguvat ebaproportsionaalselt palju).

kuidas maandada valuutariski

Olemasolevate avatud lähtekoodiga lahenduste kasutamise eelised ( nagu Pythoni teadusliku arvutamise puhul ) on tuntud ja neid on palju arutatud, nii et ma ei hakka seda siin jätkama. Kuid ma mõtlesin mainida mõnda Pythoni-keskset ressurssi, mis minu arvates olid kasulikud:

• poly2tri : suurepärane raamatukogu hulknurkade kiireks triangulatsiooniks. Samuti toetab (ja see on sageli ülioluline) hulknurki augud neis. Kirjutatud C ++ keeles, on poly2tri ka Pythoni köidetega ja seda oli üsna lihtne üles seada ja käivitada. Vaadake minu triangulate ülaltoodud meetod funktsiooni kutsete maitsmiseks.
• scipy.ruumiline : sisaldab funktsioone kumerate kere, Delaunay kolmnurkade ja muu arvutamiseks. Kiire (nagu alati), usaldusväärne jne. Märkus. Minu arvates oli kasulik kasutada enda Point andmetüüp koos toNumpy meetod: def np(self): return [self.x, self.y]. Siis saaksin hõlpsasti nimetada scipy.spatial meetodeid, näiteks: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV : avatud lähtekoodiga arvutivisiooni teegil on mõned toredad eraldiseisvad arvutusgeomeetria moodulid. Eelkõige kasutasin seda minimaalne ümbritseva kolmnurga funktsioon mõnda aega enne ise rakendamist.

Järeldus

Loodan, et see postitus on andnud teile maitset arvutusliku geomeetria kui a Pythoni arendaja , põnevate probleemide ja sama põnevate rakendustega rikas teema.

Praktikas esitavad arvutuslikud geomeetrilised rakendused ainulaadseid väljakutseid, mis sunnivad teid kasutama uusi ja põnevaid probleemide lahendamise oskusi.

Kui soovite rohkem teada saada või kui teil on minu jaoks küsimusi, saab minuga ühendust võtta [meiliga kaitstud] .