Kun ihmiset ajattelevat laskennallista geometriaa, kokemukseni mukaan he tyypillisesti ajattelevat yhtä kahdesta asiasta:

1. Vau, se kuulostaa monimutkaiselta.
2. Todellakin, kupera runko .

Tässä viestissä haluaisin valottaa hieman laskennallista geometriaa, aloittaen lyhyestä katsauksesta aiheesta ennen siirtymistä käytännön neuvoihin, jotka perustuvat omiin kokemuksiini ( hyppää eteenpäin jos sinulla on hyvä käsiteltävä aihe).

Mikä on kaikki hätää?

Vaikka kuperan rungon laskennalliset geometriset algoritmit sisältyvät tyypillisesti algoritmien johdantokurssi , laskennallinen geometria on paljon rikkaampi aihe, johon keskimääräinen kehittäjä / tietojenkäsittelytieteen tutkija kiinnittää harvoin riittävästi huomiota (ellet tee pelejä tai jotain).

Teoreettisesti kiehtova…

Teoreettisesta näkökulmasta laskennallisen geometrian kysymykset ovat usein erittäin mielenkiintoisia; vastaukset, pakottavat; ja polut, joilla he ovat saavuttaneet, vaihtelivat. Pelkästään näiden ominaisuuksien vuoksi se on mielestäni tutkimuksen arvoinen ala.

Harkitse esimerkiksi Taidegalleriaongelma : Meillä on taidegalleria ja haluamme asentaa valvontakamerat vartioimaan taidetta. Mutta meillä on tiukka budjetti, joten haluamme käyttää mahdollisimman vähän kameroita. Kuinka monta kameraa tarvitsemme?

Kun käännämme tämän laskennalliseksi geometriseksi merkinnäksi, gallerian 'pohjapiirros' on vain yksinkertainen monikulmio. Ja kyynärrasvalla voimme todistaa sen n / 3 kamerat riittävät aina polygoniin n kärjet, ei väliä kuinka sotkuinen se on. todiste itse käyttää kaksoisgraafeja, joitain graafiteoriaa, triangulaatioita ja muuta.

Täällä näemme fiksun todistustekniikan ja tuloksen, joka on tarpeeksi utelias, jotta sitä voidaan arvioida yksin. Mutta jos teoreettinen merkitys ei riitä sinulle ...

Ja tärkeä käytännössä

Kuten aiemmin mainitsin, pelinkehitys riippuu suuresti laskennallisen geometrian soveltamisesta (esimerkiksi törmäystunnistus luottaa usein esinejoukon kuperan rungon laskemiseen); samoin paikkatietojärjestelmät (GIS) , joita käytetään maantieteellisten tietojen laskemiseen ja suorittamiseen; ja robotiikka myös (esim. näkyvyys- ja suunnitteluongelmien vuoksi).

Miksi se on niin kovaa?

Otetaan melko yksinkertainen laskennallinen geometrian ongelma: onko piste ja monikulmio, onko piste polygonin sisällä? (Tätä kutsutaan kohta polygonissa tai PIP-ongelma .)

PIP tekee hyvää työtä osoittaessaan, miksi laskennallinen geometria voi olla (petollisesti) kova. Ihmissilmälle tämä ei ole vaikea kysymys. Näemme seuraavan kaavion ja se on heti meille ilmeinen, että kohta on monikulmiossa:

Jopa suhteellisen monimutkaisilla monikulmioilla vastaus ei ohita meitä yli sekunnin tai kaksi. Mutta kun syötämme tämän ongelman tietokoneelle, se saattaa nähdä seuraavan:

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)

Ihmisen aivoille intuitiivinen ei käänny niin helposti tietokoneen kieleen.

Abstraktimmin (ja sivuuttamatta tarvetta edustaa näitä asioita koodissa), näillä tieteenaloilla havaittuja ongelmia on erittäin vaikea tarkentaa (tehdä tarkoiksi) laskennallisen geometrian algoritmissa. Kuinka kuvaisimme kohta polygonissa -skenaarion käyttämättä sellaista tautologista kieltä kuin 'piste on monikulmion sisällä, jos se on polygonin sisällä'? Monet näistä ominaisuuksista ovat niin perustavanlaatuisia ja niin yksinkertaisia, että niitä on vaikea määritellä konkreettisesti.

