Geometria obliczeniowa w Pythonie: od teorii do zastosowania

Z mojego doświadczenia wynika, że ​​kiedy ludzie myślą o geometrii obliczeniowej, zazwyczaj myślą o jednej z dwóch rzeczy:

1. Wow, to brzmi skomplikowanie.
2. O tak, wypukły kadłub.

W tym poście chciałbym rzucić trochę światła na geometrię obliczeniową, zaczynając od krótkiego przeglądu tematu, a następnie przejdę do praktycznych porad opartych na moich własnych doświadczeniach (pomiń, jeśli dobrze znasz ten temat).

O co tyle zamieszania?

Podczas gdy algorytmy geometrii wypukłej kadłuba są zwykle zawarte w kursie wprowadzającym na temat algorytmów, geometria obliczeniowa jest znacznie bogatszym tematem, który rzadko przyciąga wystarczającą uwagę przeciętnego programisty/naukowca komputerowego (chyba że robisz gry lub coś takiego).

Teoretycznie intrygujące…

Z teoretycznego punktu widzenia zagadnienia geometrii obliczeniowej są często niezmiernie interesujące; odpowiedzi, przekonujące; a ścieżki, którymi do nich docierają, zróżnicowane. Już te cechy sprawiają, że moim zdaniem jest to dziedzina warta studiowania.

Rozważmy na przykład Problem Galerii Sztuki: Posiadamy galerię sztuki i chcemy zainstalować kamery bezpieczeństwa, aby chronić nasze dzieła sztuki. Ale mamy napięty budżet, więc chcemy używać jak najmniejszej liczby kamer. Ile kamer potrzebujemy?

Kiedy przełożymy to na obliczeniowy zapis geometryczny, „plan piętra” galerii jest po prostu prostym wielokątem. A przy odrobinie smarowania łokci możemy udowodnić, że kamery n/3 są zawsze wystarczające dla wielokąta na n wierzchołkach, bez względu na to, jak bardzo jest bałagan. Sam dowód wykorzystuje podwójne grafy, pewną teorię grafów, triangulacje i wiele innych.

Tutaj widzimy sprytną technikę dowodową i wynik, który jest na tyle ciekawy, że sam można go docenić. Ale jeśli teoretyczne znaczenie nie jest dla Ciebie wystarczające…

I ważne w praktyce

Jak wspomniałem wcześniej, tworzenie gier w dużej mierze opiera się na zastosowaniu geometrii obliczeniowej (na przykład wykrywanie kolizji często opiera się na obliczeniu wypukłej kadłuba zestawu obiektów); podobnie jak systemy informacji geograficznej (GIS), które są wykorzystywane do przechowywania i wykonywania obliczeń na danych geograficznych; a także robotykę (np. w przypadku problemów z widocznością i planowaniem).

Dlaczego to takie trudne?

Weźmy dość prosty problem z geometrii obliczeniowej: mając punkt i wielokąt, czy punkt leży wewnątrz wielokąta? (Nazywa się to problemem punktu w wielokącie lub PIP).

PIP wykonuje świetną robotę, demonstrując, dlaczego geometria obliczeniowa może być (zwodniczo) trudna. Dla ludzkiego oka to nie jest trudne pytanie. Widzimy następujący diagram i od razu jest dla nas oczywiste, że punkt znajduje się w wielokącie:

Nawet w przypadku stosunkowo skomplikowanych wielokątów odpowiedź nie umyka nam dłużej niż sekundę lub dwie. Ale kiedy przekażemy ten problem komputerowi, może on zobaczyć:

 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)

To, co jest intuicyjne dla ludzkiego mózgu, nie przekłada się tak łatwo na język komputerowy.

Mówiąc bardziej abstrakcyjnie (i ignorując potrzebę reprezentowania tych rzeczy w kodzie), problemy, które widzimy w tej dyscyplinie, są bardzo trudne do uściślania („upewnienia”) w algorytmie geometrii obliczeniowej. Jak moglibyśmy opisać scenariusz punkt w wielokącie bez użycia takiego tautologicznego języka, jak „Punkt jest wewnątrz wielokąta, jeśli jest wewnątrz wielokąta”? Wiele z tych właściwości jest tak podstawowych i tak podstawowych, że trudno je konkretnie zdefiniować.

