Průnik 4-úhelníků mezi sebou – Matematika – Fórum – Programujte.com

Jak zjistit průnik 2 4-úhleníků?
Pravděpodobně na to musím jít přes trojúhelníky. Bohužel všude, kde jsem hledal, byl uvedený postup, kdy musí alespoň jeden z vrcholů trojúhelníku ležet uvnitř toho druhého, a to je pro mě nepoužitelné.

Jinak jakou literaturu by jste doporučuli o analytické geometrii? Vše co jsem měl v ruce se nedostalo dál než k přímkám a rovině...

ja bych to asi resil ze ty dva 4uhelniky vemu jako roviny
pak otestovat ktere strany prochazeni tou rovinou druheho 4uhelniku, pak jestli je v nem nebo mimo a nakonec jeste mezi tema prunikama usecku..
takhle mi to zni snadno ale kdo vi jaky to bude pak :D

co presne chces zjistit? obsah pruniku, ci pouze to zdali se protinaji? take je docela dulezite zdali budou konvexni ci ne. kazdopadne bych postupoval nasledovne: mejme utvary m-uhelnik a n-uhelnik. nejprve pro vsechny dvojice usecek z m a n uhelniku spocitas jejich pruseciky (pokud existuji) a vytvoris pro ne prislusne vrcholy. Nyni zvolis libovolny z techto nove vzniklych bodu (pokud zadny takovy neexistuje, pak bud je jeden z utvary cely v druhem nebo prunik nemaji), a budes zkoumat jeho sousedy (tedy vrcholy se kterymi je spojen useckou, existuji maximalne 4, pokud nejaky z tech utvaru neprotinal sam sebe). zvolis z nich takovy, ktery je bud take nove vytvoreny (tedy nepatril do zadneho z puvodnich utvaru), nebo takovy, ktery patri do jednoho z utvaru, ale lezi uvnitr utvaru druheho (coz neni tezke poznat). pokud zadny takovy neexistuje, pak maji oba utvary prunik jeden bod, ktery jsi prave nasel. pokud nejaky takovy existuje, pak existuji prave dva (v konvexnich, u nekonvexnich jich muze byt vice, ale zvolit spravny neni tezke), a oba jsou vrcholy mnohouhelniku ktery tvori prunik, takze postoupis do jednoho z nich a opet obdobne prozkoumas jeho sousedy. takto rekonstruujes cely mnohouhelnik ktery tvori prunik, a jeho obsah uz se spocita snadno (pokud jsou utvary nekonvexni, muze takovychto mnohouhelniku vzniknout vic.
tohle reseni ony mnohouhelniky nalezne O(m*n*(logn + logm), coz je docela dobre, jestli by to mohlo jit lepe netusim...
poznamka: ty logaritmy ve slozitosti jsou pro to, ze me nenapadl lepsi zpusob jak hledat sousedy pro ony nove vznikle vrcholy - tedy
pro kazdou hranu z puvodnich utvaru si setridim vsechny nove vznikle ktere na ni lezi, a podle toho jim priradim sousedy.

aha jestli je to ve 2D tak proste zjistit kde se protinaj navzajem strany.. horsi je pokud by byl jeden podmnozinou druheho :D

To tmi : To KIIV : Díky za rady. Nějak jsme zapomněl dodat, že to uvažuji pouze v rovině. Řešení přes průniky hran jsem už zkoušel, ale nefungovalo to, protože mám velký rozsah velikostí těch troúhelníků a často se stávalo, že se jeden malý octl uprostřed velkého.
Jde mi o to zjistit hlavně zda-li nastal průnik. A pokud by se i v nějakém rozumném čase dala zjisit i hloubka průniku, tak by mi to ulehčilo spoustu věcí (respektive vzdálenost nejvzdálenějšího bodu od jedné z hran).
Trochu jsem ješte pogooglil, našel jsme pár fór kde se to řešilo, ale stále se nemůžu dopátrat nějakého "plnohodnotného" řešení...

no detekce nastani pruniku je skutecne jednoducha, jak pro konvexni, tak pro nekonvexni mnohouhelniky. podobne jako v algoritmu, nejprve vyzkousis zdali nejake hrany maji prusecik, pokud ano, jiste nastal prunik. pokud ne, pak by musel jeden mnohouhelnik cely lezet v druhem. tedy libovolne zvolis jeden bod, ktery se nachazi mimo oba mnohouhelniky, a pro oba udelas nasledujici:
vezmi libovolny vrchol mnohouhelniku, spoj ho s onim bodem mimo useckou X, a spocitej kolikrat X protne nejakou usecku prislusici druhemu mnohouhelniku. pokud to nastane lise-krat, pak tento mnohouhelnik lezi uvnitr toho druheho. dukaz vychazi z Jordanovy vety o kruznici, ale myslim ze mi to muzes verit :)

a pokud pro oba nastane sudy pocet pruniku, pak museji mit nulovy prunik. celkove tedy zjisteni trva O(mn), kde m a n jsou pocty hran uhelniku

To tmi : To tmi : Ahá, díky, ten první text jsme trochu nepochopil, ale teď už tomu rozumím. Vždyť je to tak jednoduché!

Bohužel, nový poznatek, k průniku 2 čtyřúhelníků potřebuji 24 zjistit průnik úsečky. Na jednu iteraci potřebuji zhruba 10*10 testů na průnik. To mi dává 2400 testů na jednu iteraci. Bohužel, moje PC dá maximálně 800 testů při 25 fps... Funkci na průnik úseček už optimalizovat asi nejde... Prosím, opravte mě, a řekněte mi, že mám něco špatně :smile10:
Asi budu muset najít jinej algoritmus...

To yaqwsx : pokud pamatuju z grafiky tak byl i algorytmus kterej prochazel radky obrazovky a kdyz narazil na okraj nejakeho objektu zacal vyplnovat dokud nenarazil na nejakej dalsi okraj... hadam ze tobe by stacila verze kde bys kontroloval jen radky kde sou nejaky hrany
ale kdo vi k cemu to vlastne potrebujes

To KIIV : Zkouším jednoduchou 2D skákačku s trochou fyziky. A pro začátek bych si chtěl zkusit napsat všechno sám, ať mám lepší představu jak to všechno vlastně funguje.
No, ale ještě pohledám, tento týden mám na všechno strašnou smůlu, takže třeba se mi v pondělí zadaří...

co to je za podivnou hru ze tam testujes 100 pruniku na kazdou iteraci? mozna bych to zjednodusil tim ze bych nektere z mene dulezitych kolizi (jestli nejake takove jsou) zjednodusil testovanim pruniku ctvercu ve kterych ty mnohouhelniky lezi, to je o neco snazsi.
a jak vlastne testujes prunik usecky?

KIIV napsal:
To yaqwsx : pokud pamatuju z grafiky tak byl i algorytmus kterej prochazel radky obrazovky a kdyz narazil na okraj nejakeho objektu zacal vyplnovat dokud nenarazil na nejakej dalsi okraj... hadam ze tobe by stacila verze kde bys kontroloval jen radky kde sou nejaky hrany
ale kdo vi k cemu to vlastne potrebujes