Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: LadislavBöhm 13. 04. 2014, 14:54:58
-
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). Poloha každého bodu je tedy určena hodnotou X a Y. Potřebuji najít dva nejbližší body těch množin.
Jednoduchý náčrt vypadá takto:
(http://i59.tinypic.com/2jbp5sl.png)
Zatím to dělám metodou brute-force, protože bodů je málo, ale chtěl bych zvolit něco, s menší složitostí. Jaký algoritmus mám použít? Pokud je to relevantní, píšu to v C#.
Díky
-
http://stackoverflow.com/questions/3700983/what-is-the-fastest-algorithm-to-calculate-the-minimum-distance-between-two-sets
-
mne tak z hlavy napada vyuziti R-stromu na indexovani oblasti abych porovnaval pokud mozno pouze blizke body
-
Tak jsem studoval a zapomněl jsem přidat důležitou informaci, že ty dvě množiny tvoří konvexní polygon.
Původní obrázek je tedy nepřesný, správně ten problém vypadá takto:
(http://i57.tinypic.com/35inol3.png)
-
Ano, konkávnos/konvexnost mi vrtala hlavou. Chápu-li to dobře, tak jsou to dva "obláčky" co nejdou přes sebe (cloudy :-)) Takže: Těžiště jednoho a druhého mráčku; rovnice přímky procházející těžišti mráčků, (natočení, rotace) vztyčení kolmic z těžišť - ty body co jdou od těchto kolmic ze středů (těžišť) do +/- nekonečen odebrat (jsou pasé,neboď od jednoho těžiště po druhé by měli být vhonější) a znovu cyklus rekurze: těžiště... Maybe to bude fungovat, možná to bude optimílní na množství výpočetních operací (složitost...) a možná nikoliv. Už se těším na jiné návrhy.
-
- No ono bude hodně záviset složitost, správnost a rychlost výpočtu na předpokladech, kde ty body jsou :-)) - jaká je jich "souvztažnost", pravděpodobost výskytu ap. kriteria, abychom si usnadnili práci. No to těžiště byl jenom jeden z nástřelů a vidím, že jsou i takové situace, kdy mě to odvede od správného řešení... No možná díky konvexnosti, skrytým hranám co nepůjdou vidět z těžišť na protilehlé množině (promítnutí 'světla'); bodů co mají blíže k těžišti druhé množiny než ke své množině <--> především tudy bych se asi ubíral (ale už znovu tuším, že najdu vyjímky ve své úvaze) Ale ta konvexnost je krásná... Kruci, analogový počítač, průtok kapalinou, největší tlak, rychlost,..., anebo kde nám prskne výboj...
-
Vhodneho algoritmu znamena presne co? Z hladiska vypoctoveho, pamatovej narocnosti... ?
-
Jde mi spíše o výpočtovou náročnost, jak jsem psal, zatím mi to funguje na brute-force přístupu, který je v tomhle ohledu to nejhorší. Proto hledám lepší variantu.
-
Ano, konkávnos/konvexnost mi vrtala hlavou. Chápu-li to dobře, tak jsou to dva "obláčky" co nejdou přes sebe (cloudy :-)) Takže: Těžiště jednoho a druhého mráčku; rovnice přímky procházející těžišti mráčků, (natočení, rotace) vztyčení kolmic z těžišť - ty body co jdou od těchto kolmic ze středů (těžišť) do +/- nekonečen odebrat (jsou pasé,neboď od jednoho těžiště po druhé by měli být vhonější) a znovu cyklus rekurze: těžiště... Maybe to bude fungovat, možná to bude optimílní na množství výpočetních operací (složitost...) a možná nikoliv. Už se těším na jiné návrhy.
precet sem si problem a napadnul me +- stejny algoritmus, tehle prizpevek sem cetl az kdyz sem to mel sepsane ;)
slozitost mi vysla NlogN pro prumerny/idealni pripad, N^2 pro nejhorsi (tedy ze pri kazdem odriznuti zabiju jen 1 vrchol)
je tu ale otazka - hledame nejblizsi body polygonu, nebo nejblizsi vrcholy? je mozne ze nejblizsi body budou tak ze to je vrchol-bod na hrane.
situace bod na hrane - bod na hrane by nemela nikdy nastat (krom specialniho pripadu kdy nejblizsi hrany jsou rovnobezne, ale pak existuji 2 pary vrchol-vrchol se stejnou vzdalenosti)
najit pripady vrchol-hrana by melo u konvexniho byt jednoduche, myslim ze bude stacit najit nejblizsi vrcholy, a pak zkontrolovat k nim sousedici hrany (zadna jina by nemela byt kandidat), to tak ze kolmice na hranu skrz vrchol z druhe mnoziny, prusecik je kandidat na nejblizsi bod
-
Ano, konkávnos/konvexnost mi vrtala hlavou. Chápu-li to dobře, tak jsou to dva "obláčky" co nejdou přes sebe (cloudy :-)) Takže: Těžiště jednoho a druhého mráčku; rovnice přímky procházející těžišti mráčků, (natočení, rotace) vztyčení kolmic z těžišť - ty body co jdou od těchto kolmic ze středů (těžišť) do +/- nekonečen odebrat (jsou pasé,neboď od jednoho těžiště po druhé by měli být vhonější) a znovu cyklus rekurze: těžiště... Maybe to bude fungovat, možná to bude optimílní na množství výpočetních operací (složitost...) a možná nikoliv. Už se těším na jiné návrhy.
To podle mne nebude fungovat, pokud budou nějaké body daleko od těžiště.
..... | .....
|
|
|
.|.
Tady jsou si nejbližší evidentně ty dva body dole, ale jakmile budete počítat s těžištěm, vyloučíte je.
-
http://cgm.cs.mcgill.ca/~orm/mind2p.html
-
To podle mne nebude fungovat, pokud budou nějaké body daleko od těžiště.
..... | .....
|
|
|
.|.
Tady jsou si nejbližší evidentně ty dva body dole, ale jakmile budete počítat s těžištěm, vyloučíte je.
neni pravda, alespon v tomhle pripade (a variacich)
ty rezny roviny budou rovnobezny s tou delici primkou, tedy asi takhle
...|.. | ..|...
| | |
| | |
| | |
| .|. |
zajimavejsi pripad je kdyz jeden polygon otocis vzhuru nohama:
..... | .
|
|
|
. | .....
pak ti vznikne neco takovehohle, coz porad funguje:
.../. | .
/ | /
/ | /
/ | /
. | ./....
teziste tady dava dve vlastnosti - je uvnitr polygonu (a snadno vypocitatelne), a pri rezu odebere cca polovinu vrcholu. pro korektnost je AFAIK potreba jen prvni vlastnost, pro slozitost NlogN druha
-
neni pravda, alespon v tomhle pripade (a variacich)
ty rezny roviny budou rovnobezny s tou delici primkou, tedy asi takhle
Aha, omlouvám se, špatně jsem pochopil, kde budou ty kolmice na spojnici těžišť.
-
neni pravda, alespon v tomhle pripade (a variacich)
tak sem si nakonec nalezl protipriklad, teda pokud tazatel chce nejblizsi vrcholy (tedy ne body na hranach)
. |.
|
|
|
.| .
|
|
|
. |.
nejblizsi vrcholy v tomhle pripade jsou ty nejvic vpravo u obou polygonu, ale metoda rezani pres stred by je nenasla (co by nasla je nejblizsi par vrchol-bod na hrane, ale k tomu taky muze byt protipriklad)
-
Nevím, jestli už je dobojováno a hledači našli co hledali... a úkol je splněn, nebo nikoliv. Proto se vrátím k mojí myšlence a zkusím ji rozvést (jenom ji jsem "schopen" sledovat :-)) a poprosil bych vás o posouzení. Co a jak vidím já: 1) Konvexnost - stěžejní, ulehčující a umožňující práci s pomocnými konstrukcemi jako --> 2) Těžiště 3) Body tvoří obvod 'bubliny' (bubliny jsou konvexní...) 4) Každý Bod má svého nejbližšího partnera nalevo L a napravo R. Teď s těmi myšlenkami zatřeseme... a zkusíme algoritmizovat: 5) Vybereme náhodně dva body = jeden na jedné bublině a druhý na druhé. Označme je B1 a C1 6) Spočteme těžiště bublin - ozn. BT, CT. 7) Vypočtu vzdálenosti mezi B1 a C1 , mezi těžišti BT a CT. 8.)...(a teď třeba takto) vypočtu vzdálenosti mezi body po levici a pravici bodu B1a samotného bodu B1 <-vůči-> bodům levice a pravice C1a samotného C1. Získám takto 9 vzdáleností a vyberu z nich dvojici jež splňuje minimální vzdálenost do dalšího 'kola'. Pokud taková nová dvojice neexistuje, neboť původní (B1-C1) byla 'už' minimem, pak ... /zde mám možnost/nutnost! zapracovat ještě kritérium s těžištěm/ + /zde mám možnost/nutnost! zapracovat ještě kritérium, zda mezi body není stěna bubliny - s potenciálně bližšími body.../ <-- detekci nechám pro někoho jiného, anebo až se vyspím. Snad je alespoň 'lezení' po bublině, tj. práce se sousedy inovativní (neperspektivní body, řešení - zabít).
-
Poradí si to s tímto http://pbrd.co/1eGnogE?
-
Poradí si to s tímto http://pbrd.co/1eGnogE?
vsechny dosavadni algoritmy pracuji s disjunktnimi konvexnimi polygony v rovine (tedy jak to tazatel nakreslil)
takze ne, tohle je tak hnusnej pripad ze zadnej z zatim uvedenych algoritmu nepujde (myslim si ze tohle lepe nez kazdy s kazdym ani nepujde)
Snad je alespoň 'lezení' po bublině, tj. práce se sousedy inovativní (neperspektivní body, řešení - zabít).
musim rict ze me se tenhle pristup celkem libi, ale myslim ze to ma stejny problem jako to rezani (tedy pokud opravdu chceme jen nejblizsi vrcholy, a nikoliv body na hranach) - C a B jsou vrcholy co vyberes v prnim kroku, po testu sousedu zjistis ze zadny soused ti nepomuze, takze mas vyhrano. od pohledu jsou ale neblizsi vrcholy A a B
. | . .
|
|
|
|
B | A
|
|
|
. | C .
apropo, reseni s rezanim ma slozitost O(N), ne O(NlogN) jak sem prvne psal, protoze v postupnych iteracich kontrolujeme mene vrcholu, takze se to nascita na 2N testu (za predpokladu ze pri kazdem rezu zahodime polovinu vrcholu). reseni s lezenim po hranach by take vyslo O(N)
-
Ziadna bublina, toto sa vola konvexny obal a na jeho hladanie je znamych viacero algoritmov. Cize tu ide o hladanie dvoch najblizsich bodov konvexnych obalov, ale skor sa da googlit pod najblizsimi bodmi polygonov, pretoze ide skor o graficky problem.
Ja by som asi postupoval tak, ze si usporiadam body podla poradia na obvode. Vyberem lubovolny bod a hladam bod blizsi na druhom polygone, pricom idem smerom ktorym sa znizuje vzdialenost. Vdaka konvexnosti bude iba 1 min vzdialenost pre dany bod. Cize vyberem bod na jednom, na druhom idem smerom ktorym sa vzdialenost znizuje. Vyberem bod na druhom bod v ktorom som skoncil, na prvom zase znizujem..tak by to malo skonvergovat a urcite to nebude n^2 ale pocitat sa mi to nechce.
-
takze ne, tohle je tak hnusnej pripad ze zadnej z zatim uvedenych algoritmu nepujde (myslim si ze tohle lepe nez kazdy s kazdym ani nepujde)
Taky si myslim, pokud ma jit o to najit nejblizsi body a ne vzdalenost dvou konvexnich polygonu.
Ale prece jen by se to mozna trochu zlepsit dalo pomoci trojuhelnikove nerovnosti. Kdybychom vzali teziste tech mnozin, a predpocitali vzdalenost kazdeho bodu od teziste sve mnoziny, pak muzeme nektere dvojice bodu (pri zkouseni kazdy s kazdym) vyloucit pokud je vzdalenost tezist snizena o vzdalenosti kazdeho z tech bodu od sveho teziste vetsi, nez dosavadni nejlepsi kandidat.
-
Doplneni k predchozimu - misto teziste by se dal pouzit algoritmus k-means na kazdou mnozinu zvlast. Tim by se daly naraz vyloucit cele clustery bodu, pokud popsanym zpusobem nesplnuji trojuhelnikovou nerovnost.
-
Co takhle sestavit z jedné množiny bodů kd-strom. A pak postupně ke každému bodu z druhé množiny hledat jemu nejbližší bod z té první, za použití toho kd-stromu. Rychlostně by to mohlo vyjít lépe.
-
http://aia-i.com/ijai/sample/vol1/no1/89-107.pdf
-
@Jirka: jj, a mozna bych to neimplementoval sam, ale pouzil na to nejakou jiz existujici implementaci, treba tohle: http://pointclouds.org/documentation/tutorials/kdtree_search.php
Nac znovu vynalezat kolo.
-
to je zbytecne moc bodu. navic zadani je neuplne. neni jasne jak casto bude prohledavat a kolik polygonu ma a co je ta drazsi operace. jestli helda jednou nebo mnohokrat atd atd.
polygony nechat v seznamu jak se body retezi za sebou. ty predfiltrovat viz. (http://i57.tinypic.com/2m4zp5t.png)
ve vicerozmernem prostoru to bude ale trosku vetsi opruz. jinak hledas v kazdym rozmeru pas mezi co muzes vypustit. pak dostanes bud bod (prusecik zelenych) nebo hranu nebo plochu atd. ktere budou nejbliz body polygonu co ma smysl srovnavat. to jsou ty body co tvori oranzove obdelniky na kazde strane retezu ukoncene fialovymi ovaly. ty ovaly pak znaci zmenu smeru delty v dane dimenzi.
-
a ocividne ma zmatek i v tom co chce, protoze jestli hleda ze dvou mnozin nejblizsi, tak nemuze brat jen obal, ale musi vzit i nektery body uvnitr obalu.
-
pro prekryv v jednom z rozmeru to vypada nasledovne
(http://i60.tinypic.com/2vnm8gm.png)
-
ja ten Váš princíp neak nechápem. Možte ho prosím znázorniť na nasledovnom príklade?
(http://i59.tinypic.com/11qprvk.png)
-
jo no. vraci priblizne nikoliv presne vysledky :)
-
ty appoloniovy "prostory" by asi slo jeste osetrit dalsim vyberem i v pripade ze neni prunik v tech zelenych, ale uz se mi nechce trapit halva.
-
Co takhle sestavit z jedné množiny bodů kd-strom. A pak postupně ke každému bodu z druhé množiny hledat jemu nejbližší bod z té první, za použití toho kd-stromu. Rychlostně by to mohlo vyjít lépe.
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)
co by asi fungovalo je rozdelit prostor na rovnomernou mrizku, a pak vrcholy kontrolovat jen proti mnozine bunek ktera ma moznost byt bliz nez aktualne nejmensi vzdalenost (coz se diky rovnomernosti ty mrizky udela velice snadno)
sidenote: tohle sice muze v praxi byt rychlejsi nez brute force, ale v nejhorsim pripade to je porad O(N^2)
-
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)
-
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
-
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á".
-
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.
-
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 (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)
-
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 (http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree)