Bine ai venit guest
 
User:
Pass:

[Creare cont]
[Am uitat parola]
iBac = materialul ULTRACOMPLET de pregătire pentru bac la mate. Dacă vrei poţi.
Forum pro-didactica.ro  [Căutare în forum]

Forum » Matematic─â aplicat─â » Localizarea intr-un PSLG. Metoda lespezilor.
[Subiect nou]   [Răspunde]
[1] [2]  »   [Ultima pagină]
Autor Mesaj
Blaugranas
Grup: membru
Mesaje: 69
12 Jul 2019, 15:31

[Trimite mesaj privat]

Localizarea intr-un PSLG. Metoda lespezilor.    [Editează]  [Citează] 

Un PSLG e o structura geometrica , plana formata din 3 multimi:
a) O multime de puncte din plan date prin coordonatele lor, ce se vor numi Varfuri V=

b) O multime de segmente de forma
,i diferit de j cu proprietatea
Adica se poate ca doua muchii sa aiba sursa sau destinatia aceeasi... nu ambele + intersectia oricaror 2 astfel de segmente e multimea vida. Aceste segmente se vor numi Muchii si vor fi orientate.
c) O multime de regiuni, (vor fi poligoane simple si o regiune nemarginita), determinate de muchiile PSLG-ului, numite Fete.
In plus : orice varf apartine la cel putin 2 muchii, PSLG-ul(planar straight line-graph) e structura conexa.
Structura de date folosita ptr stocarea unui PSLG o vom numi DCEL. El arata cam asha
E : 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10.
V1 : 5 , 3 , 7 , 6 , 4 , 5 , 1 , 5 , 5 , 6 .
V2 : 2 , 1 , 4 , 2 , 1 , 3 , 7 , 6 , 7 , 7 .
F1 : 1 , 2 , 1 , 3 , 1 , 2 , 2 , 3 , 5 , 1 .
F2 : 3 , 1 , 4 , 1 , 4 , 1 , 4 , 5 , 2 , 5 .
P1 : 8 , 6 , 7 ,10, 3 , 1 , 5 , 9 , 6 , 8 .
P2 : 4 , 7 , 5 , 1 , 2 , 2 , 9 , 4 ,10, 3 .

Ptr fiecare muchie i vom avea nevoie de 6 campuri de informatii:
V1(i) = varful din care pleaca muchia i
v2(i) = varful in care ajunge muchia i
F1(i) = fata aflata la dreapta muchiei i
F2(i) = fata aflata la stanga muchiei i
P1(i) = prima muchie intalnita cand rotesc muchia i in sens direct trigonometric in jurul lui V1(i)
P2(i) = prima muchie intalnita cand rotesc muchia i in sens direct trigonometric in jurul lui V2(i)
Ipoteza :
1) Nu exista 2 puncte cu aceeasi ordonata.
2) Ptr fiecare varf cu exceptia celui de sus si al celui de jos, exista si muchii care intra in varful respectiv (vin de jos) si muchii care ies (pleaca in sus).
Concluzie :
Se doreste localizarea unui punct (sau mai multe puncte) in acest PSLG cu ajutorul acestor date prin metoda lespezilor. Cine doreste ii pot da si detalii ptr cum sa priveasca problema.

Blaugranas
Grup: membru
Mesaje: 69
07 Oct 2012, 20:16

[Trimite mesaj privat]


Vad ca nu e nimeni interesat! Oricum eu o sa pun solutia in seara asta cel tarziu maine seara!

gauss
Grup: Administrator
Mesaje: 6856
08 Oct 2012, 23:37

[Trimite mesaj privat]


O structura de forma celei aratate pe
http://en.wikipedia.org/wiki/Planar_straight-line_graph
poate fi cat de cat vizualizata.

Daca problema este de a vedea pe care fata (componenta conexa a planului fara multimea de segmente muchii) se afla un punct dat din plan, reactia mea este cea de a imparti fiecare fata in triunghiuri, dupa care pot decide imediat in care triunghi se afla un punct dat. Deoarece este foarte greu sa introduc date, modul aceste de abordare mi se pare suficient...


