Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Rotaciono skeniranje?

[es] :: Art of Programming :: Rotaciono skeniranje?

[ Pregleda: 3872 | Odgovora: 18 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

BIHacker

Član broj: 16804
Poruke: 13
*.as.ka.bih.net.ba.



Profil

icon Rotaciono skeniranje?24.11.2003. u 21:23 - pre 213 meseci
Da li je moguce napisati proceduru ili funkciju u C-u ili Pascalu koja bi radila rotaciono skeniranje u sljedecem:
u datom polju (100*100), nalazi se K broj kamenova (kamenovi su pravilna geometrijska tijela, date su kordinate vrhova, kamenovi se ne poklapaju)
U tom polju nalazi se posmatrac,date su koordinate njegove pozicije.
Na svakom metru ivice tog polja nalazi se po jedan stap, e sad je potrebno izracunati koliko posmatrac vidi tih stapova.
Ev na slici je sve mnogo jasnije

nix
Prikačeni fajlovi
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 799
80.93.225.*



+61 Profil

icon Re: Rotaciono skeniranje?25.11.2003. u 11:44 - pre 213 meseci
Nadji negde osnove linearne algebre, a za dalje...pa zavisi kako organizujes skeniranje.
Na primer, moze posmatrac da skenira stapove jedan po jedan, mogu stapovi da skeniraju posmatraca (i time definisu svoju vidljivost), a moze i kamen da odredjuje prohodnost pravca posmatrac-stap. Pod pojmovima posmatrac, stap, kamen mislim naravno na objekte...

Rajko
 
Odgovor na temu

BIHacker

Član broj: 16804
Poruke: 13
*.as.ka.bih.net.ba.



Profil

icon Re: Rotaciono skeniranje?25.11.2003. u 17:37 - pre 213 meseci
e tu i jest problem, kako da provjerim dal je pravac posmatrac-stap prohodan, to jest da li duz posmatrac-kamen prolazi kroz neki kamen, dal postoji mozda neka matematicka formula za to?

nix
 
Odgovor na temu

leka
Dejan Lekić
senior software engineer, 3Developers
Ltd.
London, UK

Član broj: 234
Poruke: 2534
*.racasse.se

Sajt: dejan.lekic.org


+2 Profil

icon Re: Rotaciono skeniranje?25.11.2003. u 17:59 - pre 213 meseci
Ja bih to resio "pesacki" - svaki kamen je neki poligon jel'te, svaki poligon se sastoji od konacnog broja duzi. Vec postoji gotov nacin da se ispita da li prava sece duz (duz je zapravo deo prave od tacke A do tacke B). Posto imas pravac (pravu) kojom posmatrac treba da "ide", onda samo treba da odradis jednu rutinu koja ce da ispita da li ta prava sece duzi koje pripadaju poligonu koji zapravo predstavlja taj objekat (kamen). Ako sece makar jednu duz onda mozes bez problema da setujes neku varijablu na TRUE, koja indikuje da kamen lezi na putu posmatraca...

Sad mozemo malo i da zakomplikujemo, pa da definisemo i putanju kao prostor izmedju dva poligona (koji nisu zatvoreni, logicno) i da postavimo pitanje da li posmatrac (dat takodje kao poligon (objekat)) moze da se "provuce" pored kamena i "zida" :) itd.
Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin
 
Odgovor na temu

BIHacker

Član broj: 16804
Poruke: 13
*.as.ka.bih.net.ba.



Profil

icon Re: Rotaciono skeniranje?25.11.2003. u 19:26 - pre 213 meseci
To sam i ja prvo pomislio kada sam poceo rjesavati problem,i to sigurno ce dati rjesenje.Al problem je u vremenu, posto broj kamenova moze biti do 5000 a program treba u roku 2 sec dat rjesenje.

Kao npr.situacija na slici,gdje imamo 2 kamena, i ja sam tu proceduru ("rotaciono skeniranje") zamislio da u prvom prolazu izvrsi samo ogranicavanje (kao crvene linije na slici) a zatim u drugom izvrsi samo preprojavanje stapova koji su ostali u "vidljivim" djelovima.Sad kako to programski realizovati...?

Komplikovano :))
nix
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.verat.net