Kuinka kuvaisimme kohta polygonissa -skenaarion käyttämättä sellaista tautologista kieltä kuin 'se on polygonin sisällä, jos se on polygonin sisällä'?

Vaikea, mutta ei mahdoton. Voit esimerkiksi tarkentaa polygonin pistettä seuraavilla määritelmillä:

• Piste on monikulmion sisällä, jos mikä tahansa pisteestä alkava ääretön säde leikkaa pariton määrä polygonin reunoja (tunnetaan nimellä pariton-pariton sääntö ).
• Piste on monikulmion sisällä, jos sillä on nolla käämitysnumero (määritetään lukumääränä, kuinka monta kertaa monikulmion määrittävä käyrä kulkee pisteen ympäri).

Ellei sinulla ole kokemusta laskennallisesta geometriasta, nämä määritelmät eivät todennäköisesti ole osa olemassa olevaa sanastoa. Ja ehkä se on vertauskuva siitä, kuinka laskennallinen geometria voi ajaa sinut ajattele toisin .

Esittelyssä CCW

Nyt kun olemme tietoisia laskennallisen geometrian ongelmien tärkeydestä ja vaikeudesta, on aika kastaa kätemme.

Kohteen selkärangassa on petollisesti voimakas primitiivinen toiminto: vastapäivään, tai lyhyeksi CCW. (Varoitan nyt: CCW ilmestyy uudestaan ​​ja uudestaan.)

CCW ottaa kolme pistettä A, B ja C argumentteina ja kysyy: muodostavatko nämä kolme pistettä vastapäivään (verrattuna myötäpäivään)? Toisin sanoen, onko A -> B -> C vastapäivään kulma?

Esimerkiksi vihreä pisteet ovat CCW, kun taas netto pisteet eivät ole:

Miksi CCW on tärkeä asia

CCW antaa meille a primitiivinen toiminnan, johon voimme rakentaa. Se antaa meille paikan aloittaa laskennallisen geometrian ongelmien tarkentaminen ja ratkaiseminen.

Tarkastelemme kahta esimerkkiä, jotta voisit tuntea sen voiman.

Kuparuuden määrittäminen

Ensimmäinen: annettu polygoni, pystytkö selvittämään, onko se kupera? Kuperuus on korvaamaton ominaisuus: tietäen, että polygonisi ovat kuperat, voit usein parantaa suorituskykyä suuruusluokittain. Konkreettisena esimerkkinä: siellä on a melko yksinkertainen PIP-algoritmi joka toimii Log (n) -aikana kuperille polygoneille, mutta epäonnistuu monille koverille polygoneille.

Intuitiivisesti tällä aukolla on järkeä: kuperat muodot ovat 'hienoja', kun taas koverilla muodoilla voi olla teräviä reunoja sisään ja ulos - ne eivät vain noudata samoja sääntöjä.

Yksinkertainen (mutta ei selvä) laskennallinen geometrian algoritmi kuperuuden määrittämiseksi on tarkistaa, että jokainen peräkkäisten huippujen tripletti on CCW. Tämä vie vain muutaman rivin Python-geometriakoodia (olettaen, että points on järjestetty vastapäivään - jos points on myötäpäivään, haluat, että kaikki kolmoset ovat myötäpäivään):

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

Kokeile tätä paperilla muutamalla esimerkillä. Voit jopa käyttää tätä tulosta määritellä kuperuus. (Jotta asiat olisivat intuitiivisempia, huomaa, että CCW-käyrä A -> B -> C vastaa alle 180º: n kulmaa, mikä on laajalti opetettua tapa määritellä kuperuus .)

Linjan risteys

Toisena esimerkkinä harkitaan viivasegmentin leikkausta, joka voi myös olla ratkaistu yksin CCW: llä :

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)

Miksi näin on? Suoran segmentin leikkaus voidaan myös muotoilla seuraavasti: jos segmentti, jolla on päätepisteet A ja B, ovatko toisen segmentin päätepisteet C ja D AB: n samalla puolella? Toisin sanoen, jos käännökset A -> B -> C ja A -> B -> D ovat samassa suunnassa, segmentit eivät voi leikata. Kun käytämme tämän tyyppistä kieltä, käy selväksi, että tällainen ongelma on CCW: n leipä ja voi.

