Autor Zpráva
nethor
Profil
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
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
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
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
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
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
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
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
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
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
Kajman:
Výpočet přes MySQL šlape bezvadně, cca 20x rychleji, problém je tedy vyřešen.
Ještě jednou díky.

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: