Algoritmus pro výpočet vzdáleností od určité GPS pozice v definovaném okruhu

Ahoj, hledám algoritmus (skutečně mi stačí i teoreticky) pro tohle: mám souřadnice např. 100 GPS pozic. Vyberu si jednu pozici a chci zjistit které jiné body jsou v okruhu např. 20 km a jak jsou tyto body vzdáleny od vybrané pozice. (Např. vyberu na firmách nějakou firmu a v jejím detailu mi to vypíše i firmy v okolí 20 km seřazeno od těch nejbližších k nejvzdálenějším.) Vzdálenost dvou bodů vypočítám snadno podle pěkné funkce od Jakuba Vrány. Jde mi ale o to, vůbec efektivně zjišťovat, pro které body v okruhu počítat. Jde vůbec počítat za běhu s přesným kruhem? Nebo musím počítat pro čtverec? Jako možnosti, které se mi moc nelíbí, zatím vidím počítat to za běhu pro všechny body (to ale může být výpočetně náročné pro velký počet bodů) nebo udělat kartézský součin všech bodů, vypočítat pro každou kombinaci vzdálenost, uložit do db a podle toho přesně vybírat (ale tam zase tahle tabulka může být velmi objemná). Případně počítat za běhu s čtvercovým okolím - tj. ne s kruhem. Poradíte, co je nejefektivnější, jak to dělat? Díky.

zkus udělat ůplně miniaturní čtverečky a bude to přesnější :-) ......... jinak někde sem takový FREE skript viděl až ho zase najdu postnu ti ho .

Napsal Dan;37332

Ahoj,

hledám algoritmus (skutečně mi stačí i teoreticky) pro tohle:

mám souřadnice např. 100 GPS pozic. Vyberu si jednu pozici a chci zjistit které jiné body jsou v okruhu např. 20 km a jak jsou tyto body vzdáleny od vybrané pozice. (Např. vyberu na firmách nějakou firmu a v jejím detailu mi to vypíše i firmy v okolí 20 km seřazeno od těch nejbližších k nejvzdálenějším.)

...

Jde vůbec počítat za běhu s přesným kruhem? Nebo musím počítat pro čtverec?

Poradíte, co je nejefektivnější, jak to dělat? Díky.

Ano, jde to i v run-time. Nejpohodlnější je použít slušnou databázi, co má podporu pro počítání s prostorovými daty - PostgreSQL má Postgis, a slyšel jsem, že Oracle má nějaké Spatial extension. Nějakou podporu má v sobě i MySQL, ale když jsem se na to naposledy díval, tak to bylo v žalostném stavu, tuším, že to ani neumělo počítat v kartografických souřadnicích. V obou případech (Oracle, Postgis) nevím v ČR o hostingu, který by to měl nainstalované a nabízel to. Kdybys to chtěl nasazovat nad Postgisem, tak se ozvi soukromě - na hostingu takové vylomeniny máme. Taktéž to mám rozchozené na živých velkých projektech, takže můžu pomoct s instalací. -- Pokud stačí použít nějaké řešení (TM), tak si můžeš ručně zrobit gridování - to je jednoduchá technika prostorového indexování. Nevím, jestli ta technika je někde popsaná - věřím tomu že je, ale z hlavy to nevím (já jsem se ji naučil na VŠ před pomocínášce). Vysvětlit se to dá za 10 minut, popsat to ale rychle nedokážu. Pokud těch dat nemáš moc, tak můžeš použít hrubou sílu - ukládat souřadnice jako dvě reálná čísla, předpočítávat si vzdálenosti dvojic bodů vlastními silami a potom vyhledávat v této matici. (Pokud omezíš předpočítávání jenom na maximální předpokládanou vzdálenost hledání, můžš použít nějaký bounding box). Snad to pomohlo, kdyžtak se ptej konkrétně --V PS: No jo no, tak jsem informatik křížený s kartografem...

Díky za info. Zapomněl jsem dodat, že k dispozici mám jen MySQL5 a PHP5. Na Oracle tuhle aplikaci skutečně dávat nebudu:) Zatím to tedy vypadá, že v podstatě budu jednou za čas vytvářet ten "kartézský součin", propočítám kombinace každý s každým a kdyby to bylo moc dat, tak všechny vzdálenosti nad můj výběr smáznu.

Když předpočítávání omezíš bounding boxem okolo zájmového pixelu, tak to máš skoro zadarmo. Pokud nemáš tisíce bodů, tak to s předpočítáváním budeš mít dokonce rychleji než nějakými vychytávkami. BTW: MySQL už spatial extension má (od verze 4.1), ale právě jsem to ověřoval a ještě furt neumí kartografické souřadné systémy a počítá na placce (já si stejně myslím, že Země je placka :-) ). --V

Díky, mrknu na to. Já měl kartografii (pokud to tak lze nazvat) v rámci zeměpisu naposled na základní škole, tak se v těch termínech moc nechytám :D

Pokud tech bodu neni extremne mnoho, ale zaroven jich neni malo a skutecne nemas sanci pouzit nejakou rozumnou podporu DB, tak bych mozna zkusil spise real-time hledani a to takovymto zpusobem:

Spoctu si ctverec, kteremu je kruznice vepsana

Spoctu si urcity pocet mensich ctvercu, ktere jsou ve ctverci z predchoziho bodu, ale zaroven nejsou v kruhu (cerne oznaceno na obrazku)

Najdu vsechny body, ktere odpovidaji temto podminkam (jsou ve ctverci z bodu 1 a nejsou v ani jednom ctverci z bodu 2)

Projdu vsechny vysledky a spoctu vzdalenosti, tim je vyfiltruju a nasledne podle teto vzdalenosti seradim

Mozne upravy:

• Pouzit vice "vylucujicich" ctvercu (napr. oranzova na obrazku)
• Pouzit opacne - ctverce jistoty (kruznice by pak byla opsana danemu ctverci)
• atd.

class Point { public $x = 0, $y = 0; }

function circle_sql(&$point, $distance) {

$point_a0 = point_dir($point, $distance, 0);

// spocita hlavni ctverec (v tomto kruhu je vepsana kruznice, ve ktere hledas)

// delka strany tohoto ctverce

$q_main_len = abs(2 * ($point -> x - $point_a0 -> x));

// horni levy roh ctverce

$q_top_left = new Point($point -> x - ($q_main_len / 2), $point -> y + ($q_main_len / 2));

// vytvoreni SQL dotazu pro hledani nad danym ctvercem

$q_main_sql = 'x BETWEEN '.($q_top_left -> x).' AND '.($q_top_left -> x + $q_main_len);

$q_main_sql .= ' AND y BETWEEN '.($q_top_left -> y).' AND '.($q_top_left -> y - $q_main_len);

$point_a45 = point_dir($point, $distance, 0);

// ted vedlejsi ctverce, jeden jejich roh je v bode 45deg vzdalenem

// od stredu kruhu, druhy roh je napr. v top left

// delka strany techto ctvercu

$q_small_len = abs($q_top_left -> x - $point_a45 -> x);

// prvni ctverec (nahore vlevo)

// ma stejny roh jako ten velky

$q_small_1_top_left = &$q_top_left;

$q_small_1_sql = 'x BETWEEN '.($q_small_1_top_left -> x).' AND '.($q_small_1_top_left -> x + $q_small_len);

$q_small_1_sql .= ' AND y BETWEEN '.($q_small_1_top_left -> y).' AND '.($q_small_1_top_left -> y - $q_small_len);

// druhy ctverec (nahore vpravo)

// jeho roh je vzdaleny o main_len - small_len vpravo, y ma stejne

$q_small_2_top_left = new Point($q_top_left -> x + $q_main_len - $q_small_len,$q_top_left -> y);

$q_small_2_sql = '...';

// treti ctverec (dole vlevo)

// jeho roh je vzdaleny o main_len - small_len dole, x ma stejne

$q_small_3_top_left = new Point($q_top_left -> x,$q_top_left -> y + $q_main_len + $q_small_len);

$q_small_3_sql = '...';

// ctvrty ctverec (dole vpravo)

// roh je o main_len - small_len u obou souradnic

$q_small_4_top_left = new Point($q_top_left -> x + $q_main_len - $q_small_len,$q_top_left -> y + $q_main_len + $q_small_len);

$q_small_4_sql = '...';

// finalni sql - je v hlavnim ctverci a zaroven neni ani v jednom z tech mensich

return "SELECT id, x, y FROM body WHERE $q_main_len AND NOT ($q_small_1_sql OR $q_small_2_sql ...)";

}

function point_distance(&$point1, &$point2) {

// vrati vzdalenost mezi temito 2 body

return $distance;

}

function point_dir(&$point, $distance, $angle) {

// tahle funkce musi vratit bod, ktery je ve vzdalenosti $distance

// pod uhlem $angle od bodu $point

return $new_point;

}

No neviem o tom moc... ale predpokladam ze suradnice z GPS su vo formate latlong (zemepisna sirka a dlzka). Treba ich previes na format UTM, zona 33U (http://www.fmnh.helsinki.fi/english/botany/afe/map/mgrszones_europe.jpg), ktory bude pre vypocet vhodnejsi. Da sa na to stiahnut open source kniznica Proj.4 (http://www.remotesensing.org/proj/). No a ked uz mame data prevedene, tak nie je nic jednoduchsie ako za pomoci Pythagorovej vety vyselectovat mesta v urcitej vzdialenosti. priklad pre bod x= 681546, y=5237595, vzdialenost 10 km SELECT x, y, mesto, ROUND(SQRT(POW(681546 - x, 2) + POW(5237595 - y, 2)) / 1000) as vzdialenost FROM mesta WHERE vzdialenost < 10 ORDER BY vzdialenost Doporucujem knizku "Mistrovství v MySQL (Michael Kofler)"

Pokud se Ti tyto body pokaždé mění, není vkládání do databáze nejlepší. Ale určitě rychlý základní filtr, který vyhodí beznadějné body a nechá jen nadějné kandidáty (a hlavně nepoužívá mocniny) by byl takový: - vezmeš x-souřadnici a pokud rozdíl těch dvou souřadnic je větší než těch Tvých 20km, tak to zrovna zahodíš - to samé pro y souřadnici - zbydou kandidáti, které stojí za to líp prověřit a zatím jsi použil jen odečítání a srovnávání, což jsou velmi rychlé operace Pak může pro body, které se dostaly do výběru, nastoupit Pytagorovka. Ale určitě neodmocňuj. Radši ten součet mocnin srovnávej s předem spočítanou druhou mocninou těch 20km. Tím se vyhneš náročnému odmocňování.