Tarkka määritelmä

Nyt kun olemme maistaneet CCW: n merkityksen, katsotaanpa, miten se lasketaan. Annetut pisteet 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)

Harkitse vektorit AB ja BC ymmärtääksesi, mistä tämä määritelmä tulee. Jos otamme heidän ristitulonsa AB x BC, tämä on vektori z-akselia pitkin. Mutta mihin suuntaan (ts. + Z tai -z)? Kuten käy ilmi, jos ristitulos on positiivinen, käännös on vastapäivään; muuten se on myötäpäivään.

Tämä määritelmä tuntuu epäjohdonmukaiselta, ellei sinulla ole todella hyvää käsitystä lineaarisesta algebrasta, oikean käden säännöstä jne. Mutta siksi meillä on abstraktio - kun ajattelet CCW: tä, ajattele vain sen intuitiivista määritelmää eikä sen laskentaa. Arvo on heti selvä.

Sukellukseni laskennalliseen geometriaan ja ohjelmointiin Pythonilla

Viimeisen kuukauden aikana olen työskennellyt useiden laskennallisten geometristen algoritmien toteuttamiseksi Pythonissa. Koska piirrän niitä seuraavien osioiden aikana, käytän hetken kuvaamaan laskennallisia geometriasovelluksiani, jotka löytyvät GitHub .

Huomaa: Kokemukseni on tosin rajallinen. Koska olen työskennellyt näiden juttujen parissa kuukausien eikä vuosien ajan, ota neuvoani jyvän suolalla. Siitä huolimatta opin paljon näiden muutaman kuukauden aikana, joten toivon, että nämä vinkit osoittautuvat hyödyllisiksi.

Kirkpatrickin algoritmi

Työn ytimessä oli Kirkpatrickin algoritmi varten pisteen sijainti . Ongelma olisi jotain: annettu tasainen osa-alue (joukko ei-päällekkäisiä polygoneja tasossa) ja piste P, mikä polygoni sisältää P: n? Ajattele pisteitä polygonissa steroideilla - yhden polygonin sijasta sinulla on tasainen niistä.

Harkitse käyttötapauksena verkkosivua. Kun käyttäjä napsauttaa hiirtä, verkkosivun on selvitettävä mitä käyttäjä napsautti sitä mahdollisimman nopeasti. Oliko se painike A? Oliko se linkki B? Verkkosivu koostuu päällekkäisistä polygoneista, joten Kirkpatrickin algoritmi olisi hyvässä asemassa auttamaan.

Vaikka en keskustele algoritmista perusteellisesti, voit oppia lisää tässä .

Pienin rajaava kolmio

Alitehtävänä toteutin myös O’Rourken algoritmi pienimmän ympäröivän / rajoittavan kolmion (eli pienimmän kolmiota ympäröivän kolmion löytämiseksi) laskemiseksi lineaarisessa ajassa.

Huomautus: Pienimmän rajoittavan kolmion laskeminen ei auta tai vahingoita Kirkpatrickin algoritmin asymptoottista suorituskykyä, koska itse laskenta on lineaarista - mutta se on hyödyllinen esteettisissä tarkoituksissa.

Käytännön neuvoja, sovelluksia ja huolenaiheita

Edelliset kohdat keskittyivät siihen, miksi laskennallista geometriaa voi olla vaikea perustella tarkasti.

Käytännössä meidän on kohdattava aivan uusi joukko huolenaiheita.

Muistatko CCW: n? Kiva segmentti, katsotaanpa vielä yksi sen suurista ominaisuuksista: se suojaa meitä liukulukuvirheiden vaaroilta.

Liukulukuvirheet: Miksi CCW on kuningas

Laskennallisen geometrian kurssillani Bernard Chazelle , arvostettu professori, joka on julkaissut lisää papereita kuin voin laskea, teki siitä säännön, että emme voineet mainita kulmia yritettäessä kuvata algoritmia tai ratkaisua.

Siitä tuli sääntö, jota emme voineet edes mainita kulmat. Miksi? Kulmat ovat sotkuiset - kulmat ovat 'likaisia'.

