Algoritmul Bentley-Ottmann

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 13 martie 2020; verificarea necesită 1 editare .

Algoritmul Bentley-Ottmann (1979) permite găsirea tuturor punctelor de intersecție ale segmentelor de dreaptă în plan . Utilizează metoda liniei de măturare [1] (linie dreaptă de măturare [2] , linie dreaptă în mișcare [3] , linie de scanare [4] ; linie de măturare ) . Metoda folosește o linie dreaptă de măturare verticală care se deplasează de la stânga la dreapta, în timp ce segmentele pe care le intersectează la o anumită coordonată , pot fi ordonate după coordonată , astfel pot fi comparate între ele (care este mai mare, care este mai mică). Această comparație poate fi efectuată, de exemplu, folosind ecuația unei drepte care trece prin două puncte (segmentele sunt date de cele două puncte finale ale acestora): , unde , și , sunt coordonatele primului și celui de-al doilea punct al segmentului, respectiv. Linia dreaptă de măturare se deplasează de-a lungul așa-numitelor puncte de eveniment (capetele din stânga și din dreapta ale segmentelor, precum și punctele de intersecție ale segmentelor). După punctul de intersecție, segmentele ar trebui să fie schimbate, deoarece, de exemplu, cel mai sus dintre segmentele care se intersectează după punctul de intersecție devine cel mai jos. Algoritmul de mai jos nu este conceput pentru cazul în care două segmente se intersectează în mai mult de un punct. $X$ $y$ $\left(x - x_1 \right)/ \left(x_2 - x_1 \right) = \left(y - y_1 \right)/ \left(y_2 - y_1 \right)$ $x_{1}$ $y_1$ $x_{2}$ $y_2$

NB O linie de măturare poate fi reprezentată și ca o linie orizontală care se deplasează de sus în jos de-a lungul coordonatei , iar segmentele care o traversează pot fi comparate de-a lungul coordonatei . $y$ $X$

Prelucrarea segmentelor verticale

Există o problemă cu segmentul vertical în sensul cum să-l comparăm deasupra/dedesubtul cu segmentele care se intersectează. Pentru a face acest lucru, putem, de exemplu, să presupunem că, dacă punctul de intersecție al segmentelor verticale și neverticale este sub coordonata curentă a punctului eveniment, atunci segmentul vertical este mai mare, dacă punctul de intersecție este mai mare decât cel curent. coordonata punctului eveniment, atunci segmentul vertical este considerat sub cel care îl traversează. Dacă coordonata curentă este egală cu coordonata punctului eveniment, atunci când ștergeți un segment, luați în considerare că segmentul vertical este mai jos, în timp ce îl introduceți, presupuneți că este mai mare. $y$ $y$ $y$ $y$

Piața memoriei

În cel mai rău caz, când, de exemplu, toate segmentele, care se intersectează între ele, formează o rețea dreptunghiulară, vor exista puncte de intersecție care vor trebui stocate. Pentru a evita utilizarea pătratului de memorie în algoritm, este posibil să se elimine punctul de intersecție al segmentelor care încetează temporar să fie adiacente la o poziție dată a liniei de măturare. Aceste puncte vor fi încă găsite din nou la etapele ulterioare ale algoritmului, când segmentele date devin din nou adiacente (Pec, Sherir 1991). $O \left(n^2\right)$

Algoritm

Pseudocodul de mai jos folosește:

Q este o structură de date dinamică fără repetări cu un timp logaritmic pentru căutarea, inserarea, ștergerea punctelor de eveniment și găsirea elementului minim (de exemplu, arbore roșu-negru , arbore 2-3 ).
T este o structură de date dinamică fără repetări cu un timp logaritmic pentru căutarea, inserarea, ștergerea segmentelor. Stochează toate segmentele care intersectează linia de măturare (de exemplu, arbore roșu-negru, arbore 2-3).
q - punct eveniment.
newq - tocmai a găsit punctul de intersecție al segmentelor, punctul evenimentului.
L(q) este mulțimea de segmente al căror capăt din stânga este q (pentru segmentele verticale, capătul inferior este considerat a fi capătul din stânga).
R(q) este mulțimea de segmente al căror capăt drept este q.
I(q) este mulțimea segmentelor care se intersectează în q.