Sajt: localhost


+4 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 01:46 - pre 213 meseci
naravno da bi to bilo najsporije rešenje. to kako si ti počeo sa crvenim granicama je dobra ideja, ali nije potpuna.

elem, da bi našao sve zelene površine na slici, treba da odbaciš sve druge.

počni recimo od donjeg kamena na tvojoj slici. nađeš njegovu "najleviju" i njegovu "najdesniju" tačku, gledano iz ugla posmatrača. to su njegova gornja-leva i donja-desna tačka u ovom primeru.

zatim, izračunaš uglove pod kojim posmatrač vidi te tačke (ako posmatrača translacijom staviš u centar koordinatnog sistema, onda ugao tačke (x,y) računaš kao arctan(x/y)) i sve između tog najmanjeg i najvećeg ugla (tj između "najlevije" i "najdesnije" tačke za taj kamen) je nevidljivo.

ovaj postupak ponoviš za svo kamenje, i dobiješ da su neviljivi uglovi npr od 13-24, 150-191 i 230-299 stepeni. zatim lepo prođeš kroz sve stubove, i za svaki izračunaš ugao pod kojim ga vidi posmatrač (opet ista formula) i odbaciš sve koji upadaju u jedan od ovih intervala.

(alternativno, ova provera možda može i brže ako jednostavno ispituješ da li je tačka ispot/iznad ovih graničnih pravi, ali tu ima malo više spec slučajeva, a i nisam sugran koliko brže bi to stvarno i bilo, jer svi moderni procesori u FPU imaju tablice za sinusne/kosinusne i sve izvedene funkcije, pa je i to računanje arctan() prilično brzo)




e to je bilo prosto i elegantno rešenje. ali kao što rekoh, nije kompletno. vidi dopunjenu sliku. zaboravio si da računaš i ove plave delove kao vidljive.



nažalost, ne mogu baš da vidim elegantan način za određivanje koji su tačno stubići u toj plavoj oblasti. naravno, prost metod je da računaš udaljenost stubića od posmatrača (koren iz x2+y2), i da ispituješ da li je štap bliži od kamena, ali se to komplikuje u okolini samog kamenja (baš primetno oko trouglastog kamena)

no, ovo bi trebalo da ti bude dosta domaćeg za danas.. možda u međuvremenu neko nešto i smisli ;)


// inače: ovo je više za forum Art of Programming, pa se moli moderator...
Prikačeni fajlovi
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
..-chandran.sbs.auckland.ac.nz



+3 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 02:15 - pre 213 meseci
Citat:
BIHacker:
To sam i ja prvo pomislio kada sam poceo rjesavati problem,i to sigurno ce dati rjesenje.Al problem je u vremenu, posto broj kamenova moze biti do 5000 a program treba u roku 2 sec dat rjesenje.
Pa ako je polje 100*100 a ako su kordinate celi brojevi onda ce ti raditi krace od 2 sec.
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.verat.net

Sajt: localhost


+4 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 03:57 - pre 213 meseci
Citat:
srki:
Pa ako je polje 100*100 a ako su kordinate celi brojevi onda ce ti raditi krace od 2 sec.


hm...

10,000 stubića * 5,000 poligona * 6 stranica po kamenu (prosečno) = 300,000,000 ispitivanja.

a svako ispitivanje podrazumeva računanje jednačina za dve prave, nalaženje tačke preseka, i proveru da li je ta tačka u datom intervalu (na datoj duži).

nisam siguran da to može da se izvede za dve sekunde.. ti?
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 05:44 - pre 213 meseci
a mislis da ces za svih 10 000 stubica proveravati 5000 poligona? Pa cim naletis na jedan poligon ti prekida. Sto je veci broj poligona to je veca sansa da naletis na jedan za koji ce seci pravu do posmatraca. Driga stvar je sto ne moras da ides po stubicima nego po poligonima pa cim za jedan poligon vidis da neki stubici ne mogu da se vide onda vise ne proveravas za ostale poligone.
Mislim da moze da se uradi za 2 sec.
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.verat.net

Sajt: localhost


+4 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 06:10 - pre 213 meseci
"u najgorem slučaju" (a sve ovo posmatramo iz tog ugla), poligoni će biti mali (1x1), pa će se retko dešavati da je jedan stubić zaklonjen sa više poligona.

