Jak „nadmuchać” wielokąt? To znaczy, chcę zrobić coś podobnego do tego:
Wymagane jest, aby wszystkie krawędzie / punkty nowego (napompowanego) wielokąta znajdowały się w tej samej stałej odległości od starego (oryginalnego) wielokąta (na przykładowym obrazie nie są, ponieważ wtedy musiałby używać łuków dla zawyżonych wierzchołków, ale załóżmy na razie o tym zapomnij;)).
Matematyczny termin na to, czego szukam, to tak naprawdę wewnętrzne / zewnętrzne tworzenie wielokątów . +1 do balinta za wskazanie tego. Alternatywną nazwą jest buforowanie wielokątów .
Wyniki mojego wyszukiwania:
Oto kilka linków:
Odpowiedzi:
Pomyślałem, że mógłbym krótko wspomnieć o własnej bibliotece przycinania i kompensacji wielokątów - Clipper .
Chociaż Clipper jest zaprojektowany przede wszystkim do operacji obcinania wielokątów, wykonuje również kompensację wielokątów. Biblioteka jest darmowym oprogramowaniem typu open source napisanym w Delphi, C ++ i C # . Ma bardzo nieobciążoną licencję Boost, która pozwala na korzystanie z niej zarówno w darmowych, jak i komercyjnych aplikacjach bez opłat.
Przesunięcie wielokąta można wykonać przy użyciu jednego z trzech stylów przesunięcia - kwadratowego, okrągłego i mitered.
źródło
Wielokąt, którego szukasz, nazywa się wielokątem przesuniętym do wewnątrz / na zewnątrz w geometrii obliczeniowej i jest ściśle związany z prostym szkieletem .
Oto kilka odsuniętych wielokątów dla skomplikowanego wielokąta:
A to jest prosty szkielet innego wielokąta:
Jak wskazano również w innych komentarzach, w zależności od tego, jak daleko planujesz „nadmuchać / spuścić powietrze” z wielokąta, możesz uzyskać różne połączenia dla wyjścia.
Z punktu widzenia obliczeń: gdy masz prosty szkielet, powinieneś być w stanie stosunkowo łatwo zbudować przesunięte wielokąty. Biblioteka CGAL typu open source i (darmowa dla niekomercyjnych) zawiera pakiet implementujący te struktury. Zobacz ten przykład kodu, aby obliczyć przesunięte wielokąty za pomocą CGAL.
Podręcznik pakietu powinien dać dobry punkt wyjścia do tego, jak zbudować te struktury, nawet jeśli nie zamierzasz używać CGAL, i zawiera odniesienia do artykułów z definicjami matematycznymi i właściwościami:
Podręcznik CGAL: Prosty szkielet 2D i przesunięcie wielokąta
źródło
Do tego typu rzeczy zwykle używam JTS . Dla celów demonstracyjnych stworzyłem ten jsFiddle, który używa JSTS (port JavaScript JTS). Musisz tylko przekonwertować współrzędne, które masz na współrzędne JSTS:
Wynik jest mniej więcej taki:
Informacje dodatkowe : Zazwyczaj używam tego rodzaju pompowania / opróżniania (nieco zmodyfikowanego do moich celów) do ustawiania granic z promieniem na wielokątach rysowanych na mapie (z mapami Ulotki lub Google). Po prostu konwertujesz pary (lat, lng) na współrzędne JSTS i wszystko inne jest takie samo. Przykład:
źródło
Brzmi dla mnie tak, jak chcesz:
d
od „lewej” starej.Powstały wielokąt leży w wymaganej odległości od starego wielokąta „wystarczająco daleko” od wierzchołków. W pobliżu wierzchołka zbiór punktów w odległości
d
od starego wielokąta nie jest, jak mówisz, wielobokiem, więc podany wyżej wymóg nie może być spełniony.Nie wiem, czy ten algorytm ma nazwę, przykładowy kod w Internecie czy diabelską optymalizację, ale myślę, że opisuje to, czego chcesz.
źródło
W świecie GIS do tego zadania używa się buforowania ujemnego: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf
Biblioteka WST powinien zrobić to za Ciebie. Zobacz dokumentację operacji buforowej: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html
Aby zapoznać się z ogólnym przeglądem, zobacz także Przewodnik programisty: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf
źródło
Każda linia powinna podzielić płaszczyznę na „wewnątrz” i „kontur”; możesz to sprawdzić za pomocą zwykłej metody produktu wewnętrznego.
Przesuń wszystkie linie na zewnątrz o pewną odległość.
Rozważ całą parę sąsiednich linii (linii, a nie segmentu linii), znajdź przecięcie. To są nowe wierzchołki.
Oczyść nowy wierzchołek, usuwając wszystkie przecinające się części. - mamy tu kilka spraw
(a) Przypadek 1:
jeśli wydasz je o jeden, otrzymasz:
7 i 4 pokrywają się. Jeśli to zobaczysz, usuniesz ten punkt i wszystkie punkty pomiędzy.
(b) przypadek 2
jeśli wydasz to na dwa, masz to:
aby rozwiązać ten problem, dla każdego segmentu linii należy sprawdzić, czy pokrywa się on z późniejszymi segmentami.
(c) przypadek 3
wydatki przez 1. jest to bardziej ogólny przypadek dla przypadku 1.
(d) przypadek 4
taki sam jak przypadek 3, ale wydatki o dwa.
Właściwie, jeśli potrafisz obsłużyć przypadek 4. Wszystkie pozostałe przypadki są tylko specjalnymi przypadkami z pewnym nakładaniem się linii lub wierzchołków.
Aby zrobić przypadek 4, trzymasz stos wierzchołków .. naciskasz, gdy widzisz linie nakładające się na drugą linię, pisz ją, gdy dostajesz drugą linię. - dokładnie tak, jak robisz w wypukłym kadłubie.
źródło
Oto alternatywne rozwiązanie, sprawdź, czy bardziej Ci się to podoba.
Wykonaj triangulację , nie musi to być delaunay - wystarczyłaby każda triangulacja.
Napompuj każdy trójkąt - powinno to być trywialne. jeśli przechowujesz trójkąt w kolejności przeciwnej do ruchu wskazówek zegara, po prostu przesuń linie na prawą stronę i wykonaj skrzyżowanie.
Scal je za pomocą zmodyfikowanego algorytmu przycinania Weiler-Atherton
źródło
Ogromne podziękowania dla Angusa Johnsona za jego bibliotekę maszynki do strzyżenia. Istnieją dobre próbki kodu do robienia wycinania na stronie głównej maszynki do strzyżenia pod adresem http://www.angusj.com/delphi/clipper.php#code, ale nie widziałem przykładu przesunięcia wielokąta. Pomyślałem więc, że może przyda się komuś, jeśli opublikuję mój kod:
źródło
Jedno dodatkowe opcją jest użycie boost :: wielokąta - dokumentacja jest nieco brakuje, ale należy zauważyć, że metody
resize
ibloat
, a także przeciążony+=
operator, które faktycznie realizują buforowanie. Na przykład zwiększenie wielkości wielokąta (lub zestawu wielokątów) o pewną wartość może być tak proste, jak:źródło
+=
z zestawem wielokątów , a nie z pojedynczymi wielokątami. Wypróbuj ze std :: wektorem wielokątów. (Oczywiście wektor musi zawierać tylko jeden wielokąt).Na podstawie porady @ JoshO'Brian wydaje się, że
rGeos
pakiet wR
języku implementuje ten algorytm. ZobaczyćrGeos::gBuffer
.źródło
Istnieje kilka bibliotek, z których można korzystać (nadaje się również do zestawów danych 3D).
Można również znaleźć odpowiednie publikacje dla tych bibliotek, aby bardziej szczegółowo zrozumieć algorytmy.
Ten ostatni ma najmniej zależności i jest samowystarczalny i może czytać w plikach .obj.
Najlepsze życzenia, Stephan
źródło
Używam prostej geometrii: wektorów i / lub trygonometrii
W każdym rogu znajdź wektor środkowy i kąt środkowy. Wektor środkowy jest średnią arytmetyczną dwóch wektorów jednostkowych określonych przez krawędzie narożnika. Kąt środkowy to połowa kąta zdefiniowanego przez krawędzie.
Jeśli potrzebujesz rozszerzyć (lub skurczyć) swój wielokąt o ilość d z każdej krawędzi; powinieneś wyjść (in) o kwotę d / sin (midAngle), aby uzyskać nowy punkt narożny.
Powtórz to dla wszystkich rogów
*** Uważaj na swój kierunek. Wykonaj test CounterClockWise przy użyciu trzech punktów określających narożnik; aby dowiedzieć się, w którą stronę można wyjść lub wejść.
źródło