.: Rubriky
plus 1) Poezie a próza
plus 2) Hudba
plus 3) Galerie
mínus 4) Film
mínus 5) Divadlo
plus 6) Věda a technika
plus 7) Mozaika (ostatní)
plus 8) Projekty POSTŘEHU

 .: Chci...
... se stát autorem
... znát lidi kolem Postřehu
... sponzorovat Postřeh
... vložit/upravit článek
Boží Dar
 .: Free MP3 album!
Vinylová budoucnost 2008 Vinylová budoucnost 2007

 .: Články podle data
<<  Leden  >>
PoÚtStČtSoNe
    1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

 .: Online
Stránku si právě čtou 3 lidé.
 .: Informace
magazín Postřeh
ISSN 1803-5639
Národní knihovna ČR:
001686222
TOP 15, Fotogalerie
Chata v České KanaděChataUbytování velkých skupinPenzion v Jižních ČecháchPenzion v KunžakuRybařeníJižní ČechyPenzion StrmilovKomorníkChata u rybníka KomorníkaUbytování Česká KanadaKomorníkUbytování v Jižních Čechách
 .: Login

Jméno (přezdívka)
Heslo


Registrace nového čtenáře

 

Komentáře
ke článku: Zjíštění průniku x n-úhelníků pomocí analytické geometrie
(ze dne 22.06.2007, autor článku: Dominik Janků)

Jméno (přezdívka): 
E-mail: 
Titulek: 
Čarodějnice létá na: 
(Ochrana proti spamu
doplňte slovo do pole)
 


zbývá znaků:   zapsáno znaků:

    

V rámci komentářů nelze používat HTML tagy.

Pro vložení tučného textu, hyperlinku nebo e-mailové adresy využijte následující značky:
[b]tučné[/b], [odkaz]www.domeny.cz[/odkaz], [email]jmeno@domena.cz[/email]

S vložením komentáře souhlasíte s našimi podmínkami

************** * **************

Zjíštění průniku x n-úhelníků pomocí analytické geometrie
Doufám, že Vás podivný nadpis příliš nevystrašil. Samotný obsah snad již tak strašidelný nebude... Jednoduše si ukážeme způsob, pomoci kterého jsme schopni zjístit, zda-li se několik objektů s určenými body neprotlo...

Nutnost vyřešit tento problém vyvstala během psaní hry Tuxes. Pro zběžné obeznámení jen zmíním, že se jedná o chodící tučňáky se schopností střílet do tučňáků ostatních pomocí rozmanitých zbraní :) 

Když jsem měl k dispozici jen pistoli, problém moc složitý nebyl. Kulky z pistole letí rovnoměrně a případný zásah se dá odvodit pohým porovnáním souřadnic se souřadnicemi hráče. Vše se ale zkomplikovalo ve chvíli, kdy jsem hru spustil na pomalém počítači, který nedokázal vypočítat let kulky dostatečně rychle. Nastal nepříjmený efekt přestřeleného hráče. Při prvním snímku se kulka nacházela před hráčem, v druhém pak už za ním. Kulka by tedy měla hráče zasáhnout, ale program o tom neměl potuchy. Dalším podnětem pak byla dráha kulek, vystřelených z brokovnice. Jak všichni víme, dochází zde k "rozprsknutí" na všechny strany a dráha se stává nerovnoměrnou (tudíž nemohu použít metodu porovnávání souřadnic, která je možná jen v obdélnikovytých obrazcích).

Jako nejschůdnější řešení problému se pak jevilo spojit staré souřadnice s novými a propočítat průnik s hranami hráče na případný zásah. Obrázek bude názornější: 

hrac a kulka.png