---
df (gauss)
Blaugranas
Grup: membru
Mesaje: 69
08 Oct 2012, 23:52

[Trimite mesaj privat]


Pas 1: Renumerotam varfurile a.i. sa fie numerotate de jos in sus. Utilizand ordonatele varfurilor le ordonez de jos in sus. [O(2)=1,O(6)=2,O(5)=3,O(7)=4,O(3)=5,O(4)=6,O(1)=7]. Se modifica V1 si V2 astfel.
Pentru i=1,n
V1=O[V1] si V2=O[V2]
Pas 2: Reorientam muchiile a.i. fiecare muchie sa aibe sensul de jos in sus. (y[V1]<y[V2])
Pentru i=1,n
Daca y[V1]>y[V2]
V1<->V2 si F1<->F2 si P1<->P2
Pas 3: Organizarea PSLG-ului pentru a permite cautarea binara. Vom utiliza tehnica de "maturare a planului". Aceasta tehnica necesita urmatoarele elemente.
-> O structura geometrica pentru care solicit informatii (va fi maturata)
-> O dreapta ce se deplaseaza paralel cu o directie data si matura structura (linie maturatoare); aceasta dreapta va oferi informatiile cerute in momentul in care taie structura.
-> Starea liniei maturatoare=informatiile oferite de linia maturatoare.
-> Secventa punctelor de salt=pozitiile succesive ale liniei maturatoare; aceste puncte tb alese a.i. intre 2 puncte succesive de salt starea liniei maturatoare sa ramana neschimbata. In cazul nostru:
Structura maturata=PSLG
Linia maturatoare va fi o dreapta paralela cu axa Ox.
Informatiile cerute=muchiile taiate de linia maturatoare ordonate de la stanga la dreapta.
Secventa punctelor de salt= varfurile PSLG-ului.
Lespedea= regiunea cuprinsa intre 2 pozitii succesive ale liniei maturatoare.
Construim ptr fiecare varf i, (i=1,n) 2 multimi ordonate. A=muchiile care intra in varful i si B=muchiile care ies din varful i, ordonate in sens trigonometric in jurul punctului i.











Pentru i=2,n-1
se obtine din
inlocuind
cu









Am obtinut astfel structura cautata (aceste liste). Pentru un punct M dorim localizarea in timp logaritmic. Printr-o cautare binara localizam punctul M intr-o lespede.
Daca
sau
M e in exterior deci Fata 1. (F1)
Daca M se afla pe una din pozitiile liniei maturatoare aleg una din cele 2 lespezi delimitate de aceasta cu exceptia primei pozitii si a ultimei.
Daca
daca
=>M={1}
daca
diferit de
=>

Daca
daca
=>M={n}
daca
diferit de
=>

Dupa localizarea lui M intr-o lespede printr-o cautare binara localizam punctul M in multimea ordonata a muchiilor ce apar in lespedea respectiva. Cu aceste date puteti elabora un algoritm. Voi pune unul in limbajul C ptr cei interesati.

Blaugranas
Grup: membru
Mesaje: 69
09 Oct 2012, 00:04

[Trimite mesaj privat]


