.: 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ě čte 27 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

Zjíštění průniku x n-úhelníků pomocí analytické geometrie

Dominik Janků - 6) Věda a technika - 22. 06. 2007 - 10690 přečtení

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! 

 


Pro ohodnocení článku musíte být registrovaným čtenářem  [Akt. známka: 0 / Počet hlasů: 0]

 
Informační e-mail Upozornit emailem     Vytisknout článek Vytisknout článek

Výpis komentářů:
Komentář ze dne: 19.06.2007 13:57:06     Reagovat    Nový komentář
Autor: neregistrovaný - kainová (@)
Titulek:
Kurňa, to máme na programu ve třetáku,to si teda přečtu.:/

Komentář ze dne: 22.06.2007 10:08:48     Reagovat    Nový komentář
Autor: neregistrovaný - weerwolf
Titulek: jen 2d
zajimave, ale resi problem jen ve 2d. Ve 3d, na komplikovanejsi problemy o objekty, je analiticka geometrie docela neefektivni. Mnohem lepsi je pouzit triangulaci.

Komentář ze dne: 22.06.2007 13:02:52     Reagovat    Nový komentář
Autor: neregistrovaný - kainová (@)
Titulek:
No tak úplně jsem tomu rozuměla,no. Skončila jsem jak začínají ty vzorečky:)) Samo že moje chyba...

Komentář ze dne: 22.06.2007 20:52:49     Reagovat    Nový komentář
Autor: neregistrovaný - Harr (Harr@atlas.cz)
Titulek:
Poctivě jsem pročetla.Nejsem matematik,hry nehraji,ale obdivuji ty,kteří zvládají obojí.Věřím,že pro ně je toto přínosem.

Komentář ze dne: 27.06.2007 19:33:50     Reagovat    Nový komentář
Autor: neregistrovaný - GreenEyes (@)
Titulek:
Zel, je-li nekdo v necem temer totalni analfabet, tak je nejlepsi se k tomu rovnou priznat. Neignoruji zadne clanky. Proste na nektere nemam vdomosti. -)

Komentář ze dne: 10.06.2008 11:42:04     Reagovat    Nový komentář
Autor: neregistrovaný - (@)
Titulek:
ve vzorcich pro s,t mas prohozene u1,u2 a v1,v2

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


  
Komentář ze dne: 20.07.2011 21:35:38     Reagovat    Nový komentář
Autor: neregistrovaný - Andy (@)
Titulek: Re:
No, myslím že originálny zápis je správny. Skúsil som dosadiť konkrétne hodnoty.



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