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.

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

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

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.

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?

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

x

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

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?

[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?

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