Bentley-Ottmann algoritması - Bentley–Ottmann algorithm

İçinde hesaplamalı geometri, Bentley-Ottmann algoritması bir tarama çizgisi algoritması hepsini listelemek için geçişler bir dizi çizgi segmentinde, yani bulur kesişme noktaları (ya da sadece, kavşaklar) çizgi parçalarının. Genişler Shamos-Hoey algoritması,^[1] bir dizi çizgi parçasının herhangi bir kesişme olup olmadığını test etmek için benzer bir önceki algoritma. Aşağıdakilerden oluşan bir girdi için ${displaystyle n}$ çizgi parçaları ${displaystyle k}$ geçişlerde (veya kesişmelerde), Bentley-Ottmann algoritması zaman alır ${displaystyle {mathcal {O}} ((n + k) log n)}$. Olduğu durumlarda ${displaystyle k = {mathcal {o}} sol ({frac {n ^ {2}} {log n}} ight)}$, bu, her segment çiftini test eden saf bir algoritmada yapılan iyileştirmedir. ${displaystyle Theta (n ^ {2})}$.

Algoritma başlangıçta tarafından geliştirilmiştir Jon Bentley ve Thomas Ottmann (1979 ); ders kitaplarında daha ayrıntılı olarak anlatılmıştır Preparata ve Shamos (1985), O'Rourke (1998), ve de Berg vd. (2000). olmasına rağmen asimptotik olarak daha hızlı algoritmalar artık Chazelle ve Edelsbrunner (1992) ve Balaban (1995) Bentley-Ottmann algoritması, basitliği ve düşük bellek gereksinimleri nedeniyle pratik bir seçim olmaya devam ediyor^{[kaynak belirtilmeli ]}.

Genel strateji

Bentley-Ottmann algoritmasının ana fikri, bir süpürme çizgisi dikey bir çizginin olduğu yaklaşma L düzlem boyunca soldan sağa (veya örneğin yukarıdan aşağıya) hareket ederek giriş satırı segmentlerini sırayla keser.^[2] Algoritma, en kolay şekilde genel pozisyon, anlamı:

1. Hiçbir iki çizgi parçası uç noktası veya kesişme noktası aynı x-koordinat
2. Hiçbir çizgi parçası uç noktası başka bir çizgi parçası üzerinde yer almaz
3. Tek bir noktada üç çizgi parçası kesişmez.

Böyle bir durumda, L dikey sıralaması yalnızca sonlu bir kesikli kümede değişen bir nokta kümesinde her zaman girdi çizgi bölümlerini kesişir. Etkinlikler. Spesifik olarak, ayrı bir olay, bir çizgi parçasının bir uç noktası (sol veya sağ) veya iki çizgi parçasının kesişme noktası ile ilişkilendirilebilir. Böylece, sürekli hareket L sonlu bir adım dizisine bölünebilir ve sınırlı bir süre içinde çalışan bir algoritma tarafından simüle edilebilir.

Bu simülasyon sırasında meydana gelebilecek iki tür olay vardır. Ne zaman L bir çizgi parçasının uç noktasını süpürür s, kesişme noktası L ile s dikey sıralı kesişim noktaları kümesine eklenir veya buradan çıkarılır. Uç noktalar, girdiden algoritmaya kadar zaten bilindiği için, bu olayların tahmin edilmesi kolaydır. Kalan olaylar ne zaman meydana gelir? L iki çizgi parçası arasındaki (veya kesişen) bir kesişme boyunca süpürür s ve t. Bu olaylar aynı zamanda olaydan hemen önce şunların kesişme noktalarının olmasından da tahmin edilebilir. L ile s ve t kesişme noktalarının dikey sıralamasında bitişiktir^{[açıklama gerekli ]}.

Bentley-Ottmann algoritmasının kendisi, tarama çizgisinin giriş çizgisi segmentleri ile kesişme noktalarının mevcut dikey sırasını ve bitişik kesişim noktası çiftleri tarafından oluşturulan potansiyel gelecek olayların bir koleksiyonunu temsil eden veri yapılarını korur. Sırasıyla her olayı işler, veri yapılarını yeni kesişme noktaları kümesini temsil edecek şekilde günceller.

