Mam baze powiedzmy kilka tysiecy wspolrzednych geograficznych (moga byc rozmieszczone po calym swiecie) i teraz za pomoca tych danych chcialbym zrobic cos jak izotermy - obszary w ktorych tych punkcikow jest najwiecej chcialbym laczyc w wielokaty i pozniej w zaleznosci od nasycenia ilosci punktow w danym obszarze ustawlibym wybranemu wielokatawi odpowiedni kolor. Problemem jest dla mnie algorytm generowania tych wielokatow za pomoca posiadanych danych - macie jakies sugestie, znacie jakies algorytmy, ktore moglyby mi pomoc?
0
1
Chciałbyś takie "grupy punktów" otaczać wielokątem? Algorytm szukania otoczki wypukłej.
1
@Shalom - nie wydaje mi się, ale kto wie ;]
@sirkruk - mógłbyś doprecyzować pytanie? Rozumiem że rzucasz jakieś punkty na mapę i tam gdzie jest dużo punktów jest wyższa temperatura. Następnie wyznaczasz temperaturę w każdym punkcie i rysujesz izotermy.
Pytanie jest dość nieprecyzyjne, bo to można rozumieć (gdzie przebiegają te izolinie? ile ich?) na wiele sposobów a do algorytmu trzeba precyzyjnej definicji ;P
No ale mam dwie propozycję, zewnętrzną i wewnętrzną (z braku lepszych nazw).
Opcja wewnętrzna - dzielisz sobie obszar na jakieś wielokąty (najprościej po prostu kwadraty ale to dowolne). Następnie zliczasz ile punktów leży w każdym wielokącie i rysujesz izolinie otaczające kwadraty z podobną ilością punktów. Do zastosowania jeśli masz docelowo dużo punktów na małym obszarze (typu np. 100000). Zaletą jest szybkość, wadą duża potrzebna ilość punktów i mała dokładność.
Taki marny rysunek próbujący przekazać to co mam na myśli:
Opcja zewnętrzna - ustalasz funkcję przypisującą wartość dla odległości, po czym obliczasz wartość w każdym punkcie w wymaganej rozdzielczości (ew. obliczasz w pewnej liczbie punktów i interpolujesz. Do zastosowania jeśli masz mało punktów na dość dużym obszarze. Zaletą jest relatywnie mała potrzebna do jako-tako działania ilość punktów, wadą czasochłonność (bez jakiegoś kd-drzewa czy chociażby regular gridu się nie obejdzie).
Kolejny katastrofalny rysunek, mam antytalent do grafiki (szczególnie jeśli nie może wyrenderować za mnie komputer):
Przepraszam urażonych za katastrofalną jakość posta i obrazków, na usprawiedliwienie dodaję że jest 4 w nocy
0
Dzieki, to czego potrzebuje jest wlasnie polaczeniem algorytmu szukania otoczki wypuklej i pierwszego algorytmu z drugiej odpowiedzi.
0
Jest na to jeszcze jeden sposób:
- Tworzysz dwuwymiarową tablicę liczb o rozmiarze odpowiadającym rozdzielczości przyszłych isoterm.
- Wypełniasz tablice zerami
- Dla każdego punktu - do komórki odpowiadającej współrzędnym punktu dodajesz duża liczbę np 100000 (kilka punktów mogą trafić do tej samej komórki)
- Dokonujesz rozmazywania
Rozmazywanie:
W drugiej tablicę takiego samego rozmiaru dla każdego elementu tablicy wpisujesz średnią ważoną z okolicznych elementów.
Czyli dla elementu T'(x,y) obliczasz średnią ważoną z T(x-1,y-1),T(x,y-1),T(x+1,y-1),T(x-1,y),T(x,y),T(x+1,y),T(x-1,y+1),T(x,y+1),T(x+1,y+1)
Wagi odpowiednio:
4 8 4
8 10 8
4 8 4
Dokonujesz kilka przebiegów rozmazywania.
Znajdujesz Min i Max w rozmazanej tablice, dzielisz to na odpowiednia ilość przedziałów.
W całej tablice zamieniasz liczbę z pierwszego przedziału na 1, z drugiego na 2, itd.
Izotermy idą wzdłuż granic wyznaczonych liczbami.