u tom slučaju možemo da pretpostavimo da se broj stubića koji su zaklonjeni sa više poligona potire sa brojem stubića koji nisu uopšte zaklonjeni (znači, za koje MORAŠ da izvrtiš svih 5000 poligona).

znači da si ovim dokazom sveo proj pregledanja na prosečno 2500, zato što je 50% šansa da se poligon koji zaklanja određeni stubić nađe u prvoj polovini pregledanih poligona.


a to drugo što si rekao (da vrtiš po poligonima) se svodi na isto ovo. razmisli ponovo, za svaki poligon moraš da izvrtiš sve stubiće (koji već nisu označeni kao zaklonjeni), i da vidiš da li ih taj poligon zaklanja.


dakle, iako je broj ispitivanja pao na 150,000,000 -- opet mi se ne čini da su 2 sekunde dovoljne...
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 08:13 - pre 213 meseci
Citat:
-zombie-:
a to drugo što si rekao (da vrtiš po poligonima) se svodi na isto ovo. razmisli ponovo, za svaki poligon moraš da izvrtiš sve stubiće (koji već nisu označeni kao zaklonjeni), i da vidiš da li ih taj poligon zaklanja.
E ovo vec moze znatno da se ubrza. Prvo proveris za kamenje koje je najblize posmatracu cime si najveci broj stubica vec oznacio kao nevidljive. Posle moras da proveravas za mnogo manji broj stubica.
 
Odgovor na temu

BIHacker

Član broj: 16804
Poruke: 13
*.as.ka.bih.net.ba.



Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 10:50 - pre 213 meseci

e to je bilo prosto i elegantno rešenje. ali kao što rekoh, nije kompletno. vidi dopunjenu sliku. zaboravio si da računaš i ove plave delove kao vidljive.



nažalost, ne mogu baš da vidim elegantan način za određivanje koji su tačno stubići u toj plavoj oblasti. naravno, prost metod je da računaš udaljenost stubića od posmatrača (koren iz x2+y2), i da ispituješ da li je štap bliži od kamena, ali se to komplikuje u okolini samog kamenja (baš primetno oko trouglastog kamena)


Mislim da ste tu malo pogrijesili, kao sto rekoh stubici se nalaze na stranicama ovog polja i to na svakom metru po 1, znaci posto je polje 100*100 znaci ukupno ima 400 stubica.

I usput hvala vam puno ste pomogli,tu je negdje rjesenje.
nix
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.dialup.xtra.co.nz



+3 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 11:02 - pre 213 meseci
Te sad nam kazes da je tu samo 400 stubica!!!! :-))))
Pa sigurno moze u 2 sec! Gledas samo uglove kako ti je zombie pokazao i vidis koji stubici pripadaju/ne pripadaju uglovima koja pokriva svaki kamen.
 
Odgovor na temu

Dejan Lozanovic
Dejan Lozanovic
Beograd

Član broj: 691
Poruke: 2325
*.vdial.verat.net

Jabber: null@elitesecurity.org
Sajt: speedy-order.com


+75 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 13:36 - pre 213 meseci
He he, pravo da ti kazem imao sam isti problem koji sam resio, vezan za aiarena

http://alas.matf.bg.ac.yu/~mr97209/libaiarena.h

Kod je pod GPL-om, pa ako ti odgovara GPL kao licenca http://www.gnu.org/copyleft/gpl.html
(ili nas nezvanicni prevod http://www.elitesecurity.org/tema/27296 radi boljeg razumevanja samog GPL-a) kontaktiraj me pa cu ti dati kod posto jos uvek razvijam projekat pa nisam nista jos objavio javno.

Ako ti neodgovara GPL onda mogu da ti dam mali hint, uzmi tacku posmatraca i tacke stapova pa onda "crtaj" linije od posmatraca do stapa stim sto ce umesto crtanje tacke u liniji tebi biti ispitivanje uslova da li si naisao na kamen. Najbrzi algoritam za crtanje linija je mid-point algoritam, naci ces ga sigurno na netu.


 
Odgovor na temu

leka
Dejan Lekić
senior software engineer, 3Developers
Ltd.
London, UK

Član broj: 234
Poruke: 2534
*.racasse.se

Sajt: dejan.lekic.org


+2 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 13:41 - pre 213 meseci
libaiarena je kewl ;)
Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin
 