Miksi? Kulmat ovat sotkuiset. Kulmat ovat ”likaisia”. Kun sinun on laskettava kulma, sinun on jaettava tai käytettävä likiarvoa (esimerkiksi mitä tahansa Pi: tä varten) tai trigonometristä funktiota.

Kun joudut laskemaan kulman koodissa , melkein aina olla lähellä. Sinulta tulee pois pieni liukulukuinen tarkkuus - sillä on merkitystä, kun testaat tasa-arvoa. Voit ratkaista jonkin tason tason kahdella eri tavalla ja tietysti odottaa, että p1.x == p2.x and p1.y == p2.y Mutta todellisuudessa tämä tarkistus epäonnistuu usein . Lisäksi (ja selvästi) näillä pisteillä on sitten erilaiset hajautusarvot.

Tilanteen pahentamiseksi virhetasosi kasvaa, kun pienet erot etenevät laskelmien kautta. (Lisää tieteellisiä esimerkkejä: Tämä paperi käy läpi mikä voi mennä pieleen laskettaessa kuperaa runkoa tai Delaunayn kolmiomittausta.)

Joten mitä voimme tehdä asialle?

melkein yhtä

Osa Pythonin laskennallisen geometrian ongelmasta on sitä, että vaadimme tarkkuus maailmassa, jossa asiat ovat harvoin tarkka. Tästä tulee ongelma useammin kuin kulmia käsiteltäessä. Harkitse seuraavaa:

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

Itse asiassa tämä koodi tulostaa virheen! noin 70% ajasta (empiirisesti). Voimme puuttua tähän huoleen olemalla hieman lempeämpi tasa-arvon määritelmän suhteen; eli uhraamalla jonkin verran tarkkuutta.

Yksi lähestymistapa, jota olen käyttänyt (ja nähnyt esimerkiksi joissakin OpenCV moduulit) on määritellä kaksi numeroa yhtä suuriksi, jos ne eroavat toisistaan ​​vain jonkin pieniarvoisen epsilonin suhteen. Pythonissa sinulla voi olla:

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

Käytännössä tämä on erittäin hyödyllistä. Harvoin, jos koskaan, laskisitko kaksi pistettä, jotka eroavat toisistaan ​​alle 1e-5 ja joiden on tosiasiallisesti tarkoitus olla eri pisteitä. Suosittelen erittäin voimakkaasti tämän tyyppisen ohituksen käyttöönottoa. Samanlaisia ​​menetelmiä voidaan käyttää linjoille, esimerkiksi:

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

Tietysti on ehdotettu edistyneempiä ratkaisuja. Esimerkiksi tarkan geometrisen laskennan ajattelukoulu (kuvattu kohdassa Tämä paperi ) tavoitteena on, että kaikki ohjelman päätöksentekopolut riippuvat yksinomaan ohjelmasta merkki joidenkin laskelmien sijasta sen tarkan numeerisen arvon sijasta poistetaan monet liukulukulaskelmiin liittyvistä huolenaiheista. Meidän lähes tasa-arvo lähestymistapa vain naarmuttaa pintaa, mutta on usein riittävä käytännössä.

CCW on kuningas

Ylemmällä tasolla on (epäilemättä) ongelmallista, että me jopa määritellä ratkaisumme tarkkojen laskennallisten suureiden suhteen, kuten kulmat tai pistekoordinaatit. Sen sijaan, että puuttuisi pelkästään oireisiin (ts. Liukulukujen virheiden pesu almostEqual: lla), miksi et kuitenkaan korjata syytä? Ratkaisu: Kulmien sijaan ajattelun sijaan ajatella CCW: n suhteen , joka auttaa lieventämään liukulukulaskentaan liittyviä huolenaiheita.

Tässä on konkreettinen esimerkki: Oletetaan, että sinulla on kupera monikulmio P , kärki v , ja jokin kohta u monikulmion ulkopuolella. Kuinka voit selvittää, onko viiva uv leikkaa P ylä- tai alapuolella v vai ei lainkaan vakiona?

Raa'an voiman ratkaisu (sen lisäksi, että se on lineaarinen, eikä vakio) olisi ongelmallinen, koska joudut laskemaan tarkat viivan leikkauspisteet.