Veri yapıları

Bu bölüm olabilir kafa karıştırıcı veya belirsiz okuyuculara. Özellikle, ikili arama ağacının iç ve yaprak düğümlerinin neyi temsil ettiği açıklanmamıştır. Bir çizgi parçasının öncülünü veya halefini eklerken, silerken veya bulurken çizgi parçaları birbirleriyle nasıl karşılaştırılır? Bir çizgi parçasını başka bir doğru parçasının selefi ve halefi yapan nedir? Lütfen bize yardım et bölümü netleştir. Bununla ilgili bir tartışma olabilir konuşma sayfası. (Mart 2018) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Süpürme hattının kesişme noktalarını verimli bir şekilde korumak için L girdi çizgi segmentleri ve gelecekteki olayların sırası ile Bentley – Ottmann algoritması iki veri yapıları:

• Bir ikili arama ağacı ("süpürme çizgisi durum ağacı"), kesişen giriş satırı segmentleri kümesini içerir Ltarafından sipariş edildi y-bu segmentlerin kesiştiği noktaların koordinatları L. Geçiş noktalarının kendileri değil ikili arama ağacında açıkça gösterilir. Bentley – Ottmann algoritması yeni bir segment ekleyecek s süpürme çizgisi L sol uç noktayı geçiyor p bu segmentin (yani, en küçük segmentin son noktası) x-Süpürme çizgisi sağlandığında koordinat L yukarıda bu makalede açıklandığı gibi soldan başlar). Doğru segment konumu s ikili arama ağacında, her bir adımın p ile kesişen başka bir segmentin üstünde veya altında L. Bu nedenle, logaritmik zamanda bir ekleme gerçekleştirilebilir. Bentley-Ottmann algoritması aynı zamanda bölümleri ikili arama ağacından silecek ve diğer bölümlerin hemen üstünde ya da altında olan bölümleri belirlemek için ikili arama ağacını kullanacaktır; bu işlemler, segmentlerin temel geometrisine referans olmaksızın sadece ağaç yapısının kendisi kullanılarak gerçekleştirilebilir.

• Bir öncelik sırası ("olay kuyruğu"), Bentley – Ottmann algoritmasında gelecekteki olası olayların bir sırasını korumak için kullanılır. Her olay bir noktayla ilişkilendirilir p düzlemde, bir segment uç noktası veya bir kesişme noktası ve olay, çizgi L süpürür p. Böylelikle olaylara öncelik verilebilir. x-Her olayla ilişkili noktaların koordinatları. Bentley-Ottmann algoritmasında, gelecekteki potansiyel olaylar, henüz üzerinden geçmemiş çizgi parçası uç noktalarından ve birbirinin hemen üstünde veya altında bulunan parça çiftlerini içeren çizgi çiftlerinin kesişme noktalarından oluşur.

Algoritmanın, tarama çizgisinin açıkça bir temsilini korumasına gerek yoktur. L veya düzlemdeki konumu. Aksine, konumu L dolaylı olarak temsil edilir: en son işlenen olayla ilişkili noktadan geçen dikey çizgidir.

İkili arama ağacı herhangi bir dengeli ikili arama ağacı veri yapısı, örneğin kırmızı-siyah ağaç; tek gereken, ekleme, silme ve aramaların logaritmik süre almasıdır. Benzer şekilde, öncelik sırası bir ikili yığın veya herhangi bir diğer logaritmik zaman öncelikli kuyruk; gibi daha karmaşık öncelik kuyrukları Fibonacci yığını gerekli değildir. Öncelik kuyruğunun alan karmaşıklığının, onu uygulamak için kullanılan veri yapısına bağlı olduğuna dikkat edin.

Ayrıntılı algoritma

Bentley – Ottmann algoritması aşağıdaki adımları gerçekleştirir.

1. Öncelik kuyruğunu başlatın Q her biri düzlemdeki bir noktayla ilişkilendirilen ve x- noktanın koordinatı. Yani, başlangıçta, Q giriş segmentlerinin her bir uç noktası için bir olay içerir.
2. Bir kendini dengeleyen ikili arama ağacı T süpürme çizgisini geçen çizgi parçalarının Ltarafından sipariş edildi y- geçiş noktalarının koordinatları. Başlangıçta, T boş. (Çizgi süpürse bile L açıkça temsil edilmediğinden, başlangıçta tüm girdi segmentlerinin solunda olan dikey bir çizgi olarak hayal etmek faydalı olabilir.)
3. Süre Q boş değil, olayı bulun ve buradan kaldırın Q bir noktayla ilişkili p minimum ile x-koordinat. Bunun ne tür bir olay olduğunu belirleyin ve aşağıdaki vaka analizine göre işleyin:
   • Eğer p bir çizgi parçasının sol uç noktasıdır s, ekle s içine T. Çizgi parçalarını bulun r ve t sırasıyla hemen üstte ve altındadır s içinde T (eğer varsa); eğer geçiş r ve t (komşuları s Durum veri yapısında) olay kuyruğunda gelecekteki olası bir olayı oluşturur, bu olası gelecekteki olayı olay kuyruğundan kaldırın. Eğer s haçlar r veya t, bu kesişme noktalarını olay kuyruğuna gelecekteki olası olaylar olarak ekleyin.
   • Eğer p bir çizgi parçasının sağ uç noktasıdır s, Kaldır s itibaren T. Segmentleri bulun r ve t bu (kaldırılmadan önce s) sırasıyla hemen üstünde ve altında idi T (eğer varsa). Eğer r ve t çapraz, bu geçiş noktasını olay kuyruğuna gelecekteki olası bir olay olarak ekleyin.
   • Eğer p iki parçanın kesişme noktasıdır s ve t (ile s altında t geçişin solunda), pozisyonlarını değiştirin s ve t içinde T. Değişimden sonra segmentleri bulun r ve sen (eğer varsa) hemen altında ve üstünde olanlar t ve s, sırasıyla. Kesişen noktaları kaldırın rs (ör. arasında bir geçiş noktası r ve s) ve tu (ör. arasında bir geçiş noktası t ve sen) olay kuyruğundan ve eğer r ve t çapraz veya s ve sen çapraz, bu kesişme noktalarını olay kuyruğuna ekleyin.

Analiz

Algoritma, her segment uç noktası veya geçiş noktası için sıralı sırayla bir olay işler. ${displaystyle x}$- tümevarımla kanıtlanabileceği gibi bu noktaların koordinatları. Bunun nedeni, ${displaystyle i}$Olay işlendiyse, sonraki olay (bu bir kesişme noktasıysa) ile temsil edilen segmentlerin sıralamasında bitişik olan iki segmentin kesişmesi olmalıdır. ${displaystyle T}$ve algoritma, olay kuyruğundaki potansiyel gelecek olaylar olarak komşu segmentler arasındaki tüm geçişleri koruduğu için; bu nedenle, sonraki doğru olay her zaman olay kuyruğunda mevcut olacaktır. Sonuç olarak, çözmek için tasarlandığı problem olan giriş hattı segmentlerinin tüm kesişmelerini doğru bir şekilde bulur.

Bentley – Ottmann algoritması bir dizi işliyor ${displaystyle 2n + k}$ olaylar, nerede ${displaystyle n}$ giriş satırı segmentlerinin sayısını gösterir ve ${displaystyle k}$ kesişme sayısını gösterir. Her olay, ikili arama ağacında ve olay kuyruğunda sabit sayıda işlem tarafından işlenir ve (çünkü yalnızca segment uç noktaları ve bitişik segmentler arasında geçişler içerdiğinden) olay kuyruğu hiçbir zaman şunlardan fazlasını içermez: ${displaystyle 3n}$ Etkinlikler. Tüm işlemler zaman alır ${displaystyle {mathcal {O}} (log n)}$. Dolayısıyla, algoritmanın toplam süresi ${displaystyle {mathcal {O}} ((n + k) log n)}$.

Algoritma tarafından bulunan geçişlerin bulunduktan sonra depolanması gerekmiyorsa, algoritma tarafından herhangi bir zamanda kullanılan alan ${displaystyle {mathcal {O}} (n)}$: Her biri ${displaystyle n}$ giriş çizgisi segmentleri, ikili arama ağacının en fazla bir düğümüne karşılık gelir Tve yukarıda belirtildiği gibi olay kuyruğu en fazla ${displaystyle 3n}$ elementler. Bu boşluk sınırının nedeni Kahverengi (1981); algoritmanın orijinal versiyonu biraz farklıydı (geçiş olaylarını ${displaystyle Q}$ başka bir olay iki kesişen segmentin bitişik olmamasına neden olduğunda) daha fazla alan kullanmasına neden olur.^[3]

Chen ve Chan (2003) Bentley-Ottmann algoritmasının, bilgilerinin çoğunu girdiyi temsil eden bir dizideki segmentlerin sırasına göre kodlayan ve yalnızca ${displaystyle {mathcal {O}} (log ^ {2} n)}$ ek hafıza hücreleri. Bununla birlikte, kodlanmış bilgilere erişmek için algoritma, logaritmik bir faktörle yavaşlatılır.

Özel pozisyon

Yukarıdaki algoritma açıklaması, çizgi parçalarının dikey olmadığını, çizgi parçası uç noktalarının diğer çizgi parçalarının üzerinde olmadığını, kesişmelerin yalnızca iki çizgi parçası tarafından oluşturulduğunu ve iki olay noktasının aynı değere sahip olmadığını varsayar. x-koordinat. Başka bir deyişle, köşe durumlarını hesaba katmaz, yani genel pozisyon giriş segmentlerinin uç noktalarının. Ancak, bu genel konum varsayımları çoğu çizgi parçası kesişimi uygulaması için makul değildir. Bentley ve Ottmann (1979) bu tür sayısal çakışmalardan kaçınmak için girdiyi biraz karıştırmayı önerdi, ancak bu karışıklıkların nasıl gerçekleştirileceğini ayrıntılı olarak açıklamadı. de Berg vd. (2000) Özel konum girdilerinin işlenmesine yönelik aşağıdaki önlemleri daha ayrıntılı olarak açıklayın:

• Olay noktaları arasındaki bağları aynı şekilde kırın x-kullanarak koordine edin y-koordinat. Farklı etkinlikler y-Kordinatlar eskisi gibi işlenir. Bu değişiklik, hem birden çok olay noktası sorununu hem de aynı x- koordinat ve dikey çizgi segmentleri sorunu: Dikey bir segmentin sol uç noktası, daha düşük olanı olarak tanımlanır. y- koordinat ve böyle bir segmenti işlemek için gereken adımlar, çok yüksek bir eğime sahip dikey olmayan bir segmenti işlemek için gerekenlerle temelde aynıdır.
• Bir çizgi parçasını bir kapalı küme, uç noktalarını içeren. Bu nedenle, bir uç noktayı paylaşan iki çizgi parçası veya başka bir parçanın uç noktasını içeren bir çizgi parçası, iki çizgi parçasının kesişimi olarak kabul edilir.
• Birden çok çizgi parçası aynı noktada kesiştiğinde, bu kesişim için tek bir olay noktası oluşturun ve işleyin. Bu olayın neden olduğu ikili arama ağacında yapılan güncellemeler, bunun sağ son nokta olduğu herhangi bir çizgi parçasının kaldırılmasını, bunun sol uç nokta olduğu yeni çizgi bölümlerinin eklenmesini ve bu olay noktasını içeren kalan çizgi bölümlerinin sırasının tersine çevrilmesini içerebilir. . Tarafından açıklanan algoritma sürümünün çıktısı de Berg vd. (2000) kesişen çizgi parçası çiftleri kümesinden ziyade, ait oldukları parçalarla etiketlenen çizgi parçalarının kesişme noktaları kümesinden oluşur.

Dejenereliklere benzer bir yaklaşım, LEDA Bentley – Ottmann algoritmasının uygulanması.^[4]

Sayısal hassasiyet sorunları

