Volba vhodného algoritmu

[h7]

Poradí si to s tímto http://pbrd.co/1eGnogE?

[Reklama]

[anonym]

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

Kód: [Vybrat]

.             | . .
              |
              |
              |
              |
            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)

[andy]

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.

[JS]

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.

[JS]

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.

[Reklama]

[Jirka]

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

[Pedro]

@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.

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

[9875]

ja ten Váš princíp neak nechápem. Možte ho prosím znázorniť na nasledovnom príklade?

[.]

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.

[anonym]

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)