Trudne, ale nie niemożliwe. Na przykład możesz ujednolicić punkt w wielokącie za pomocą następujących definicji:

• Punkt znajduje się wewnątrz wielokąta, jeśli dowolny promień nieskończony rozpoczynający się w tym punkcie przecina się z nieparzystą liczbą krawędzi wielokąta (znana jako reguła parzysty-nieparzysty).
• Punkt znajduje się wewnątrz wielokąta, jeśli ma niezerową liczbę uzwojeń (określoną jako liczba okrążeń krzywej definiującej wielokąt wokół punktu).

Jeśli nie masz doświadczenia z geometrią obliczeniową, te definicje prawdopodobnie nie będą częścią twojego istniejącego słownika. I być może jest to symboliczne dla tego, jak geometria obliczeniowa może skłonić cię do innego myślenia .

Przedstawiamy CCW

Teraz, gdy mamy wyczucie wagi i trudności problemów z geometrią obliczeniową, nadszedł czas, aby zmoczyć ręce.

Podstawą podmiotu jest zwodniczo potężna prymitywna operacja: przeciwnie do ruchu wskazówek zegara lub w skrócie „CCW”. (Ostrzegam cię teraz: CCW będzie się pojawiać raz za razem.)

CCW przyjmuje jako argumenty trzy punkty A, B i C i pyta: czy te trzy punkty składają się na obrót w kierunku przeciwnym do ruchu wskazówek zegara (w przeciwieństwie do obrotu zgodnego z ruchem wskazówek zegara)? Innymi słowy, czy A -> B -> C jest kątem przeciwnym do ruchu wskazówek zegara?

Na przykład, zielone punkty to CCW, podczas gdy czerwone punkty nie są:

Dlaczego CCW ma znaczenie

CCW daje nam prymitywną operację, na której możemy budować. Daje nam miejsce na rozpoczęcie rygoryzowania i rozwiązywania problemów geometrii obliczeniowej.

Aby dać ci poczucie jego mocy, rozważmy dwa przykłady.

Określanie wypukłości

Po pierwsze: mając wielokąt, czy potrafisz określić, czy jest on wypukły? Wypukłość jest nieocenioną właściwością: świadomość, że wielokąty są wypukłe, często pozwala poprawić wydajność o rzędy wielkości. Jako konkretny przykład: istnieje dość prosty algorytm PIP, który działa w czasie log(n) dla wielokątów wypukłych, ale zawodzi w przypadku wielu wielokątów wklęsłych.

Intuicyjnie ta luka ma sens: kształty wypukłe są „ładne”, podczas gdy kształty wklęsłe mogą mieć ostre krawędzie wchodzące i wychodzące — po prostu nie przestrzegają tych samych zasad.

Prostym (ale nieoczywistym) algorytmem geometrii obliczeniowej do określania wypukłości jest sprawdzenie, czy każda trójka kolejnych wierzchołków ma kierunek CCW. Zajmuje to tylko kilka linijek kodu geometrii Pythona (zakładając, że points są podane w kolejności przeciwnej do ruchu wskazówek zegara — jeśli points są w kolejności zgodnej z ruchem wskazówek zegara, będziesz chciał, aby wszystkie trójki były zgodne z ruchem wskazówek zegara):

 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

Wypróbuj to na papierze z kilkoma przykładami. Możesz nawet użyć tego wyniku do zdefiniowania wypukłości. (Aby uczynić rzeczy bardziej intuicyjnymi, zauważ, że krzywa CCW od A -> B -> C odpowiada kątowi mniejszemu niż 180, co jest powszechnie nauczanym sposobem definiowania wypukłości.)

Przecięcie linii

Jako drugi przykład rozważ przecięcie odcinków linii, które można również rozwiązać za pomocą samego 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)