Algoritmanın doğruluğu için, bir çizgi parçası uç noktası ile diğer çizgi bölümleri arasındaki yukarıdaki-aşağıdaki ilişkilerin yaklaşık olarak belirlenmesi ve farklı olay noktalarının doğru bir şekilde önceliklendirilmesi gereklidir. Bu nedenle, giriş çizgisi segmentlerinin uç noktaları için tamsayı koordinatlarının kullanılması ve rasyonel sayı tam olarak iki parçanın kesişme noktalarının koordinatları kullanılarak keyfi kesinlikte aritmetik. Ancak bu koordinatların hesaplamalarını ve karşılaştırmalarını hızlandırmak mümkün olabilir. kayan nokta hesaplamalar ve bu şekilde hesaplanan değerlerin sıfırdan yeterince uzak olup olmadıklarının herhangi bir hata olasılığı olmadan kullanılabilir olup olmadığının test edilmesi.^[4] Bentley-Ottmann algoritmasının saf bir uygulamasının gerektirdiği kesin aritmetik hesaplamalar, giriş koordinatlarından beş kat daha fazla hassasiyet biti gerektirebilir, ancak Boissonat ve Preparata (2000) Algoritmada gerekli kesinlik miktarını girdi koordinatları olarak bit sayısının iki katına düşüren değişiklikleri açıklar.

Daha hızlı algoritmalar

O (n günlük n) Bentley – Ottmann algoritması için zaman sınırının bir kısmı gereklidir, çünkü eşleşen alt sınırlar içinde kesişen çizgi segmentlerini tespit etme sorunu için cebirsel karar ağacı hesaplama modelleri.^[5] Ancak, bağımlılık k, geçiş sayısı iyileştirilebilir. Clarkson (1988) ve Mulmuley (1988) her ikisi de rastgele hale getirilmiş algoritmalar sağladı düzlemsel grafik bunların uç noktaları çizgi parçalarının uç noktaları ve kesişimleri olan ve kenarları bu köşeleri birleştiren bölümlerin bölümleri olan O (n günlük n + k) ve bu problem aranjman inşaat çözüldü belirleyici olarak aynı O (n günlük n + k) zaman sınırı Chazelle ve Edelsbrunner (1992). Bununla birlikte, bu düzenlemeyi bir bütün olarak inşa etmek, O (n + k), O (n) Bentley-Ottmann algoritmasının uzay sınırı; Balaban (1995) O zamanındaki tüm kavşakları listeleyen farklı bir algoritma tanımladı (n günlük n + k) ve boşluk O (n).

Giriş çizgisi segmentleri ve bunların uç noktaları bir satırın kenarlarını ve köşelerini oluşturuyorsa bağlantılı grafik (muhtemelen geçişlerle), O (n günlük n) Bentley – Ottmann algoritması için zaman sınırının bir kısmı da azaltılabilir. Gibi Clarkson, Cole ve Tarjan (1992) göster, bu durumda problemi beklenen O (O) zamanında çözmek için rastgele bir algoritma varn günlük * n + k), nerede günlük* gösterir yinelenen logaritma, logaritmadan çok daha yavaş büyüyen bir fonksiyon. Yakından ilişkili bir rastgele algoritma Eppstein, Goodrich ve Strash (2009) aynı problemi O zamanında çözer (n + k günlük^(ben)n) herhangi bir sabit için ben, nerede günlük^(ben) logaritma işlevini yineleyerek elde edilen işlevi gösterir ben zamanlar. Bu algoritmalardan ilki, her zaman doğrusal zaman alır. k daha büyük n bir günlük tarafından^(ben)n faktör, herhangi bir sabit için benikinci algoritma doğrusal zaman alırken k den daha küçük n bir günlük tarafından^(ben)n faktör. Bu algoritmaların her ikisi de Bentley-Ottmann algoritmasının girdinin küçük rastgele örneklerine uygulanmasını içerir.

Notlar

Referanslar

• Balaban, I. J. (1995), "Segment kesişimlerini bulmak için optimal bir algoritma", Proc. 11. ACM Symp. Hesaplamalı Geometri, s. 211–219, doi:10.1145/220279.220302, S2CID  6342118.
• Bartuschka, U .; Mehlhorn, K.; Näher, S. (1997), "Düz çizgi parçası kesişim problemi için bir tarama çizgisi algoritmasının sağlam ve verimli bir uygulaması", içinde Italiano, G.F.; Orlando, S. (editörler), Proc. Worksh. Algoritma Mühendisliği.
• Bentley, J. L.; Ottmann, T. A. (1979), "Geometrik kesişimleri bildirmek ve saymak için algoritmalar", Bilgisayarlarda IEEE İşlemleri, C-28 (9): 643–647, doi:10.1109 / TC.1979.1675432, S2CID  1618521.
• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), "Bölüm 2: Çizgi parçası kesişimi", Hesaplamalı Geometri (2. baskı), Springer-Verlag, s.19–44, ISBN  978-3-540-65620-3.
• Boissonat, J.-D .; Preparata, F.P. (2000), "Kesişen segmentler için sağlam düzlem süpürme" (PDF), Bilgi İşlem Üzerine SIAM Dergisi, 29 (5): 1401–1421, doi:10.1137 / S0097539797329373.
• Brown, K. Q. (1981), Geometrik Kesişimleri Raporlama ve Sayma Algoritmaları "Hakkında Yorumlar""", Bilgisayarlarda IEEE İşlemleri, C-30 (2): 147, doi:10.1109 / tc.1981.6312179, S2CID  206622367.
• Chazelle, Bernard; Edelsbrunner, Herbert (1992), "Düzlemde çizgi parçalarını kesişen optimal bir algoritma", ACM Dergisi, 39 (1): 1–54, doi:10.1145/147508.147511, S2CID  785741.
• Chen, E. Y .; Chan, T. M. (2003), "Segment kesişimi için alanı verimli kullanan bir algoritma", Proc. 15. Kanada Hesaplamalı Geometri Konferansı (PDF).
• Clarkson, K. L. (1988), "Hesaplamalı geometride rasgele örnekleme uygulamaları, II", Proc. 4. ACM Symp. Hesaplamalı Geometri, s. 1–11, doi:10.1145/73393.73394, S2CID  15134654.
• Clarkson, K. L.; Cole, R .; Tarjan, R. E. (1992), "Trapez diyagramlar için rastgele paralel algoritmalar", International Journal of Computational Geometry and Applications, 2 (2): 117–133, doi:10.1142 / S0218195992000081. Corrigendum, 2 (3): 341–343.
• Eppstein, D.; Goodrich, M.; Strash, D. (2009), "Doğrusal olmayan çok sayıda geçişe sahip geometrik grafikler için doğrusal zaman algoritmaları", Proc. 20. ACM-SIAM Symp. Ayrık Algoritmalar (SODA 2009), s. 150–159, arXiv:0812.0893, Bibcode:2008arXiv0812.0893E, doi:10.1137/090759112, S2CID  13044724.
• Mulmuley, K. (1988), "Hızlı düzlemsel bölümleme algoritması, I", Proc. 29. IEEE Symp. Bilgisayar Biliminin Temelleri (FOCS 1988), s. 580–589, doi:10.1109 / SFCS.1988.21974, S2CID  34582594.
• O'Rourke, J. (1998), "Bölüm 7.7: Segmentlerin Kesişimi", C'de Hesaplamalı Geometri (2. baskı), Cambridge University Press, s. 263–265, ISBN  978-0-521-64976-6.
• Preparata, F.P.; Shamos, M.I. (1985), "Bölüm 7.2.3: Çizgi segmentlerinin kesişimi", Hesaplamalı Geometri: Giriş, Springer-Verlag, s. 278–287.
• Pach, J.; Sharir, M. (1991), "Segment düzenlemelerinde dikey görünürlük ve Bentley – Ottmann çizgi süpürme algoritmasındaki kuyruk boyutu hakkında", Bilgi İşlem Üzerine SIAM Dergisi, 20 (3): 460–470, doi:10.1137/0220029, BAY  1094525.
• Shamos, M.I.; Hoey, Dan (1976), "Geometrik kesişim sorunları", 17. IEEE Konf. Bilgisayar Biliminin Temelleri (FOCS 1976), s. 208–215, doi:10.1109 / SFCS.1976.16, S2CID  124804.

Dış bağlantılar

• Smid, Michiel (2003), Bir dizi çizgi segmentinde kesişimlerin hesaplanması: Bentley-Ottmann algoritması (PDF).