Průnik 4-úhelníků mezi sebou – Matematika – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
yaqwsx+9
Posthunter
4. 4. 2009   #1
-
0
-

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

Nahlásit jako SPAM
IP: 85.160.68.–
Life is too short to remove USB mass storage safely...
Správný drsňák udělá z konzole cokoliv
Reklama
Reklama
KIIV+42
God of flame
4. 4. 2009   #2
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.1.–
Program vždy dělá to co naprogramujete, ne to co chcete...
tmi0
Věrný člen
4. 4. 2009   #3
-
0
-

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.

Nahlásit jako SPAM
IP: 213.226.226.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
KIIV+42
God of flame
4. 4. 2009   #4
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.1.–
Program vždy dělá to co naprogramujete, ne to co chcete...
yaqwsx+9
Posthunter
4. 4. 2009   #5
-
0
-

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

Nahlásit jako SPAM
IP: 85.160.86.–
Life is too short to remove USB mass storage safely...
Správný drsňák udělá z konzole cokoliv
tmi0
Věrný člen
4. 4. 2009   #6
-
0
-

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

Nahlásit jako SPAM
IP: 213.226.226.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
yaqwsx+9
Posthunter
4. 4. 2009   #7
-
0
-

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é!

Nahlásit jako SPAM
IP: 85.160.86.–
Life is too short to remove USB mass storage safely...
Správný drsňák udělá z konzole cokoliv
yaqwsx+9
Posthunter
4. 4. 2009   #8
-
0
-

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

Nahlásit jako SPAM
IP: 85.160.86.–
Life is too short to remove USB mass storage safely...
Správný drsňák udělá z konzole cokoliv
KIIV+42
God of flame
4. 4. 2009   #9
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.1.–
Program vždy dělá to co naprogramujete, ne to co chcete...
yaqwsx+9
Posthunter
4. 4. 2009   #10
-
0
-

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ří...

Nahlásit jako SPAM
IP: 85.160.86.–
Life is too short to remove USB mass storage safely...
Správný drsňák udělá z konzole cokoliv
tmi0
Věrný člen
4. 4. 2009   #11
-
0
-

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?

Nahlásit jako SPAM
IP: 213.226.226.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
Yety0
Stálý člen
6. 5. 2009   #12
-
0
-

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



Jj, ja bych to asi resil stejně

Nahlásit jako SPAM
IP: 94.113.49.–
Kapitán A. J. Rimmer vesmírný dobrodruh
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 7 hostů

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý