Algoritm simplu (pseudo-cod) pentru intersecția segmentului de linie

Încerc să rezolv această întrebare, dar sunt blocat în legătură cu modul de a face acest lucru. Voi posta întrebarea și apoi voi explica unde sunt eu.

Având în vedere un set de segmente de linie orizontală și linii verticale cu dimensiunea totală n, dorim să calculam numărul de segmente orizontale intersectate de fiecare linie verticală. Algoritmul ar trebui să fie de complexitate O (n * logn), și ar trebui să fie obținut prin sortare, urmând o scanare liniară. Un segment orizontal este specificat de două coordonate x și o coordonată y, în timp ce o linie verticală este specificată de o singură coordonată x. Ieșirea este o serie de numere număr [l], una pentru fiecare linie verticală l.

Pentru sortare, cred că aș sorta întregul set cu care linia se termină mai devreme (adică cea mai mică a doua coordonată x, sau în cazul unei linii verticale, doar o singură coordonată x), astfel încât am o progresie liniară prin toate liniile. Sunt doar confuză cu privire la modul în care scanarea liniară după sortare ar trebui să fie jucată. Dacă cineva are sugestii, sfaturi sau recomandări, aș aprecia!

PS: Aceasta este o practică pentru o perioadă de timp, așa că, în timp ce nu este neapărat temele, încă o voi marca ca atare.

0

2 răspunsuri

Mai întâi puneți toate punctele de început/sfârșit ale segmentelor orizontale. și coordonatele x ale liniilor verticale, împreună.

În al doilea rând, sortați-le. Să numim lista sortată L .

În al treilea rând, prin imagistică există o linie de scanare verticală, pornind de la cea mai mare parte a listei de puncte L , care se mișcă spre dreapta.

Ori de câte ori linia de scanare atinge un punct, este fie un punct de pornire al unui segment orizontal, fie un punct final al unui segment orizontal sau o linie verticală.

Și puteți face două lucruri atunci când mutați linia de scanare:

1) păstrați setul de segmente orizontale pe care linia de scanare se intersectează în prezent (ori de câte ori este un punct de început/sfârșit al unui segment orizontal, adăugați/ștergeți-l în/din set)

2) ori de câte ori este o linie verticală, știți că linia verticală este intersectată de toate segmentele orizontale din setul pe care îl mențineți pe drum în 1)

Deci, sortarea este O (nlogn); mutarea liniei de scanare prin lista sortată L este O (n)

Toate în toate, este O (nlogn)

0
adăugat
Sunt un pic confuz ca modul în care acest lucru ar fi implementat într-un algoritm, menținând în același timp cerința de complexitate. Fiecare punct este doar un set (x1, x2) pentru segmentele liniei orizontale și (x) pentru liniile verticale. Dacă ați sfărâmat toate punctele și le-ați pus într-o singură listă, de unde știți care este linia de început/sfârșit/vertical?
adăugat autor Tesla, sursa
@Tesla o modalitate intuitivă ar fi crearea unei structuri, de exemplu Point , care are două câmpuri, un câmp este coordonatul, celălalt indică dacă este un punct de pornire, un punct final sau o linie verticală. Deci, puteți sorta lista Point pe primul câmp și verificați ce se bazează pe al doilea câmp.
adăugat autor xvatar, sursa

The question can be written otherwise:

Foreach horizontal segment (x1,x2), find all the vertical lines that intersect it. You can do that by sorting the vertical lines getting a set of position x.

Acum, executați o căutare binară și poziția x1 în setul lui x, să-i sunăm poziția p1. Faceți același lucru pentru x2, p2. Numărul de intersecții pentru segmentul dat este egal cu p2-p1.

Faceți asta pentru toate segmentele orizontale.

Sorting the vertical segments will take O(klog(k)). Every search is done in O(log(k)) and is done twice for each segment: O(mlog(k)). Where k is the number of vertical lines and m the number of horizontal segments. n = m+k > m,k therefor, the overall complexity is O(nlogn).

0
adăugat
Sunt puțin confuz. De exemplu, dacă aveți o linie orizontală (2,6) și o linie verticală (5), efectuând căutarea binară pentru ambele 2 și 6, veți obține un set (2,5,6) cu p1 = 0 și p2 = 2, corect? Apoi, folosind p2-p1 + 1, veți obține 3, spre deosebire de răspunsul care este doar 1. Am interpretat greșit ceva?
adăugat autor Tesla, sursa
De asemenea, cred că este un pic dificil să vină cu numărul de linii orizontale pe care fiecare linie verticală le traversează cu această metodă, care este rezultatul dorit.
adăugat autor Tesla, sursa
Ei bine, așa cum am imaginat că soluția dvs. a fost că după sortare, aș avea o buclă care se repetă prin toate segmentele de linie orizontală și fiecare iterație are două căutări binare și vine cu numărul de linii verticale care traversează segmentul de linie orizontal actual . Nu am văzut o cale simplă de identificare a liniilor verticale pe care se intersectă. Cred că ați putea adăuga o altă buclă care mărește matricea pentru toate n "p1
adăugat autor Tesla, sursa
Nop, am făcut o greșeală acolo. Nu te-ai gândit. Valoarea corectă nu ar trebui să fie greu de găsit totuși. Rezultatul este p1 = 0, p2 = 1 și nu 2. Trebuie să tratezi 2 cazuri, unul când binary_search găsește valoarea și unul când binary_search returnează un slot gol. Sunt prea somnoros pentru a rezolva acest lucru, dar nu ar trebui să fie greu să ghicesc :)
adăugat autor Samy Arous, sursa
Bineînțeles că se întâmplă dacă un segment se intersectează cu o linie atunci linia intersectează segmentul. E o bijecție. De fiecare dată când un segment intersectează o linie, trebuie doar să creșteți contorul corespunzător. La sfârșitul algoritmului veți avea matricea numărului. Așa cum am spus că sunt cam obosit acum. Voi pune mâna pe mâine și o voi împinge aici.
adăugat autor Samy Arous, sursa