Da domnule Gauss aveti si dvs dreptate cu triunghiurile. Aceasta este intuitiv varianta pe care merge studentu`. Dar noi adica eu in calitate de informatician n-am voie sa fac asha ceva. Pai daca ma duc cu un algoritm din asta la prof ma da ala afara in suturi. Trebuie s-o luam pe scurtatura. Impartirea in zone regiuni de triunghiuri nu prea e omeneasca mai ales ca am pus o gramada de restrictii problemei... exact ptr a folosi aceasta metoda 'inginereasca' a lespezilor. Iar cand faceti toate triunghiurile acelea ganditi-va ce risipa facetzi! Eu nu am nevoie de triunghiuri. Daca am un PSLG de 10 noduri si doar 9 muchii ce fac ? Ma apuc si construiesc triunghiuri in +? Nu e eficient! M-ati inteles?

Blaugranas
Grup: membru
Mesaje: 69
09 Oct 2012, 12:05

[Trimite mesaj privat]


12 18
-8 1
8 10
7 -6
-15 5
2 3
1 12
5 -10
3 -5
-10 -4
1 -9
-3 8
1 7
11 4 1 0 13 3
12 2 2 5 16 15
9 4 0 1 4 1
9 10 4 0 17 12
10 8 4 7 4 14
5 11 3 2 8 7
6 11 2 0 18 1
5 7 6 3 9 14
3 5 6 5 10 16
7 3 6 0 8 15
1 8 3 4 13 5
7 10 0 7 10 5
1 11 1 3 17 6
7 8 7 3 12 11
2 3 0 5 18 9
5 12 2 5 6 2
1 9 4 1 11 3
2 6 2 0 2 7
3 5

Acesta este fisieru` de intrare lespede.txt care tb sa fie in acelasi folder cu executabilu`.

Blaugranas
Grup: membru
Mesaje: 69
09 Oct 2012, 12:09

[Trimite mesaj privat]


x

Euclid
Grup: Administrator
Mesaje: 2653
09 Oct 2012, 23:33

[Trimite mesaj privat]


[Citat]

...
...
Ipoteza :
1) Nu exista 2 puncte cu aceeasi ordonata.
2) Ptr fiecare varf cu exceptia celui de sus si al celui de jos, exista si muchii care intra in varful respectiv (vin de jos) si muchii care ies (pleaca in sus).
Concluzie :
Se doreste localizarea unui punct (sau mai multe puncte) in acest PSLG cu ajutorul acestor date prin metoda lespezilor. Cine doreste ii pot da si detalii ptr cum sa priveasca problema.


Ma tem ca nu am inteles intrebarea... ce se intelege prin "localizare" ?

De asemenea, ipoteza 1) nu este rezonabila (daca vorbim de o problema din lumea reala).


---
Euclid
Blaugranas
Grup: membru
Mesaje: 69
10 Oct 2012, 14:14

[Trimite mesaj privat]


1) Ipoteza asha este n-ai cum s-o schimbi. Daca sunt 2 puncte cu aceeasi ordonata atunci nu se mai poate aplica metoda lespezilor deoarece lespedea ar fi paralela cu o muchie ceea ce nu vrem... deci tb s-o iei ca atare! (dar daca vrei sa-ti complici existenta aplicand algoritmul pe un astfel de PSLG n-ai decat).
2) Prin localizare inteleg gasirea fetei din care face parte punctul. Gandeste-te ca u ai anumite muchii din acest graf nu toate gandeste-te ca ai o parte din fete nu toate si cautam algoritmi eficienti pentru gasirea fetei din care face parte punctul (in plan).
3) Acum e cam tarziu am dat solutia deja... o sa postez maine o problema asemanatoare daca vrei?

Euclid
Grup: Administrator
Mesaje: 2653
10 Oct 2012, 21:37

[Trimite mesaj privat]


[Citat]
Un PSLG e o structura geometrica , plana formata din 3 multimi:
a) O multime de puncte din plan date prin coordonatele lor, ce se vor numi Varfuri V=

b) O multime de segmente de forma
,i diferit de j cu proprietatea
Adica se poate ca doua muchii sa aiba sursa sau destinatia aceeasi... nu ambele + intersectia oricaror 2 astfel de segmente e multimea vida. Aceste segmente se vor numi Muchii si vor fi orientate.
c) O multime de regiuni, (vor fi poligoane simple si o regiune nemarginita), determinate de muchiile PSLG-ului, numite Fete.
In plus : orice varf apartine la cel putin 2 muchii, PSLG-ul(planar straight line-graph) e structura conexa.


Conform definitie, eu inteleg ca ceva de genul
[Cod]

*--->*
|
|
v
*

se incadreaza in acele conditii. Care sunt fetele?


---
Euclid
Blaugranas
Grup: membru
Mesaje: 69
10 Oct 2012, 22:15

[Trimite mesaj privat]


Mister... ordonatele tb sa difere... chiar nu intelegi? Iar o fata are pe putin 3 muchii!!!

[1] [2]  »   [Ultima pagină]


Legendă:  Access general  Conţine mesaje necitite  46782 membri, 57439 mesaje.
© 2007, 2008, 2009, 2010 Pro-Didactica.ρ