Dlaczego tak jest? Przecięcie odcinków linii można również sformułować jako: mając dany odcinek z punktami końcowymi A i B, czy punkty końcowe C i D innego odcinka leżą po tej samej stronie AB? Innymi słowy, jeśli zakręty z A -> B -> C i A -> B -> D są w tym samym kierunku, segmenty nie mogą się przecinać. Kiedy używamy tego typu języka, staje się jasne, że takim problemem jest chleb z masłem CCW.

Rygorystyczna definicja

Teraz, gdy zasmakowaliśmy w znaczeniu CCW, zobaczmy, jak to jest obliczane. Biorąc pod uwagę punkty 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)

Aby zrozumieć, skąd pochodzi ta definicja, rozważ wektory AB i BC. Jeśli weźmiemy ich iloczyn poprzeczny AB x BC, będzie to wektor wzdłuż osi z. Ale w którym kierunku (tzn. +z lub -z)? Jak się okazuje, jeśli iloczyn krzyżowy jest dodatni, obrót jest przeciwny do ruchu wskazówek zegara; w przeciwnym razie zgodnie z ruchem wskazówek zegara.

Ta definicja będzie wydawać się nieintuicyjna, chyba że naprawdę dobrze rozumiesz algebrę liniową, regułę prawej ręki itp. Ale właśnie dlatego mamy abstrakcję — kiedy myślisz CCW, pomyśl tylko o jej intuicyjnej definicji, a nie o jej obliczeniach. Wartość zostanie natychmiast wyczyszczona.

Moje nurkowanie w geometrii obliczeniowej i programowaniu w Pythonie

Przez ostatni miesiąc pracowałem nad implementacją kilku algorytmów geometrii obliczeniowej w Pythonie. Ponieważ będę się na nich rysował w następnych kilku sekcjach, poświęcę chwilę na opisanie moich aplikacji do geometrii obliczeniowej, które można znaleźć na GitHub.

Uwaga: Moje doświadczenie jest wprawdzie ograniczone. Ponieważ pracuję nad tym od miesięcy, a nie lat, przyjmij moją radę z przymrużeniem oka. To powiedziawszy, wiele się nauczyłem w ciągu tych kilku miesięcy, więc mam nadzieję, że te wskazówki okażą się przydatne.

Algorytm Kirkpatricka

U podstaw mojej pracy leżała implementacja algorytmu Kirkpatricka do lokalizacji punktów. Stwierdzenie problemu byłoby mniej więcej takie: biorąc pod uwagę podpodział planarny (pęczek nienakładających się wielokątów na płaszczyźnie) i punkt P, który wielokąt zawiera P? Na sterydach myśl punkt w wielokącie — zamiast pojedynczego wielokąta, masz ich pełen samolot.

Jako przypadek użycia rozważ stronę internetową. Kiedy użytkownik kliknie myszą, strona internetowa musi jak najszybciej dowiedzieć się, w co kliknął. Czy to był przycisk A? Czy to był link B? Strona internetowa składa się z niezachodzących na siebie wielokątów, więc algorytm Kirkpatricka byłby dobrze przygotowany do pomocy.

Chociaż nie będę omawiał szczegółowo algorytmu, możesz dowiedzieć się więcej tutaj.

Minimalny trójkąt ograniczający

Jako podzadanie zaimplementowałem również algorytm O'Rourke'a do obliczania minimalnego trójkąta obejmującego/ograniczającego (czyli znajdowania najmniejszego trójkąta, który obejmuje wypukły zbiór punktów) w czasie liniowym.

Uwaga: Obliczenie minimalnego trójkąta ograniczającego nie pomaga ani nie szkodzi asymptotycznej wydajności algorytmu Kirkpatricka, ponieważ samo obliczenie jest w czasie liniowym — ale jest przydatne ze względów estetycznych.

Praktyczne porady, zastosowania i wątpliwości

Poprzednie sekcje koncentrowały się na tym, dlaczego geometria obliczeniowa może być trudna do rygorystycznego rozumowania.

W praktyce mamy do czynienia z całą masą obaw.

Pamiętasz CCW? Jako miły segue, zobaczmy jeszcze jedną z jego wielkich zalet: chroni nas przed niebezpieczeństwem błędów zmiennoprzecinkowych.

Błędy zmiennoprzecinkowe: dlaczego CCW jest królem

Na moim kursie geometrii obliczeniowej Bernard Chazelle, ceniony profesor, który opublikował więcej prac, niż jestem w stanie zliczyć, ustanowił zasadę, że nie możemy wspominać o kątach, kiedy próbujemy opisać algorytm lub rozwiązanie.

Czemu? Kąty są bałaganiarskie. Kąty są „brudne”. Kiedy musisz obliczyć kąt, musisz podzielić lub użyć jakiegoś przybliżenia (na przykład wszystkiego, co dotyczy Pi) lub jakiejś funkcji trygonometrycznej.

Kiedy musisz obliczyć kąt w kodzie , prawie zawsze będziesz przybliżać. Odbijesz się z niewielkim stopniem precyzji zmiennoprzecinkowej — co ma znaczenie, gdy testujesz równość. Możesz rozwiązać jakiś punkt na płaszczyźnie za pomocą dwóch różnych metod i oczywiście oczekiwać, że p1.x == p2.x and p1.y == p2.y . Ale w rzeczywistości to sprawdzenie często kończy się niepowodzeniem. Co więcej (i oczywiście), punkty te będą miały różne skróty.

Co gorsza, twój stopień błędu będzie się zwiększał, gdy drobne różnice rozprzestrzenią się w twoich obliczeniach. (Dla niektórych bardziej naukowych przykładów, ten artykuł omawia, co może się nie udać podczas obliczania wypukłego kadłuba lub triangulacji Delaunaya.)

Co więc możemy z tym zrobić?

prawie równe

Częścią problemu geometrii obliczeniowej Pythona jest to, że wymagamy dokładności w świecie, w którym rzeczy rzadko są dokładne. Stanie się to problemem częściej niż podczas obsługi kątów. Rozważ następujące:

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

W rzeczywistości ten kod wyświetli „Błąd!” mniej więcej 70% czasu (empirycznie). Możemy rozwiązać ten problem, nieco bardziej pobłażliwie podając naszą definicję równości; to znaczy poświęcając pewien stopień dokładności.

Jedno podejście, które zastosowałem (i widziałem np. w niektórych modułach OpenCV) polega na zdefiniowaniu dwóch liczb jako równych, jeśli różnią się tylko małą wartością epsilon. W Pythonie możesz mieć:

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

W praktyce jest to bardzo pomocne. Rzadko, jeśli w ogóle, można obliczyć dwa punkty różniące się o mniej niż 1e-5, które w rzeczywistości mają być różnymi punktami. Gorąco polecam zaimplementowanie tego typu nadpisania. Podobne metody można zastosować do linii, na przykład:

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

Oczywiście zaproponowano bardziej zaawansowane rozwiązania. Na przykład szkoła myślenia „dokładnych obliczeń geometrycznych” (opisana w tym artykule) dąży do tego, aby wszystkie ścieżki decyzyjne w programie zależały wyłącznie od znaku jakiegoś obliczenia, a nie jego dokładnej wartości liczbowej, co eliminuje wiele związanych z nim obaw. do obliczeń zmiennoprzecinkowych. Nasze podejście do prawie równości tylko zarysowuje powierzchnię, ale w praktyce często wystarcza.

CCW jest królem

Na wyższym poziomie jest (prawdopodobnie) problematyczne, że nawet definiujemy nasze rozwiązania w kategoriach tak dokładnych wielkości obliczeniowych, jak kąty lub współrzędne punktu. Zamiast zająć się samymi objawami (tj. przemyć błędy zmiennoprzecinkowe za pomocą almostEqual ), dlaczego nie zająć się przyczyną? Rozwiązanie: zamiast myśleć w kategoriach kątów, myśl w kategoriach CCW , co pomoże odrzucić obawy związane z obliczeniami zmiennoprzecinkowymi.

Oto konkretny przykład: powiedzmy, że masz wypukły wielokąt P , wierzchołek v i punkt u poza wielokątem. Jak możesz dowiedzieć się, czy linia uv przecina P powyżej lub poniżej v , czy wcale, w stałym czasie?

Rozwiązanie brutalnej siły (oprócz czasu liniowego, a nie stałego) byłoby problematyczne, ponieważ musiałbyś obliczyć dokładne punkty przecięcia linii.

Jedno z podejść o stałym czasie, które widziałem, obejmuje:

• Obliczanie niektórych kątów za pomocą arctan2 .
• Konwersja tych kątów na stopnie poprzez pomnożenie przez 180/Pi.
• Zbadanie relacji między tymi różnymi kątami.

Na szczęście autor wykorzystał powyższą technikę almostEqual do wygładzenia błędów zmiennoprzecinkowych.

Moim zdaniem lepiej byłoby całkowicie uniknąć problemu błędów zmiennoprzecinkowych. Jeśli poświęcisz kilka minut, aby przyjrzeć się problemowi na papierze, możesz uzyskać rozwiązanie oparte całkowicie na CCW. Intuicja: jeśli wierzchołki sąsiadujące z v są po tej samej stronie uv , to linia się nie przecina; w przeciwnym razie sprawdź, czy u i v są po tej samej stronie linii między sąsiednimi wierzchołkami i, w zależności od wyniku, porównaj ich wysokości.

Oto kod Pythona do testowania przecięcia powyżej v (przecięcie poniżej po prostu odwraca kierunek porównań):

 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

Rozwiązanie nie jest od razu oczywiste gołym okiem, ale jest w języku algorytmu geometrii obliczeniowej: „ta sama strona linii” jest klasycznym elementem tego niezawodnego algorytmu.

Zrobione jest lepsze niż idealne

W literaturze geometrycznej obliczeniowej często występuje sporo czarów związanych z pozornie prostymi operacjami. Daje to wybór: możesz robić rzeczy w trudny sposób, postępując zgodnie z artykułem, który definiuje niewiarygodnie zaawansowane rozwiązanie niezbyt zaawansowanego problemu - lub możesz robić rzeczy w łatwy sposób, z odrobiną brutalnej siły.

Ponownie użyję przykładu: próbkowanie losowego punktu wewnętrznego z dowolnego wielokąta. Innymi słowy, daję ci prosty wielokąt, a ty dajesz mi losowy punkt w jego wnętrzu (równomiernie rozłożony na wielokącie).

Często do testowania wymagane są punkty wewnętrzne. W takim przypadku algorytm geometrii obliczeniowej, który je wytwarza (w granicach rozsądku), nie ma żadnych szczególnych wymagań dotyczących środowiska wykonawczego. Szybkim i brudnym rozwiązaniem, którego wdrożenie zajmuje około 2 minut, byłoby wybranie losowego punktu w polu zawierającym wielokąt i sprawdzenie, czy sam punkt znajduje się w wielokącie.

Na przykład możemy pominąć dwa razy i znaleźć prawidłową próbkę tylko w trzecim punkcie:

Oto kod:

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

Nazywa się to próbkowaniem odrzucenia : wybieraj losowe punkty, aż jeden z nich spełni twoje kryteria. Chociaż znalezienie punktu spełniającego twoje kryteria może wymagać kilku próbek, w praktyce różnica będzie nieistotna dla twojego zestawu testów. Po co więc pracować ciężej? Podsumowując: nie bój się jechać brudną drogą, gdy wymaga tego okazja.

Przy okazji: jeśli potrzebujesz dokładnego algorytmu losowego próbkowania, jest tutaj sprytny, który zaimplementowałem poniżej. Istota tego:

1. Wykonaj triangulację swojego wielokąta (tj. podziel go na trójkąty).
2. Wybierz trójkąt z prawdopodobieństwem proporcjonalnym do jego powierzchni.
3. Weź losowy punkt z wybranego trójkąta (operacja w czasie stałym).

Zauważ, że ten algorytm wymaga triangulacji wielokąta, co natychmiast nakłada na algorytm inne powiązanie w czasie wykonywania, a także konieczność posiadania biblioteki do triangulacji dowolnych wielokątów (ja użyłem poly2tri z powiązaniami Pythona).

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

Mamy nadzieję, że dodatkowy wysiłek wynika z kodu. Pamiętaj: jak mówią na Facebooku „zrobione jest lepsze niż doskonałe”. To samo dotyczy problemów z geometrią obliczeniową.

Testy wizualne i automatyczne

Ponieważ wiele problemów, nad którymi pracujesz w geometrii obliczeniowej, jest definiowanych w kategoriach łatwo widocznych jakości lub ilości, testowanie wizualne jest szczególnie ważne – choć same w sobie niewystarczające. Idealny zestaw testów będzie zawierał kombinację testów wizualnych i losowych testów automatycznych.

Ponownie postępujemy według przykładu. Rozważ przetestowanie naszej implementacji algorytmu Kirkpatricka. W jednym kroku algorytm musi związać dany wielokąt trójkątem i dokonać triangulacji obszaru między wielokątem a trójkątem zewnętrznym. Oto wizualny przykład, w którym ciągła zielona linia definiuje początkowy wielokąt, a linie przerywane określają obszar triangulacji:

Potwierdzenie, że ta triangulacja została wykonana poprawnie, jest bardzo trudne do zweryfikowania za pomocą kodu, ale jest natychmiast widoczne dla ludzkiego oka. Uwaga: Gorąco sugeruję użycie Matplotlib do pomocy w testach wizualnych — tutaj jest fajny przewodnik.

Później będziemy chcieli zweryfikować, czy algorytm poprawnie lokalizuje punkty. Losowe, zautomatyzowane podejście polegałoby na wygenerowaniu wielu punktów wewnętrznych dla każdego wielokąta i upewnieniu się, że zwracamy żądany wielokąt. W kodzie:

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

Moglibyśmy wtedy użyć metody runLocator na różnych zestawach wielokątów, dając nam dobrze zróżnicowany zestaw testów.

Rozwiązania typu open source

Geometria obliczeniowa ma ładny zestaw bibliotek i rozwiązań typu open source, dostępnych niezależnie od wybranego języka programowania (chociaż biblioteki C ++ wydają się pojawiać nieproporcjonalnie).

Korzyści płynące z korzystania z istniejących rozwiązań open source (tak jak w przypadku obliczeń naukowych w Pythonie) są dobrze znane i szeroko omawiane, więc nie będę o tym tutaj mówić. Pomyślałem jednak, że wspomnę o kilku zasobach skoncentrowanych na Pythonie, które okazały się przydatne:

• poly2tri: świetna biblioteka do szybkich triangulacji wielokątów. Obsługuje również (a to często kluczowe) wielokąty z otworami . Napisany w C++, poly2tri posiada również powiązania Pythona i był dość łatwy do uruchomienia. Zobacz moją metodę triangulate powyżej, aby poznać smak wywołań funkcji.
• scipy.spatial: zawiera funkcje do obliczania wypukłych kadłubów, triangulacji Delaunaya i innych. Szybki (jak zawsze), niezawodny itp. Uwaga: Przydatne jest użycie własnego typu danych Point z metodą toNumpy : def np(self): return [self.x, self.y] . Wtedy spokojnie mógłbym wywołać metody scipy.spatial, np.: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV: biblioteka wizyjna o otwartym kodzie źródłowym zawiera kilka ładnych, samodzielnych modułów geometrii obliczeniowej. W szczególności przez jakiś czas korzystałem z funkcji minimalnego trójkąta zamykającego, zanim sam ją zaimplementowałem.

Wniosek

Mam nadzieję, że ten post dał ci smak piękna geometrii obliczeniowej jako programisty Pythona, tematu bogatego w fascynujące problemy i równie fascynujące zastosowania.

W praktyce implementacje geometrii obliczeniowej stanowią wyjątkowe wyzwania, które zachęcą Cię do ćwiczenia nowych i ekscytujących umiejętności rozwiązywania problemów.

Jeśli chcesz dowiedzieć się więcej lub masz do mnie jakieś pytania, skontaktuj się ze mną pod adresem [email protected].