segmenteIntersecții(puncte[]) 1) Sunt inițializate Q și T. Toate capetele segmentelor ordonate după coordonatele x sunt introduse în Q, iar dacă cele două puncte coincid, apoi punctul final din stânga al segmentului este plasat în fața punctului final din dreapta. Dacă doar x se potrivește, atunci punctul cu y mai mic este cel mai mic. T ← ∅ 2) în timp ce Q != ∅ q ←min(Q); processPoint(q); processPoint(q) 1) Găsiți în Q toate segmentele care conțin q; // vor fi adiacente în Q, deoarece punctele de eveniment care sunt conținute în acestea segmentele au aceleași coordonate; 2) dacă (|L(q)| + |R(q)| + |I(q)| > 1) SAU (|I(q)| > 0) apoi punctul de întoarcere q; 3) dacă (|I(q)| = 0) ȘI (|L(q)|+|R(q)| > 0) // în punctul considerat, toate segmentele doar încep sau se termină; atunci I(q) ← I(q) ∪ L(q) ∪ R(q); // se adaugă la I(q) L(q) și R(q) 4) Îndepărtați din TR(q) și I(q); 5) Introduceți în TI(q) și L(q); // toate segmentele din multimea I(q) au fost scoase din T, dar acum sunt inserate inapoi in ordinea schimbata dupa punctul de intersectie; 6) dacă (L(q)∪I(q) = ∅) SAU (|I(q)| = |R(q)| - 1) apoi Găsiți în T vecinii de sus și de jos ai lui q su și sl; newq = findIntersect(su, sl); dacă newq != NULL apoi adauga(Q, newq); 7) altfel Fie s′ segmentul cel mai sus din L(q)∪I(q); Fie su vecinul superior al lui s′ în T; Fie s′′ cel mai de jos segment din L(q) ∪ I(q); Fie sl vecinul inferior al lui s′′ în T; newq = findIntersect(su, s′); dacă newq != NULL apoi adauga(Q, newq); newq = findIntersect(sl, s′′); dacă newq != NULL apoi adauga(Q, newq); // apoi eliminați pătratul de memorie; newq = findIntersect(sl, su); dacă newq != NULL apoi șterge (Q, newq); newq = findIntersect(s′′, su); dacă newq != NULL apoi șterge (Q, newq); newq = findIntersect(sl, s′); dacă newq != NULL apoi șterge (Q, newq); găsiIntersect(sl, su) dacă sl și su se intersectează la dreapta liniei de măturare (sau pe linia de măturare deasupra punctului evenimentului curent) apoi returnează newq; altfel returnează NULL;

Analiză

Fie numărul de segmente, fie numărul de segmente care intersectează punctul . Atunci timpul pentru a inițializa Q este , iar pentru a inițializa T este . Este nevoie de timp pentru a găsi toate segmentele care trec prin punct și pentru a actualiza Q. Pentru a actualiza T este, de asemenea, timpul. Total: , unde este numărul de puncte de intersecție . . $n$ $m\stânga(q\dreapta)$ $q$ $O \left(n \log n \dreapta)$ $O\stânga(1\dreapta)$ $q$ $O \left(m \left(q \right) \log n \right)$ $O \left(m \left(q \right) \log n \right)$ $O \left(n \log n + \sum m \left(q \right) \log n \right) = O \left(n \log n + \log n \sum m \left(q \right) \right ) = O \left( \left(n+k \right) \log n \right)$ $k$ $\left( \sum m \left(q \right) = O \left(n+k \right) \right)$ $k = O \left(n^2 \right)$

Memorie , din cauza faptului că punctele de intersecție ale segmentelor care nu mai sunt adiacente sunt eliminate, altfel ar fi , unde . $O\stânga(n\dreapta)$ $O \left(n + k \dreapta)$ $k = O \left(n^2 \right)$

Note

↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmi: construcție și analiză = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
↑ Praparata F., Sheimos M. Computational Geometry: An Introduction = Computational Geometry An introduction. — M .: Mir, 1989. — 478 p.
↑ Kormen, T. , Leizerson, C. , Rivest, R. Algorithms: construction and analysis = Introduction to Algorithms / Per. din engleza. ed. A. Shen. — M. : MTsNMO, 2000. — 960 p. - ISBN 5-900916-37-5 .
↑ Laszlo M. Computational geometry and computer graphics in C++. - M. : BIOM, 1997. - 304 p.

Literatură

Berg M., Cheong O., Creveld M., Overmars M. Computational geometry. Algoritmi și aplicații = Computational Geometry: Algorithms and Applications. - M. : DMK-Press, 2016. - 438 p. - ISBN 978-5-97060-406-9 .
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Geometrie computațională: algoritmi și aplicații. - Springer, 2000. - 368 p.
Praparatha F., Sheimos M. Computational Geometry O introducere. — M .: Mir, 1989. — 478 p.
Laszlo M. Geometrie computațională și grafică pe computer în C++. - M. : BIOM, 1997. - 304 p.
T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmi. Construcție și analiză = Introducere în algoritmi. - Ed. a II-a. - „Williams”, 2005. - 1296 p.

Link -uri

Vizualizatorul este un caz special (algoritmul Sheimos-Goy, 1976 (determinarea prezenței segmentelor care se intersectează)).