Algorytm napełniania / opróżniania (kompensowania, buforowania) wielokątów

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:

• Badanie strategii offsetu wielokąta
• Przesunięcie wielokąta, PROBLEM
• Buforowanie danych wielokąta

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.

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

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:

function vectorCoordinates2JTS (polygon) {
  var coordinates = [];
  for (var i = 0; i < polygon.length; i++) {
    coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y));
  }
  return coordinates;
}

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:

Brzmi dla mnie tak, jak chcesz:

• Zaczynając od wierzchołka, skieruj twarz w kierunku przeciwnym do ruchu wskazówek zegara wzdłuż sąsiedniej krawędzi.
• Zastąp krawędź nową, równoległą krawędzią umieszczoną w pewnej odległości dod „lewej” starej.
• Powtórz dla wszystkich krawędzi.
• Znajdź przecięcia nowych krawędzi, aby uzyskać nowe wierzchołki.
• Wykryj, czy zostałeś skrzyżowanym wielokątem i zdecyduj, co z tym zrobić. Prawdopodobnie dodaj nowy wierzchołek na skrzyżowaniu i pozbądź się starych. Nie jestem pewien, czy jest lepszy sposób na wykrycie tego, niż po prostu porównanie każdej pary nieprzylegających krawędzi, aby sprawdzić, czy ich przecięcie leży między obiema parami wierzchołków.

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 dod 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.

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

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:

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

jeśli wydasz je o jeden, otrzymasz:

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 i 4 pokrywają się. Jeśli to zobaczysz, usuniesz ten punkt i wszystkie punkty pomiędzy.

(b) przypadek 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

jeśli wydasz to na dwa, masz to:

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

aby rozwiązać ten problem, dla każdego segmentu linii należy sprawdzić, czy pokrywa się on z późniejszymi segmentami.

(c) przypadek 3

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

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.

Oto alternatywne rozwiązanie, sprawdź, czy bardziej Ci się to podoba.

1. Wykonaj triangulację , nie musi to być delaunay - wystarczyłaby każda triangulacja.

2. 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.

3. Scal je za pomocą zmodyfikowanego algorytmu przycinania Weiler-Atherton

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:

    public static List<Point> GetOffsetPolygon(List<Point> originalPath, double offset)
    {
        List<Point> resultOffsetPath = new List<Point>();

        List<ClipperLib.IntPoint> polygon = new List<ClipperLib.IntPoint>();
        foreach (var point in originalPath)
        {
            polygon.Add(new ClipperLib.IntPoint(point.X, point.Y));
        }

        ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset();
        co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon);

        List<List<ClipperLib.IntPoint>> solution = new List<List<ClipperLib.IntPoint>>();
        co.Execute(ref solution, offset);

        foreach (var offsetPath in solution)
        {
            foreach (var offsetPathPoint in offsetPath)
            {
                resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y)));
            }
        }

        return resultOffsetPath;
    }

Jedno dodatkowe opcją jest użycie boost :: wielokąta - dokumentacja jest nieco brakuje, ale należy zauważyć, że metody resizei bloat, 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:

poly += 2; // buffer polygon by 2

Na podstawie porady @ JoshO'Brian wydaje się, że rGeospakiet w Rjęzyku implementuje ten algorytm. Zobaczyć rGeos::gBuffer.

Istnieje kilka bibliotek, z których można korzystać (nadaje się również do zestawów danych 3D).

1. https://github.com/otherlab/openmesh
2. https://github.com/alecjacobson/nested_cages
3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

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

Używam prostej geometrii: wektorów i / lub trygonometrii

1. 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.

2. 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.

3. 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ść.