Алгоритм замітання прямою або алгоритм замітання площини — це алгоритмічна парадигма, яка використовує уявну замітальну пряму або замітальну поверхню для розв'язування різних задач у евклідовому просторі. Це одна з ключових технік обчислювальної геометрії.
Ідея алгоритмів цього типу полягає у використанні уявної прямої (частіше вертикальної), яка рухається площиною і зупиняється у деяких точках, де відбуваються обчислення. Геометричні операції обмежені геометричними об'єктами, які або перетинаються, або прилягають до замітальної прямої, а повний розв'язок доступний, коли пряма пройде через усі об'єкти.
Історія
Цей підхід можна простежити від алгоритмів порядкового сканування в комп'ютерній графіці, потім його використано в ранніх алгоритмах компонування інтегральних схем, у яких геометричний опис інтегральної схеми робився у вигляді паралельних смужок, оскільки повний опис не поміщався в пам'ять.
Застосування
Застосування цього підходу призвело до прориву в обчислювальній складності геометричних алгоритмів, коли Шеймос і Гоуї (англ. Dan Hoey) представили алгоритми пошуку перетину відрізків на площині, і, зокрема, вони описали, як комбінація підходу замітання прямою з ефективними структурами даних (збалансованими двійковими деревами) дозволяє виявити, чи є перетини N відрізків на площині, зі складністю O. Тісно пов'язаний алгоритм Бентлі — Оттманна використовує техніку замітання прямою, щоб отримати всі K перетинів серед будь-яких N відрізків на площині з часовою складністю та складністю за пам'яттю .
Відтоді цей підхід використовувався в розробці ефективних алгоритмів для низки задач, таких як побудова діаграми Вороного (алгоритм Форчуна) і тріангуляції Делоне або булевих операцій над многокутниками.
Узагальнення та розширення
Топологічне замітання — це вид замітання площини з ослабленням вимог до порядку опрацювання точок, що дозволяє уникнути повного сортування точок і дозволяє алгоритму замітання прямою працювати ефективніше.
[en] для побудови геометричних алгоритмів можна вважати різновидом замітання в проєктивно двоїстій площині — проєктивна двоїстість перетворює нахил прямої в площині в x-координату точки в двоїстій площині, так що проходження прямої упорядковано за її нахилом. Таким чином, алгоритм обертового кронциркуля є двоїстим для процесу проходження через точки, відсортовані за їх x-координатами, в алгоритмі замітання площини.
Підхід «замітання» можна узагальнити для більших розмірностей.
Примітки
- Shamos, Hoey, 1976, с. 208–215.
- Souvaine, 2008.
Література
- Michael I. Shamos, Dan Hoey. Geometric intersection problems // Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76). — 1976. — С. 208–215. — DOI:
- Diane Souvaine. Line Segment Intersection Using a Sweep Line Algorithm. — 2008.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm zamitannya pryamoyu abo algoritm zamitannya ploshini ce algoritmichna paradigma yaka vikoristovuye uyavnu zamitalnu pryamu abo zamitalnu poverhnyu dlya rozv yazuvannya riznih zadach u evklidovomu prostori Ce odna z klyuchovih tehnik obchislyuvalnoyi geometriyi Animaciya algoritmu Forchuna metodu zamitannya pryamoyu dlya pobudovi diagram Voronogo Ideya algoritmiv cogo tipu polyagaye u vikoristanni uyavnoyi pryamoyi chastishe vertikalnoyi yaka ruhayetsya ploshinoyu i zupinyayetsya u deyakih tochkah de vidbuvayutsya obchislennya Geometrichni operaciyi obmezheni geometrichnimi ob yektami yaki abo peretinayutsya abo prilyagayut do zamitalnoyi pryamoyi a povnij rozv yazok dostupnij koli pryama projde cherez usi ob yekti IstoriyaCej pidhid mozhna prostezhiti vid algoritmiv poryadkovogo skanuvannya v komp yuternij grafici potim jogo vikoristano v rannih algoritmah komponuvannya integralnih shem u yakih geometrichnij opis integralnoyi shemi robivsya u viglyadi paralelnih smuzhok oskilki povnij opis ne pomishavsya v pam yat ZastosuvannyaZastosuvannya cogo pidhodu prizvelo do prorivu v obchislyuvalnij skladnosti geometrichnih algoritmiv koli Shejmos i Gouyi angl Dan Hoey predstavili algoritmi poshuku peretinu vidrizkiv na ploshini i zokrema voni opisali yak kombinaciya pidhodu zamitannya pryamoyu z efektivnimi strukturami danih zbalansovanimi dvijkovimi derevami dozvolyaye viyaviti chi ye peretini N vidrizkiv na ploshini zi skladnistyu O Nlog N displaystyle N log N Tisno pov yazanij algoritm Bentli Ottmanna vikoristovuye tehniku zamitannya pryamoyu shob otrimati vsi K peretiniv sered bud yakih N vidrizkiv na ploshini z chasovoyu skladnistyu O N K log N displaystyle O N K log N ta skladnistyu za pam yattyu O N displaystyle O N Vidtodi cej pidhid vikoristovuvavsya v rozrobci efektivnih algoritmiv dlya nizki zadach takih yak pobudova diagrami Voronogo algoritm Forchuna i triangulyaciyi Delone abo bulevih operacij nad mnogokutnikami Uzagalnennya ta rozshirennyaTopologichne zamitannya ce vid zamitannya ploshini z oslablennyam vimog do poryadku opracyuvannya tochok sho dozvolyaye uniknuti povnogo sortuvannya tochok i dozvolyaye algoritmu zamitannya pryamoyu pracyuvati efektivnishe en dlya pobudovi geometrichnih algoritmiv mozhna vvazhati riznovidom zamitannya v proyektivno dvoyistij ploshini proyektivna dvoyistist peretvoryuye nahil pryamoyi v ploshini v x koordinatu tochki v dvoyistij ploshini tak sho prohodzhennya pryamoyi uporyadkovano za yiyi nahilom Takim chinom algoritm obertovogo kroncirkulya ye dvoyistim dlya procesu prohodzhennya cherez tochki vidsortovani za yih x koordinatami v algoritmi zamitannya ploshini Pidhid zamitannya mozhna uzagalniti dlya bilshih rozmirnostej PrimitkiShamos Hoey 1976 s 208 215 Souvaine 2008 LiteraturaMichael I Shamos Dan Hoey Geometric intersection problems Proc 17th IEEE Symp Foundations of Computer Science FOCS 76 1976 S 208 215 DOI 10 1109 SFCS 1976 16 Diane Souvaine Line Segment Intersection Using a Sweep Line Algorithm 2008