Yksi näkemäni jatkuvan ajan lähestymistapa sisältää:

• Lasketaan joitain kulmia arctan2: lla.
• Muunna nämä kulmat asteiksi kertomalla 180 / Pi.
• Näiden eri kulmien välisten suhteiden tutkiminen.

Onneksi kirjoittaja käytti almostEqual yllä oleva tekniikka tasoittamaan liukulukuvirheet.

Mielestäni on parempi välttää liukulukuvirheet kokonaan. Jos sinulla on muutama minuutti aikaa tutkia ongelmaa paperilla, saat ratkaisun, joka perustuu kokonaan CCW: hen. Intuitio: jos pisteet vierekkäin v ovat samalla puolella uv , niin viiva ei leikkaa; muuten, katso jos u ja v ovat vierekkäisten pisteiden välisen viivan samalla puolella ja vertailevat tuloksesta riippuen niiden korkeuksia.

Tässä on Python-koodi risteyksen testaamiseksi yllä v (alla oleva leikkauskohta kääntää vain vertailusuunnan):

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

Ratkaisu ei ole heti ilmeinen paljaalla silmällä, mutta se on Kieli laskennallisen geometrian algoritmista: ’viivan sama puoli’ on klassinen osa luotettavaa algoritmia.

Valmis on parempi kuin täydellinen

Laskennallisessa geometrisessa kirjallisuudessa näennäisesti yksinkertaisissa toiminnoissa on usein melko paljon velhoja. Tämä antaa sinulle valinnanvaraa: voit tehdä asioita kovalla tavalla seuraamalla paperia, joka määrittelee uskomattoman edistyneen ratkaisun ei-niin edistyneeseen ongelmaan - tai voit tehdä asioita helpolla tavalla hieman raakalla voimalla.

Jälleen käytän esimerkkiä: satunnaisen sisäpisteen ottaminen mielivaltaisesta monikulmiosta. Toisin sanoen annan sinulle yksinkertaisen monikulmion, ja annat minulle sen sisällä satunnaisen pisteen (tasaisesti jakautunut monikulmion yli).

Usein testaukseen tarvitaan sisätiloja. Siinä tapauksessa sinulla ei ole mitään erityisiä ajonaikaisia ​​vaatimuksia laskennallisessa geometrian algoritmissa, joka tuottaa ne (järjen rajoissa). Nopea ja likainen ratkaisu, jonka toteuttaminen vie ~ 2 minuuttia, olisi valita satunnaispiste polygonin sisältävässä laatikossa ja nähdä, onko piste itse polygonin sisällä.

Saatamme esimerkiksi jättää väliin kahdesti ja löytää kelvollisen näytteen vain kolmannesta kohdasta:

Tässä koodi:

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

Tämä tunnetaan nimellä hylkäysnäyte : ota satunnaisia ​​pisteitä, kunnes yksi täyttää kriteerit. Vaikka se voi vaatia useita näytteitä löytääksesi kriteerisi vastaavan pisteen, käytännössä ero on merkityksetön testipakettiisi. Joten miksi työskennellä kovemmin? Yhteenvetona: älä pelkää mennä likaisella reitillä, kun tilaisuus sitä vaatii.

Muuten: jos haluat tarkka satunnaisen näytteenoton algoritmi, on älykäs tässä jonka olen toteuttanut alla. Sen ydin:

1. Kolmio monikulmiosi (eli jaa se kolmioiksi).
2. Valitse kolmio, jonka todennäköisyys on verrannollinen sen pinta-alaan.
3. Ota satunnainen piste valitun kolmion sisältä (vakioaikainen operaatio).

Huomaa, että tämä algoritmi edellyttää kolmiota monikulmiosta, mikä asettaa algoritmille välittömästi erilaisen ajonajan sidotun sekä välttämättömyyden, jonka sinun on omistaa kirjasto mielivaltaisten polygonien kolmioimiseksi (käytin poly2tri Python-siteillä).

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

Toivottavasti ylimääräinen vaivaa käy ilmi koodista. Muista: kuten Facebookissa sanotaan, 'Tehty on parempi kuin täydellinen' . Sama koskee laskennallisia geometrian ongelmia.

