Volba vhodného algoritmu

.

Re:Volba vhodného algoritmu
« Odpověď #30 kdy: 17. 04. 2014, 07:45:12 »
k tomu predfiltrovani.
prvni najdes zeleny cary minima/maxima ve vsech rozmerech
kdyz se v zadnem rozmeru interval neprekryva s intervalem druheho porovnavaneho konvexniho obalu
....tak se divas zda mas bod primo v pruniku
....jinak rozdelujes obal na intervaly koncici prekryvem hran obepsaneho rovnobezniku (rovnobezny s osou prostoru pokud ovsem neresis neuklidovsky prostor)
........prochazis body obalu od kraje intervalu vcetne tech kraju co se dotykaji zelenych minim/maxim
........koncis a zacinas specialnim pripadem bodoveho prekryvu rovnobezniku co vypada jak hrana
jinak konstruujes appoloniovy kruznici a hledas jestli maji prunik
....kdyz nemaji pouzijes to v hornim ifu
....pokud maji, prohledavas cely obal (asi by to slo jeste zoptimalizovat, ale otazka je jestli to ma smysl a komu se to chce)


.

Re:Volba vhodného algoritmu
« Odpověď #31 kdy: 17. 04. 2014, 07:50:47 »
err skrtni tu cast s tim bodem v pruniku. jdes ty intervaly od / do vcetne tech extra pripadu, kdy je obepsany rovnobeznik menerozmerny / hrana obalu rovnobezna s osou prostoru

Jirka

Re:Volba vhodného algoritmu
« Odpověď #32 kdy: 17. 04. 2014, 08:56:47 »
Citace
uplne nevidim jak bych tam pouzil kD strom (protoze ten mi klidne muze ty dva nejblizsi vrcholy dat do ruznych bunek, ve chvili kdy sahas na nekolik bunek tak uz je v tom trochu bordel)

V kd-stromu by byly "zaindexované" body pouze z jedné množiny. Pak by se pro každý bod z druhé množiny provedl dotaz na kd-strom, který by vrátil k němu nejbližší bod. V podstatě to funguje jako binární vyhledání akorát s tím rozdílem, že na každé vrstvě kd-stromu se to dělí podle jiné souřadnice (např. na sudých podle X, na lichých podle Y, ve 2d jsou tyto dělicí roviny v podstatě přímky rovnoběžné s osami). Druhý rozdíl je, že při vyhledávání je nutno kontrolovat zda-li bod nalezený v "bližším" podstromu, je blíže než dělící přímka. V případě, že je blíže je to bez problému a máme co jsme hledali. V případě že ne, je nutné zkontrolovat i body ve "vzdálenějšího" podstromu. Nicméně, i když těch "pohledů" do "vzdálenějšího" podstromu může být relativně dost, pořád to bude rychlejší než "hrubá sílá".


Juro

Re:Volba vhodného algoritmu
« Odpověď #33 kdy: 17. 04. 2014, 21:13:06 »
Ahoj,

nejsem profesí programátor, ale v jednom hobby projektu řeším volbu vhodného algoritmu. Mám dvě množiny bodů v kartézské soustavě souřadnic o dvou osách (X a Y)...
Ahoj,

tiez nie som zrovna programator, ale riesil by som to tak, ze by som vybral nahodne 3 dvojce a dal technikom preratat vzdialenosti. Potom by som ich zoradil a nazval Standard, Professional a Enterprise. Toto by malo pokryt vacsinu poziadaviek na blizke body. Ak by niekto potreboval este blizsie body, riesil by som to ako projekt a customizaciu za cca 140 EUR/h analyza a 110 EUR/h vyvoj.

Tomáš

Re:Volba vhodného algoritmu
« Odpověď #34 kdy: 17. 04. 2014, 23:58:35 »
Zdá se mi, že problém je vyřešen už v odpovědi #1 od g5869: když se do ní začteš, najdeš např. článek http://www-cgrl.cs.mcgill.ca/~godfried/publications/mindist.pdf, kde autoři umí problém vyřešit takto:
  • pro ošklivé případy (jako je např. v odpovědi #15) ve složitosti nejvýše O(n log n) tím, že: najdou minimální kostru grafu obsahujícího všechny vrcholy na obrázku, tzn. grafu z obou množin dohromady (najít kostru celkem pěkně uměl už matematik Borůvka, když za první republiky hledal, jak co nejkratším elektrickým vedením pospojovat Moravské vesničky; ale dnes je i řada jiných algoritmů) a pak už na té kostře jen vyberou hranu, která vede z jedné množiny do druhé a přitom je nejkratší taková - to už zabere jen O(n)
  • pro hezké případy (jako např. ty dva konvexní polygony) to autoři obdobným postupem umí dokonce ve složitosti nejvýše O(n)



Tomáš

Re:Volba vhodného algoritmu
« Odpověď #35 kdy: 18. 04. 2014, 01:40:47 »
Ještě oprava odpovědi #34: s tím Borůvkou jsem se nechal trochu unést: jeho algoritmus je určen pro malinko jiný účel a v tomto případě by našel řešení v O(E log n), kde E je počet všech možných hran a tedy E = O(n^2).
Ale jde to opravdu v O(n log n) - viz např. zde: http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree