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
Odpowiedzi:
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.
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ą.
Jeśli nie znaleźliśmy żadnych punktów przecięcia podczas budowania wykresu, mamy jeden z następujących warunków:
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.
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:
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.
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.
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)