Visuaalinen ja automatisoitu testaus

Koska monet laskennallisen geometrian kanssa työskentelemäsi ongelmat on määritelty helposti visualisoitavien ominaisuuksien tai määrien perusteella, visuaalinen testaus on erityisesti tärkeä - vaikkakin yksinään riittämätön. Ihanteellisessa testipaketissa on yhdistelmä visuaalista ja satunnaistettua automaattista testausta.

Ihanteellisessa testipaketissa on yhdistelmä visuaalista ja satunnaistettua automaattista testausta.

Jatkamme jälleen esimerkkiä. Harkitse Kirkpatrickin algoritmin toteutuksen testaamista. Yhdessä vaiheessa algoritmin on sidottava annettu polygoni kolmiolla ja kolmioitava alue monikulmion ja ulkokolmion välillä. Tässä on visuaalinen esimerkki, jossa yhtenäinen vihreä viiva määrittää alkupolygonin ja katkoviivat määrittävät kolmiomaisen alueen:

Vahvistamista siitä, että tämä kolmiomittaus on suoritettu oikein, on erittäin vaikea tarkistaa koodin avulla, mutta se on heti ilmeinen ihmissilmälle. Huomaa: Suosittelen, että käytät Matplotlib auttaa visuaalisessa testauksessa - siellä on mukava opas tässä .

Myöhemmin haluamme varmistaa, että algoritmi paikantaa pisteet oikein. Satunnaistettu, automatisoitu lähestymistapa olisi luoda joukko sisäpisteitä jokaiselle polygonille ja varmistaa, että palautamme halutun monikulmion. Koodissa:

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

Voisimme sitten käyttää runLocator menetelmä monikulmioille, mikä antaa meille hyvin monipuolisen testipaketin.

Avoimen lähdekoodin ratkaisut

Laskennallisessa geometriassa on mukava valikoima avoimen lähdekoodin kirjastoja ja ratkaisuja, jotka ovat käytettävissä valitsemastasi ohjelmointikielestä riippumatta (vaikka C ++ -kirjastot näyttävätkin keräävän suhteettoman paljon).

Nykyisten avoimen lähdekoodin ratkaisujen hyödyt ( kuten Pythonin tieteellisen laskennan yhteydessä ) ovat tunnettuja ja niistä on keskusteltu laajasti, joten en jatka sitä täällä. Ajattelin mainita muutaman Python-keskeisen resurssin, jotka pidin hyödyllisinä:

• poly2tri : loistava kirjasto monikulmioiden nopeaan kolmiomittaukseen. Tukee myös (ja tämä on usein ratkaisevaa) polygoneja reikiä heissä. Kirjoitettu C ++: lla, poly2tri: llä on myös Python-sidokset ja se oli melko helppo saada käyttöön. Katso minun triangulate yllä oleva menetelmä makuun funktiokutsut.
• scipy.spatial : sisältää toiminnot kuperien runkojen, Delaunayn kolmiomittausten ja muun laskemiseen. Nopea (kuten aina), luotettava jne. Huomaa: Minusta oli hyödyllistä käyttää omaa Point tietotyyppi a toNumpy menetelmä: def np(self): return [self.x, self.y]. Sitten voisin helposti kutsua scipy.spatial-menetelmiä, esim .: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV : avoimen lähdekoodin tietokonenäkökirjastossa on hienoja itsenäisiä laskennallisia geometriamoduuleja. Erityisesti käytin sitä vähimmäiskotelointitoiminto jonkin aikaa ennen kuin toteutan sen itse.

Johtopäätös

Toivon, että tämä viesti on antanut sinulle maun laskennallisen geometrian kauneudesta Python-kehittäjä , aihe, jossa on paljon kiehtovia ongelmia ja yhtä kiehtovia sovelluksia.

Käytännössä laskennalliset geometriset toteutukset esittävät ainutlaatuisia haasteita, jotka pakottavat sinut käyttämään uusia ja jännittäviä ongelmanratkaisutaitoja.

Jos olet kiinnostunut oppimaan lisää tai sinulla on kysyttävää, minuun voi ottaa yhteyttä osoitteessa [sähköposti suojattu] .