Jak połączyć złożone wielokąty?

Biorąc pod uwagę dwa wielokąty:

POLYGON((1 0, 1 8, 6 4, 1 0))
POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

Jak mogę obliczyć związek (połączony wielokąt)?

Przykład Dave'a używa serwera SQL do utworzenia unii, ale ja muszę to zrobić w kodzie. Szukam wzoru matematycznego lub przykładu kodu w dowolnym języku, który ujawnia rzeczywistą matematykę. Próbuję stworzyć mapy, które dynamicznie łączą kraje w regiony. Zadałem tutaj pokrewne pytanie: Grupowanie kształtów geograficznych

To jest bardzo dobre pytanie. Zaimplementowałem ten sam algorytm na c # jakiś czas temu. Algorytm konstruuje wspólny kontur dwóch wielokątów (tj. Konstruuje sumę bez dziur). Tutaj jest.

Krok 1. Utwórz wykres opisujący wielokąty.

Dane wejściowe: pierwszy wielokąt (n punktów), drugi wielokąt (m punktów). Wyjście: wykres. Wierzchołek - wielokąt będący punktem przecięcia.

Powinniśmy znaleźć skrzyżowania. Przejdź przez wszystkie boki wielokątów w obu wielokątach [O (n * m)] i znajdź wszystkie przecięcia.

• Jeśli przecięcie nie zostanie znalezione, po prostu dodaj wierzchołki i połącz je z krawędzią.

• Jeśli zostaną znalezione jakieś przecięcia, posortuj je według długości do ich punktu początkowego, dodaj wszystkie wierzchołki (początek, koniec i przecięcia) i połącz je (już w kolejności posortowanej) z krawędzią.

Krok 2. Sprawdź skonstruowany wykres

Jeśli nie znaleźliśmy żadnych punktów przecięcia podczas budowania wykresu, mamy jeden z następujących warunków:

1. Polygon1 zawiera polygon2 - zwraca polygon1
2. Polygon2 zawiera polygon1 - zwraca polygon2
3. Polygon1 i polygon2 nie przecinają się. Zwróć polygon1 AND polygon2.

Krok 3. Znajdź lewy dolny wierzchołek.

Znajdź minimalne współrzędne xiy (minx, miny). Następnie znajdź minimalną odległość między (minx, miny) a punktami wielokąta. Ten punkt będzie lewym dolnym punktem.

Krok 4. Skonstruuj wspólny kontur.

Zaczynamy przesuwać wykres od lewego dolnego punktu i kontynuujemy, aż wrócimy do niego. Na początku zaznaczamy wszystkie krawędzie jako nieodwiedzone. W każdej iteracji powinieneś wybrać następny punkt i oznaczyć go jako odwiedzony.

Aby wybrać następny punkt, wybierz krawędź o maksymalnym kącie wewnętrznym w kierunku przeciwnym do ruchu wskazówek zegara.

Obliczam dwa wektory: wektor1 dla bieżącej krawędzi i wektor2 dla każdej kolejnej nieodwiedzonej krawędzi (jak pokazano na rysunku).

Dla wektorów obliczam:

1. Iloczyn skalarny (iloczyn skalarny). Zwraca wartość związaną z kątem między wektorami.
2. Iloczyn wektorowy (iloczyn wektorowy). Zwraca nowy wektor. Jeśli współrzędna z tego wektora jest dodatnia, iloczyn skalarny daje mi kąt prosty w kierunku przeciwnym do ruchu wskazówek zegara. W przeciwnym razie (współrzędna z jest ujemna), obliczam kąt między wektorami jako 360 - kąt z iloczynu skalarnego.

W rezultacie otrzymuję krawędź (i odpowiadający jej następny wierzchołek) z maksymalnym kątem.

Dodaję do listy wyników każdy przekazany wierzchołek. Lista wyników to wielokąt sumujący.

Uwagi

1. Ten algorytm pozwala nam łączyć wiele wielokątów - aby zastosować je iteracyjnie z parami wielokątów.
2. Jeśli masz ścieżkę składającą się z wielu krzywych i linii Beziera, powinieneś najpierw spłaszczyć tę ścieżkę.

Jest to trudny, ale dobrze zrozumiany temat, który często nosi nazwę „uregulowane operacje boolowskie na wielokątach”. Możesz spojrzeć na tę odpowiedź MathOverflow , która zawiera poniższy rysunek (z biblioteki wycinków Alana Murty ), z różowym związkiem połączonym z OP :

Musisz określić, które punkty znajdują się w środku . Po usunięciu tych punktów można wstawić jeden zestaw punktów „zewnętrznych” do drugiego. Twoje punkty wstawiania (np. Tam, gdzie masz strzałkę na obrazku po prawej stronie) to miejsca, w których trzeba było usunąć punkty ze zbiorów wejściowych.

Dobre pytanie! Nigdy wcześniej tego nie próbowałem, ale teraz spróbuję.

Po pierwsze: musisz wiedzieć, gdzie te dwa kształty się pokrywają. Aby to zrobić, możesz spojrzeć na każdą krawędź w wielokącie A i zobaczyć, gdzie przecina się i krawędź w wielokącie B. W tym przykładzie powinny istnieć dwa punkty przecięcia.

Następnie: nadaj kształt związku. Możesz wziąć wszystkie wierzchołki w A i B, a także punkty przecięcia, a następnie wykluczyć wierzchołki zawarte w ostatecznym kształcie. Aby znaleźć te punkty, wygląda na to, że możesz znaleźć dowolny wierzchołek A znajdujący się wewnątrz B i dowolny wierzchołek B znajdujący się wewnątrz A.

Spróbuj gpc .

Rozwiązanie, które widziałem przy użyciu drzew BSP, jest opisane tutaj .

Zasadniczo opisuje przecięcie jako sumę krawędzi wielokąta A, które znajdują się wewnątrz wielokąta B (w tym krawędzi częściowych i obliczonych przy użyciu drzewa BSP ). Następnie możesz zdefiniować A  /  B jako ~ (~ A  / \ ~ B ), gdzie ~ oznacza odwrócenie uzwojenia wielokąta, / oznacza związek, a / \ oznacza przecięcie.

To bardzo stare pytanie, ale funkcja Union_ z Boost zadziałała dla mnie.

Zobacz ten fragment poniżej:

#include <iostream>
#include <vector>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>

#include <boost/foreach.hpp>


int main()
{
    typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > polygon;

    polygon green, blue;

    boost::geometry::read_wkt(
        "POLYGON((0 0, 0 10, 10 10, 10 0, 0 0))", green);

    boost::geometry::read_wkt(
        "POLYGON((5 5, 5 15, 15 15, 15 5, 5 5))", blue);

    std::vector<polygon> output;
    boost::geometry::union_(green, blue, output);

    int i = 0;
    std::cout << "green || blue:" << std::endl;
    BOOST_FOREACH(polygon const& p, output)
    {
        std::cout << i++ << ": " << boost::geometry::area(p) << std::endl;

        for (int i = 0; i < p.outer().size(); i++)
        {
            std::cout << p.outer().at(i).x() << " " << p.outer().at(i).y() << std::endl;
        }
    }



    return 0;
}

Podczas grupowania krajów mam nadzieję, że nie będzie się pokrywać - możesz wziąć dość naiwny algorytm, który szuka wspólnych wierzchołków - prostym widokiem byłoby iterowanie punktów na jednym wielokącie i sprawdzenie, czy znajduje się on na którymkolwiek z innych wielokątów i dzieli ten sam następny lub poprzedni punkt, aby sprawdzić, czy jest zgodność. Następnie po prostu usuń wspólny wierzchołek, aby utworzyć swój związek

Musiałem dziś rozwiązać ten sam problem i znalazłem rozwiązanie za pomocą tej biblioteki: http://www.cs.man.ac.uk/~toby/alan/software/ .

Lista zawiera wiele implementacji językowych, w tym Java, Obj-C, C #, Lua, Python i inne.

Napotkałem ten sam problem i rozwiązałem go w następujący sposób

Opakowanie Cython do tłumaczenia C ++ biblioteki Clipper Angusa Johnsona (wersja 6.4.2) https://github.com/fonttools/pyclipper

pc = pyclipper.Pyclipper()
def get_poly_union(polygons):
    pc.AddPaths(polygons, pyclipper.PT_SUBJECT, True)
    solution = pc.Execute(pyclipper.CT_UNION, pyclipper.PFT_NONZERO, pyclipper.PFT_NONZERO)
    return solution[0]

print_image = image.copy()
solution = get_poly_union(polygons_array) 
#polygons_array=[polygon,polygon,polygon, ...,polygon] and polygon=[point,point,point...,point]

cv2.drawContours(print_image, [np.asarray(solution)], -1, (0, 255, 0), 2)

plt.imshow(print_image)