Bentley-Ottmann algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. marts 2020; verifikation kræver 1 redigering .

Bentley-Ottmann-algoritmen (1979) gør det muligt at finde alle skæringspunkter for lige linjesegmenter i planet . Den bruger metoden med at feje linje [1] (feje lige linje [2] , flytte lige linje [3] , scanne linje [4] ; feje linje ) . Metoden bruger en lodret fejende lige linje, der bevæger sig fra venstre mod højre, mens segmenterne, som den skærer ved en given koordinat , kan ordnes efter koordinaten , så de kan sammenlignes med hinanden (som er højere, hvilket er lavere). Denne sammenligning kan for eksempel udføres ved hjælp af ligningen for en ret linje, der går gennem to punkter (segmenter er givet ved deres to endepunkter): , hvor , og , er koordinaterne for det første og andet punkt i segmentet, henholdsvis. Den fejende lige linje bevæger sig langs de såkaldte hændelsespunkter (venstre og højre ende af segmenterne, såvel som segmenternes skæringspunkter). Efter skæringspunktet bør segmenterne ombyttes, da f.eks. det øverste af de skærende segmenter efter skæringspunktet bliver det laveste. Algoritmen nedenfor er ikke designet til det tilfælde, hvor to segmenter skærer hinanden i mere end ét punkt. $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 En fejende linje kan også repræsenteres som en vandret linje, der bevæger sig fra top til bund langs koordinaten , og segmenter, der krydser den, kan sammenlignes langs koordinaten . $y$ $x$

Behandling af lodrette segmenter

Der er et problem med det lodrette segment i den forstand, hvordan man sammenligner det over/under med de krydsende segmenter. For at gøre dette kan vi for eksempel antage, at hvis skæringspunktet for de lodrette og ikke-lodrette segmenter er under den aktuelle koordinat for begivenhedspunktet, så er det lodrette segment højere, hvis skæringspunktet er højere end det aktuelle koordinat for begivenhedspunktet, så betragtes det lodrette segment under det, der krydser det. Hvis den aktuelle koordinat er lig med koordinaten for begivenhedspunktet, skal du, når du sletter et segment, overveje, at det lodrette segment er lavere, mens du indsætter det, antage, at det er højere. $y$ $y$ $y$ $y$

Memory Square

I værste fald, når for eksempel alle segmenterne, der krydser hinanden, danner et rektangulært gitter, vil der være skæringspunkter, som skal lagres. For at undgå at bruge hukommelsesfirkanten i algoritmen er det muligt at fjerne skæringspunktet for segmenter, der midlertidigt ophører med at være tilstødende ved en given position af den fejede linje. Disse punkter vil stadig blive fundet igen ved de efterfølgende trin af algoritmen, når de givne segmenter bliver tilstødende igen (Pec, Sherir 1991). $O \venstre(n^2 \højre)$

Algoritme

Pseudokoden nedenfor bruger:

Q er en dynamisk datastruktur uden gentagelser med en logaritmisk tid til at søge, indsætte, slette hændelsespunkter og finde minimumselementet (f.eks. rød-sort træ , 2-3-træ ).
T er en dynamisk datastruktur uden gentagelser med en logaritmisk tid til at søge, indsætte, slette segmenter. Den gemmer alle de segmenter, der skærer den fejende linje (f.eks. rød-sort træ, 2-3 træ).
q - begivenhedspunkt.
newq - har lige fundet skæringspunktet for segmenterne, punktet for begivenheden.
L(q) er det sæt af segmenter, hvis venstre ende er q (for lodrette segmenter anses den nederste ende for at være den venstre ende).
R(q) er det sæt af segmenter, hvis højre ende er q.
I(q) er det sæt af segmenter, der skærer hinanden ved q.

segmenterSkæringspunkter(punkter[]) 1) Q og T initialiseres. Alle ender af segmenterne ordnet efter x-koordinaten indtastes i Q, og hvis de to punkter falder sammen, derefter placeres det venstre endepunkt af segmentet foran det højre endepunkt. Hvis kun x matcher, så er punktet med det mindre y det mindste. T ← ∅ 2) mens Q != ∅ q ←min(Q); procesPunkt(q); procespunkt(q) 1) Find i Q alle segmenter, der indeholder q; // de vil være tilstødende i Q, da de begivenhedspunkter, der er indeholdt i disse segmenter har de samme koordinater; 2) hvis (|L(q)| + |R(q)| + |I(q)| > 1) ELLER (|I(q)| > 0) derefter Returpunkt q; 3) hvis (|I(q)| = 0) OG (|L(q)|+|R(q)| > 0) // ved det betragtede punkt, begynder eller slutter alle segmenter kun; derefter I(q) ← I(q) ∪ L(q) ∪ R(q); // føje til I(q) L(q) og R(q) 4) Fjern fra TR(q) og I(q); 5) Indsæt i TI(q) og L(q); // alle segmenter fra mængden I(q) er fjernet fra T, men nu er de indsat tilbage i ændret rækkefølge efter skæringspunktet; 6) hvis (L(q)∪I(q) = ∅) ELLER (|I(q)| = |R(q)| - 1) Find derefter i T de øvre og nedre naboer af q su og sl; newq = findSkæringspunkt(su, sl); hvis newq != NULL derefter tilføje(Q, newq); 7) andet Lad s′ være det øverste segment fra L(q)∪I(q); Lad su være den øverste nabo til s′ i T; Lad s′′ være det laveste segment fra L(q) ∪ I(q); Lad sl være den nederste nabo af s′′ i T; newq = findSkæringspunkt(su, s′); hvis newq != NULL derefter tilføje(Q, newq); newq = findSkæring(sl, s′′); hvis newq != NULL derefter tilføje(Q, newq); // fjern derefter hukommelsesfirkanten; newq = findSkæringspunkt(sl, su); hvis newq != NULL derefter delete(Q, newq); newq = findSkæringspunkt(s′′, su); hvis newq != NULL derefter delete(Q, newq); newq = findSkæring(sl, s′); hvis newq != NULL derefter delete(Q, newq); find skæringspunkt(sl, su) hvis sl og su skærer hinanden til højre for fejelinjen (eller på fejelinjen over det aktuelle hændelsespunkt) returner derefter newq; ellers returnerer NULL;

Analyse

Lade være antallet af segmenter, være antallet af segmenter, der skærer punktet . Så er tiden til at initialisere Q , og at initialisere T er . Det tager tid at finde alle de segmenter, der passerer gennem punktet og opdatere Q. At opdatere T er også tid. I alt: , hvor er antallet af skæringspunkter . . $n$ $m\venstre(q\højre)$ $q$ $O \venstre(n \log n \højre)$ $O\venstre(1\højre)$ $q$ $O \venstre(m \venstre(q \højre) \log n \højre)$ $O \venstre(m \venstre(q \højre) \log n \højre)$ $O \venstre(n \log n + \sum m \venstre(q \højre) \log n \højre) = O \venstre(n \log n + \log n \sum m \venstre(q \højre) \højre ) = O \venstre( \venstre(n+k \højre) \log n \højre)$ $k$ $\venstre( \sum m \venstre(q \højre) = O \venstre(n+k \højre) \højre)$ $k = O \venstre(n^2 \højre)$

Hukommelse , på grund af det faktum, at skæringspunkterne for segmenter, der ikke længere støder op, fjernes, ellers ville det være , hvor . $O\venstre(n\højre)$ $O \venstre(n + k \højre)$ $k = O \venstre(n^2 \højre)$

Noter

↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
↑ Praparata F., Sheimos M. Computational Geometry: An Introduction = Computational Geometry En introduktion. — M .: Mir, 1989. — 478 s.
↑ Kormen, T. , Leizerson, C. , Rivest, R. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Pr. fra engelsk. udg. A. Shen. — M. : MTsNMO, 2000. — 960 s. - ISBN 5-900916-37-5 .
↑ Laszlo M. Beregningsgeometri og computergrafik i C++. - M. : BINOM, 1997. - 304 s.

Litteratur

Berg M., Cheong O., Creveld M., Overmars M. Computational geometri. Algoritmer og applikationer = Computational Geometry: Algoritmer og applikationer. - M. : DMK-Press, 2016. - 438 s. - ISBN 978-5-97060-406-9 .
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Beregningsgeometri: Algoritmer og applikationer. - Springer, 2000. - 368 s.
Praparatha F., Sheimos M. Computational Geometry En introduktion. — M .: Mir, 1989. — 478 s.
Laszlo M. Beregningsgeometri og computergrafik i C++. - M. : BINOM, 1997. - 304 s.
T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmer. Konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - "Williams", 2005. - 1296 s.