Předpokládejme tedy, že jak kulka tak hráč jsou určeny 4 body, které je ohraničují. Kulka i hráč jsou čtyřúhelníky. Průnik zjísíme tak, že porovnáme 2 rovnice přímek v parametrickém tvaru a stanovíme podmínku, že oba výsledky rovnic musí náležet do intervalu <0; 1>, což je podmínkou toho, aby se jednalo o průnik úseček, nikoliv přímek. Ten stejný postup opakujeme takovým způsobem, aby se každá úsečka z jednoho objektu, porovnala s každou úsečkou objektu druhého. Celkem budeme potřebovat vypočítat 4 * 4 * 2 rovnic (v tom horším případě), v tom lepším případě nám budou stačit výpočty 2, pakliže výsledek každého z nich bude v intervalu <0; 1>, pak budeme moci stanovit průnik - tedy průstřel objektu.

Dost bylo zamotané teorie. Nyní se podíváme jak na to, z pohledu matematiky. Příklad si ukážeme na 2 úsečkách, u kterých budeme zjíšťovat průnik. Parametricky je úsečka v rovině (2D) určena těmito rovnicemi:

x = X+u1t
y = Y+u2
Kde X a Y je x-ová a y-ová souřadnice bodu, který leží na přímce a u1, u2 jsou souřadnice směrového vektoru přímky. Písmenko t je pak poloha na přímce. Právě toto t musí náležet do intervalu <0; 1>, začátek (0) a konec (1). Máme-li 2 body, které určují úsečku:
A = [XA; YA]
B = [XB; YB]
pak u1 = (XB-XA)u2 = (YB-YA)
Nechť máme 2 úsečky, z nihž ta první je tvořena body A, B a druhá body C,D:
A = [XA; YA], B = [XB; YB], u = (XB-XA; YB-YA)
C = [XC; YC], D = [XD; YD], v = (XD-XC; YD-YC)
Z předchozích řádků je patrné, že již máme 2 směrové vektory. Pro úsečku AB je to vektor u. Pro úsečku CD pak vektor v. Pro úplnost ještě napíši parametrickou rovnici úsečky AB:
x = XA + (XB-XA)t = XA + u1t
y = YA + (YB-YA)t = YA + u2t

Nyní obě rovnice obou úseček porovnáme. Tzn. x jedné se bude rovnat x druhé:

XA + u1t = XC + v1s
YA + u2t = YC + v2s

Je jasné, že dvě úsečky nemohou mít stejná písmenka t, proto jedne z nich přiřadíme t a druhé s. Pakliže bude s, t náležet do intervalu <0; 1>, usečky se protly. V opačném případě se protly přímky (pakliže nejsou rovnoběžné) a to my nechceme. Nyní už jen stačí pomocí algebraických úprav odvodit rovnici pro t a rovnici pro s tak, abychom za ně mohli dosadit libovolné body:

s = (u1*(YA-YC) - u2*(XA-XC)) / (u2*v1 - u1*v2)
t = (v1*(YA-YC) - v2*(XA-XC)) / (u1*v2 - u2*v1)

Všechny body známe, směrové vektory umíme vypočítat. Náše snaha je tedy u konce a ta má také :) Pokud někdo nalezne jednodušší způsob, nechť mě o něm informuje, rád se na něj podívám. Prozatím je toto jedinná a univerzální možnost, jak testovat průnik několika objektů tvořené několika body (tedy alespoň dvěmi). Jak můžete vidět, výpočet to není nikterak triviální, zvláště když vememe v potaz jeho častou iteraci. Kdybychom měly tři objekty a každý z nich by byl tvořen 5 body, museli bychom provést max. 250 výpočtů (!) než bychom zjístili, že se neprotly. To už je docela síla :) Proto programování a počítačům zdar! 

 



 .: Služby & akce PT




 

 

(c) Postřeh team 2001 - 2009        postaveno na českém opensource redakčním systému phpRS

 

fotografie

|

grafika

|

hudba

|

literatura

|

umění

|

galerie

|

poezie

|

gramodeska

|

ars polyri

|

věda

|

elektro

|

technika

|

radio

|

bastlení

|

konstrukce

|

schémata

optimalizace PageRank.cz