| Autor | Zpráva | ||
|---|---|---|---|
| nethor Profil |
#1 · Zasláno: 9. 4. 2016, 18:30:02
Zdravím ,
potřebuji spočítat nejkratší možnou vzdálenost mezi dvěma polygony. Programem a přijatelně rychle. Vrcholové body polygonu (dále jen body polygonu) jsou dány souřednicemi X a Y. Dělám to tím způsobem, že spočítám vzdálenost všech bodů polygonu A od všech bodů polygonu B a vyberu nejkratší. Polygony mají kolem 60 bodů, je to tedy 60*60 =3600 výpočtů. Správně bych měl ještě spočítat vzdálenost bodů pol.A od úsešek pol.B a naopak. z důvodu rychlosti jsem tyto kroky vynechal (chyba je v tomto konkrétním případě zanedbatelná). I tak ale 1 výpočet vzdálenosti polygonů v PHP trvá 2 - 6 s. a vzáleností polygonů potřebuji porovnat kolem 100 000, což vychází řádově na několik dní strojočasu. Nabízí se otázka, jak spočítat vzdálenost pol. nějek sofistikovaněji, ne tak otrocky a tím výpočet urychlit. - Když se na polygony na výkresu koukne člověk, měly by stačit 2-3 výpočty a jsme doma. Nenapdá mě ale způsob jak vytvořit algoritmus, který by selekci relevantních bodů provedl. Šlo by asi pracovat s těžištěm polygonu, vždy se ale vyskytne nějaká vyjímka, která mi postup zhatí. Nějaký nápad, jak na to? |
||
| Alphard Profil |
#2 · Zasláno: 9. 4. 2016, 19:51:12
Jsou ty polygony obecné, nebo třeba konvexní?
„Dělám to tím způsobem, že spočítám vzdálenost všech bodů polygonu A od všech bodů polygonu B a vyberu nejkratší.“ Pro porovnání stačí vypočítat součty mocnin, odmocnina je drahá operace, takže odmocnit až finální nejkratší úsek. |
||
| nethor Profil |
Alphard:
Polygony jsou zcela obecné, často nekonvexní a velmi různorodé. „odmocnina je drahá operace, takže odmocnit až finální nejkratší úsek.“ To mě nenapadlo, díky za tip, zkusím. Počet vrcholů polygonu jsem špatně odhadnul, je jich cca 500 - 2000. Tou úpravou s odmocninou se asi něco ušetřilo, ale nic závratného, Testnul jsem při té příležitosti rychlost fcí sqrt() a pow() , kupodivu pow je o něco málo pomalejší. $Val = ($X = $A - $B) * $X ; vychází o něco rychleji, než $Val = pow($A - $B , 2) ; ... Asi trochu brzdí volání fce (?)
Řešením by bylo snížit počet operací, což mě vrací k původní myšlence. |
||
| Alphard Profil |
#4 · Zasláno: 10. 4. 2016, 01:45:06
nethor:
„Počet vrcholů polygonu jsem špatně odhadnul, je jich cca 500 - 2000.“ To spíš, zdálo se mi, že to trvá strašně dlouho, 1000^2 = 1M, což by těm 3 s zhruba odpovídalo. Snížit složitost je samozřejmě nejlepší, ale není špatné udělat i jiné úpravy... Pokud vím, žádné kouzelné matematické řešení neexistuje, při modelování ve 3D je to ještě větší boj. Ale tam jsem ještě neviděl řešení v PHP :-) Vzhledem k novým informacím o počtu bodů bude mít smysl použít nějakou heuristiku pro odhad perspektivních bodů. Teď je tam složitost n^2, což je 1M operací, kdyby se např. vypočítaly úhly jednotlivých bodů vzhledem k těžišti obou mnohoúhelníků a dál se testoval jen perspektivní kvadrant, stalo by se z toho zhruba (n/4)^2, což bude 16x rychlejší. Další možností redukce vstupních bodů je výpočet vzdálenosti vzhledem k těžišti druhého mnohoúhelníku a pak detailní testování např. zase jen čtvrtiny bodů. Všechno to jsou heuristiky a umím si představit situaci, kdy to selže, ale určitá chyba je zanesená už v samotném přístupu, kdy se uvažují jen vrcholy. Bylo by dobré vědět, jaké odchylky jsou přípustné. Mimochodem, ty jednotlivé body se tahají z databáze (hádám vzhledem k předešlým tématům)? Docela by mě zajímala optimalizace databáze pro tyto výpočty, můžete zkusit udělat join (bez omezující podmínky, vytvořit úplný kartézský součet) bodů dvou mnohoúhelníků a vypočítat ty vzdálenosti na úrovni databáze. „Tou úpravou s odmocninou se asi něco ušetřilo, ale nic závratného“ Tak nic závratného jsem ani nečekal, PHP je interpretovaný jazyk, v každé iteraci bude hromada dereferencí v přístupu k paměti, nečekám zázraky ani při cachování, takže ten výpočet odmocniny se v tom dost ztratí. Ale každá operace, která se může vynechat, pomůže. |
||
| _es Profil |
#5 · Zasláno: 10. 4. 2016, 07:01:56
nethor:
„Když se na polygony na výkresu koukne člověk“ Keď píšeš o výkrese, tak to je len 2D? Alebo 3D? „Polyhony jsou zcela obecné, často nekonvexní a velmi různorodé.“ Môžu byť aj s „dutinami“ a potom jeden polygón v druhom, alebo môžu mať aj spoločný prienik? |
||
| nethor Profil |
Alphard:
Právě o tu heuristiku mi šlo, nic se ni nepodařilo vygooglit. (i ten algoritmus pro délku jsem si odvodil..) Můžu si dovolit chybu až cca 5% z délky, ale nechci tam zanést logickou chybu, která by vedla k úplnému selhání v nějakém speciálním případě. Od úložiště v db jsem pro tohle použití upustil, MySQL byla pomalá a občas i padala, tabulka začala být hrozně velká. Napsal jsem vlastní - SerialStore() zjednodušeně: serializovaná data v texťáku (+ ošetřené zamykání, doplňování) a v databázi mám jen odkaz. To běhá dobře. _es: Pouze 2D , bez děr(dutin). Průnik a dotyk jsem již vyloučil jiným algoritmem. Počítám pouze nejmenší vzdálenost. |
||
| Kajman Profil |
#7 · Zasláno: 10. 4. 2016, 13:24:54
nethor:
„Od úložiště v db jsem pro tohle použití upustil“ Mysql od verze 5.7.5 by snad měla umět dev.mysql.com/doc/refman/5.7/en/spatial-relation-functions-object-shapes.html#function_st-distance A postresql by měla mít rozšítení PostGis, kterým to asi také půjde. |
||
| nethor Profil |
#8 · Zasláno: 10. 4. 2016, 14:23:02
Kajman:
st-distance() funguje - pro vzdálenost bodů, ale výpočet je o hodně pomalejší, než v PHP: Počet cyklů:10000 Time:2.97s Koukal jem teď, že MySQL umí pracovat i s polygony: dev.mysql.com/doc/refman/5.7/en/gis-polygon-property-functions.html, ale fci pro vzdálenost jsem tam nenašel. |
||
| TomášK Profil |
Problém nejmenší vzdálenosti vrcholů dvou polygonů jde vyřešit v O(n*log(n)), ale bude to vyžadovat pár grafových algoritmů. Jestli jsou na to v php knihovny nevím, ono moc nedává smysl psát to v php. Hádám, že bruteforce algorithm v C (Rust, C++, Java, ..., možná i Javascript) bude na tomhle počtu rychlejší než sofistikovaný postup v php (křišťálová koule říká, že 2-10krát).
Uvažujme graf, jehož vrcholy jsou vrcholy obou polygonů a hrany jsou hrany mezi polygony (n^2 hran). Není složité nahlédnout (:-)), že nejkratší spojnice bude ležet i v minimální kostře tohoto grafu [jinak bych mohl nahradit hranu v kostře spojující polygony tou nejkratší]. V O(n*log(n)) se dají se najít grafy, které mají O(n) hran a jejichž podgrafem je minimální kostra, třeba Delaunay triangulation (duální graf k Voroného diagramu). Nejde o příliš pokročilou teorii grafů, všechny uvedené algoritmy budou v úvodním kurzu, ale na pár řádků to taky není. |
||
| _es Profil |
#10 · Zasláno: 10. 4. 2016, 21:34:23
nethor:
„Můžu si dovolit chybu až cca 5% z délky, ale nechci tam zanést logickou chybu, která by vedla k úplnému selhání v nějakém speciálním případě.“ Žiadny taký nepresný algoritmus so zaručenou maximálnou chybou v percentách na „zcela obecné“ polygóny neexistuje. Ani tvoje zjednodušenie „spočítám vzdálenost všech bodů polygonu A od všech bodů polygonu B a vyberu nejkratší“ to nezaručuje - dajú sa vymyslieť prípady, kedy bude chyba viac ako 5 %. |
||
| nethor Profil |
#11 · Zasláno: 12. 4. 2016, 10:44:07
TomášK:
Díky za nasměrování, zjevně to řešit lze, bohužel je i v nástinu několik pojmů z matamatiky, se kterými jsem se dříve nesetkal a studium problematiky by mi asi trvalo déle, než výpočet 'brutal force' v PHP. Holt nechám o pár dní déle mašinu proběhnout. Díky všem. |
||
| Kajman Profil |
#12 · Zasláno: 12. 4. 2016, 12:22:28
nethor:
„ale fci pro vzdálenost jsem tam nenašel.“ To je právě ta st_distance mysql> SELECT ST_distance(ST_GeomFromText('POLYGON((0 2,1 4,1 0,0 2))'), ST_GeomFromText('POLYGON((2 1,2 3,3 2,2 1))')) vzdalenost;
+------------+
| vzdalenost |
+------------+
| 1 |
+------------+
1 row in set (0.01 sec) |
||
| nethor Profil |
#13 · Zasláno: 12. 4. 2016, 17:17:59
Kajman:
To vypadá dobře! Děkuju. (Když jem to původně zkoušel, nešlo mi do ST_distance zadat polygony -> chybná syntax) |
||
| nethor Profil |
#14 · Zasláno: 13. 4. 2016, 10:41:34
Kajman:
Výpočet přes MySQL šlape bezvadně, cca 20x rychleji, problém je tedy vyřešen. Ještě jednou díky. |
||
|
Časová prodleva: 8 let
|
|||
0