Problem polega na tym, aby dowiedzieć się, jak zgiąć łuki, aby zwiększyć ich rozdzielczość wizualną.
Oto jedno rozwiązanie (spośród wielu możliwych). Rozważmy wszystkie łuki pochodzące ze wspólnego pochodzenia. Łuki są tutaj najbardziej zatłoczone. Aby je najlepiej rozdzielić, ułóżmy je tak, aby rozkładały się pod równymi kątami . Problem polega na tym, że narysujemy odcinki linii prostej od początku do miejsc docelowych, ponieważ zwykle będą skupienia miejsc docelowych w różnych kierunkach. Wykorzystajmy naszą swobodę do wyginania łuków, aby możliwie równomiernie rozmieszczać odchodzące kąty.
Dla uproszczenia użyjmy łuków kołowych na mapie. Naturalną miarą „zgięcia” łuku od punktu y do punktu x jest różnica między jego łożyskiem w punkcie y a łożyskiem bezpośrednio od y do x . Taki łuk jest sektorem koła, na którym leżą oba y i x ; geometria elementarna pokazuje, że kąt gięcia jest równy połowie kąta zawarcia w łuku.
Aby opisać algorytm, potrzebujemy trochę więcej notacji. Niech y będzie punktem początkowym (zgodnie z rzutem na mapie) i niech x_1 , x_2 , ..., x_n będą punktami docelowymi. Zdefiniuj a_i jako namiar od y do x_i , i = 1, 2, ..., n .
Na wstępie przyjmijmy, że łożyska (wszystkie od 0 do 360 stopni) są w porządku rosnącym: wymaga to obliczenia łożysk, a następnie ich posortowania; oba są prostymi zadaniami.
Idealnie byłoby, gdyby łożyska łuków były równe 360 / n , 2 * 360 / n itd. W stosunku do niektórych łożysk początkowych. Różnice między pożądanymi a rzeczywistymi łożyskami są zatem równe i * 360 / n - a_i plus łożysko początkowe, a0 . Największa różnica to maksimum tych n różnic, a najmniejsza różnica to ich minimum. Ustawmy a0 tak, aby znajdowało się w połowie drogi między wartością maksymalną a minimalną; jest to dobry kandydat na łożysko początkowe, ponieważ minimalizuje maksymalną liczbę zgięć, które wystąpią . W związku z tym zdefiniuj
b_i = i * 360 / n - a0 - a_i:
to jest gięcie do użycia .
Narysowanie okrągłego łuku od y do x, który obejmuje kąt 2 b_i, polega na elementarnej geometrii , więc pominę szczegóły i przejdę od razu do przykładu. Oto ilustracje rozwiązań dla 64, 16 i 4 losowych punktów umieszczonych na prostokątnej mapie
Jak widać, rozwiązania wydają się ładniejsze wraz ze wzrostem liczby punktów docelowych. Rozwiązanie dla n = 4 wyraźnie pokazuje, w jaki sposób łożyska są równomiernie rozmieszczone, ponieważ w tym przypadku odstęp wynosi 360/4 = 90 stopni i oczywiście ten odstęp jest dokładnie osiągnięty.
To rozwiązanie nie jest idealne: prawdopodobnie możesz zidentyfikować kilka łuków, które można ręcznie ulepszyć, aby poprawić grafikę. Ale to nie zrobi okropnej roboty i wydaje się, że to naprawdę dobry początek.
Algorytm ma tę zaletę, że jest prosty: najbardziej skomplikowana część polega na sortowaniu miejsc docelowych według ich położenia.
Kodowanie
Nie znam PostGIS, ale być może kod użyty do narysowania przykładów może służyć jako przewodnik dla implementacji tego algorytmu w PostGIS (lub innym GIS).
Za pseudokod należy uważać następujące (ale Mathematica go wykona :-). (Jeśli ta strona obsługuje TeX, podobnie jak matematyka, statystyki i TCS, mógłbym to uczynić o wiele bardziej czytelnym.) Notacja obejmuje:
- W nazwach zmiennych i funkcjach rozróżniana jest wielkość liter.
- [Alpha] jest małą grecką postacią. ([Pi] ma wartość, którą Twoim zdaniem powinna mieć.)
- x [[i]] to element i tablicy x (indeksowany od 1).
- f [a, b] stosuje funkcję f do argumentów a i b. Funkcje w odpowiednim przypadku, takie jak „Min” i „Tabela”, są zdefiniowane w systemie; funkcje z początkową małą literą, takie jak „kąty” i „przesunięcie”, są zdefiniowane przez użytkownika. Komentarze wyjaśniają wszelkie niejasne funkcje systemu (takie jak „Arg”).
- Tabela [f [i], {i, 1, n}] tworzy tablicę {f [1], f [2], ..., f [n]}.
- Okrąg [o, r, {a, b}] tworzy łuk koła wyśrodkowany na o o promieniu r od kąta a do kąta b (oba w radianach przeciwnie do ruchu wskazówek zegara od wschodu).
- Porządkowanie [x] zwraca tablicę indeksów posortowanych elementów x. x [[Zamawianie [x]]] to posortowana wersja x. Gdy y ma taką samą długość jak x, y [[Kolejność [x]]] sortuje y równolegle do x.
Wykonalna część kodu jest na szczęście krótka - mniej niż 20 wierszy - ponieważ ponad połowa z nich to albo deklaratywne obciążenie, albo komentarze.
Narysuj mape
zto lista miejsc docelowych i ypochodzenie.
circleMap[z_List, y_] :=
Module[{\[Alpha] = angles[y,z], \[Beta], \[Delta], n},
(* Sort the destinations by bearing *)
\[Beta] = Ordering[\[Alpha]];
x = z[[\[Beta] ]]; (* Destinations, sorted by bearing from y *)
\[Alpha] = \[Alpha][[\[Beta]]]; (* Bearings, in sorted order *)
\[Delta] = offset[\[Alpha]];
n = Length[\[Alpha]];
Graphics[{(* Draw the lines *)
Gray, Table[circle[y, x[[i]],2 \[Pi] i / n + \[Delta] - \[Alpha][[i]]],
{i, 1, Length[\[Alpha]]}],
(* Draw the destination points *)
Red, PointSize[0.02], Table[Point[u], {u, x}]
}]
]
Utwórz łuk kołowy od punktu xdo punktu, yzaczynając od kąta \[Beta]względem łożyska x -> y.
circle[x_, y_, \[Beta]_] /; -\[Pi] < \[Beta] < \[Pi] :=
Module[{v, \[Rho], r, o, \[Theta], sign},
If[\[Beta]==0, Return[Line[{x,y}]]];
(* Obtain the vector from x to y in polar coordinates. *)
v = y - x; (* Vector from x to y *)
\[Rho] = Norm[v]; (* Length of v *)
\[Theta] = Arg[Complex @@ v]; (* Bearing from x to y *)
(* Compute the radius and center of the circle.*)
r = \[Rho] / (2 Sin[\[Beta]]); (* Circle radius, up to sign *)
If[r < 0, sign = \[Pi], sign = 0];
o = (x+y)/2 + (r/\[Rho]) Cos[\[Beta]]{v[[2]], -v[[1]]}; (* Circle center *)
(* Create a sector of the circle. *)
Circle[o, Abs[r], {\[Pi]/2 - \[Beta] + \[Theta] + sign, \[Pi] /2 + \[Beta] + \[Theta] + sign}]
]
Oblicz łożyska od początku do listy punktów.
angles[origin_, x_] := Arg[Complex@@(#-origin)] & /@ x;
Oblicz średnicę resztek zestawu łożysk.
xto lista łożysk w posortowanej kolejności. Idealnie, x [[i]] ~ 2 [Pi] i / n.
offset[x_List] :=
Module[
{n = Length[x], y},
(* Compute the residuals. *)
y = Table[x[[i]] - 2 \[Pi] i / n, {i, 1, n}];
(* Return their midrange. *)
(Max[y] + Min[y])/2
]