Odgovor na temu

Dejan Lozanovic
Dejan Lozanovic
Beograd

Član broj: 691
Poruke: 2325
*.vdial.verat.net

Jabber: null@elitesecurity.org
Sajt: speedy-order.com


+75 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 13:46 - pre 213 meseci
Citat:
srki:
Te sad nam kazes da je tu samo 400 stubica!!!! :-))))
Pa sigurno moze u 2 sec! Gledas samo uglove kako ti je zombie pokazao i vidis koji stubici pripadaju/ne pripadaju uglovima koja pokriva svaki kamen.


Ma moze i za mnogo manje vremena sta je iscrtati 400 linija sa recimo mid-point algoritmom, to je kod mene na p2 433 mhz odradjeno za 0.15 sec
 
Odgovor na temu

Cybernoid II

Član broj: 14852
Poruke: 528

Sajt: www.youtube.com/watch?v=7..


+1 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 16:31 - pre 213 meseci
Dosta davno radio sam slican algoritam. Najbrze je da se panorama podeli na sekcije od 90 stepeni i koristi z depth buffer 3D projekcije. Svaka linija se predstavi pomocu vektora nomale i ako je naopako okrenuta ne iscrtava se.

Ako ti nije bitno koji kamen zaklanja koji sutbić onda je jednostavno.

Postavi koordinatni početak u posmatrača i razvrstaš duži koje sačinjavaju poligone u 4 grupe prema kvadrantima kojima pripadaju. Onda za svaki stubić proveravaš da li se duž posmatrač-stubić seče sa svakom pozitivno orjentisanom duži u tom kvadrantu, dok ne nađeš prvu koja se seče.

A ako ima više duži poligona kamenja od stubića brže je proveravati obrnuto, tj za svaku duž poligona da li se seče sa duži posmatrač stubić.

Ako još imaš istu konfiguraciju kamenja za različite položaje posmatrača, sortiranje kamenja u BSP ubrzava proces.

Ostaje pitanje da li ćeš koristiti inverzne trigonometrijske funkcije ili osnovne aritmetičke operacije za proveru preseka, odnosno da li ćeš računati ugao pod kojim se vidi kamen i duž te projekcije proveravati za presek ili ćeš svaku duž poligona zasebno, šta je brže?

Potraži na google
fast 2D line segment intersection algorithm
verujem da ćeš naći gotove procedure.



[Ovu poruku je menjao Cybernoid II dana 27.11.2003. u 04:16 GMT]
#!/usr/bin/basho
mv frog ancient_pond
echo "Splash!"
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.verat.net

Sajt: localhost


+4 Profil

icon Re: Rotaciono skeniranje?26.11.2003. u 21:33 - pre 213 meseci
Citat:
BIHacker:
Mislim da ste tu malo pogrijesili, kao sto rekoh stubici se nalaze na stranicama ovog polja i to na svakom metru po 1, znaci posto je polje 100*100 znaci ukupno ima 400 stubica.

I usput hvala vam puno ste pomogli,tu je negdje rjesenje.


pa što nereče odma tako ;)

znači, za tih 400 tačaka, bilo koji algoritam koji ti padne na pamet će završiti za 2 sekunde (a i dalje je onaj moj predlog najlakši ;)
 
Odgovor na temu

Cybernoid II

Član broj: 14852
Poruke: 528

Sajt: www.youtube.com/watch?v=7..


+1 Profil

icon Re: Rotaciono skeniranje?27.11.2003. u 09:55 - pre 213 meseci
Ako poligon predstaviš kao nadovezane vektore u smeru ubrnutom od kazaljke na satu u prvom kvadrantu negativno orjentisani su oni vektori koji idu nagore ulevo i analogno tome.

#!/usr/bin/basho
mv frog ancient_pond
echo "Splash!"
 
Odgovor na temu

[es] :: Art of Programming :: Rotaciono skeniranje?

[ Pregleda: 3872 | Odgovora: 18 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.