Poligonlarda Boole işlemleri - Boolean operations on polygons
Poligonlarda Boole işlemleri bir dizi Boole işlemleri (VE, VEYA, DEĞİL, XOR, ...) bir veya daha fazla grupta çalışan çokgenler bilgisayar grafiklerinde. Bu işlem setleri yaygın olarak kullanılmaktadır. bilgisayar grafikleri, CAD, ve EDA (içinde entegre devre fiziksel tasarım ve doğrulama yazılımı).
Algoritmalar
- Greiner-Hormann kırpma algoritması
- Vatti kırpma algoritması
- Sutherland-Hodgman algoritması (özel durum algoritması)
- Weiler – Atherton kırpma algoritması (özel durum algoritması)
Yazılımda kullanır
Çokgenler üzerindeki Boole işlemleri için ilk algoritmalar, aşağıdakilerin kullanımına dayanıyordu: bit eşlemler. Çokgen şekillerini modellemede bitmap'lerin kullanılmasının birçok dezavantajı vardır. Dezavantajlardan biri, çokgenlerin çözünürlüğü çokgenleri temsil etmek için kullanılan bit sayısıyla orantılı olduğundan bellek kullanımının çok büyük olabilmesidir. Çözünürlük ne kadar yüksek istenirse, o kadar fazla bit gerekir.
Çokgenlerde Boolean işlemleri için modern uygulamalar, düzlem süpürme algoritmalarını (veya Süpürme hattı algoritmaları ). Poligonlarda Boolean işlemleri için düzlem süpürme algoritmalarını kullanan kağıtların bir listesi aşağıdaki Referanslar bölümünde bulunabilir.
Boole işlemleri dışbükey çokgenler ve tek renkli çokgenler aynı yönde gerçekleştirilebilir doğrusal zaman.[1]
Ayrıca bakınız
- Yapıcı katı geometri, benzer bir dizi işlem kullanarak üç boyutlu şekilleri tanımlama yöntemi
Notlar
- ^ Katz, Matthew J .; Overmars, Mark H .; Sharir, Micha (1992), "Küçük birleşim boyutuna sahip nesneler için etkili gizli yüzey çıkarma", Hesaplamalı Geometri: Teori ve Uygulamalar, 2 (4): 223–234, doi:10.1016 / 0925-7721 (92) 90024-M.
Kaynakça
- Mark de Berg, Marc van Kreveld, Overmars'ı İşaretle ve Otfried Schwarzkopf, Computational Geometry - Algorithms and Applications, Second Edition, 2000
- Jon Louis Bentley ve Thomas A. Ottmann, Geometrik Kesişimleri Raporlamak ve Saymak İçin Algoritmalar, Bilgisayarlarda IEEE İşlemleri, Cilt. C-28, No. 9, Eylül 1979, s. 643–647
- Jon Louis Bentley ve Derick Wood, Dikdörtgen Kesişimlerini Raporlamak İçin En Kötü Durum Algoritması, Bilgisayarlarda IEEE İşlemleri, Cilt. C-29. 7, Temmuz 1980, s. 571–577
- Ulrich Lauther, Boolean Maske İşlemleri için O (N log N) Algoritması, 18. Tasarım Otomasyon Konferansı, 1981, s. 555–562
- James A. Wilmore, IC Maskelerinde Verimli Boole İşlemleri, 18. Tasarım Otomasyon Konferansı, 1981, s. 571–579
- Nievergelt, J .; Preparata, F. P. (Ekim 1982). "Kesişen Geometrik Figürler için Düzlem Süpürme Algoritmaları". ACM'nin iletişimi. 25 (10): 739–747. CiteSeerX 10.1.1.83.3275. doi:10.1145/358656.358681.
- Thomas Ottmann, Peter Widmayer ve Derick Wood "Boole Maskeleme Problemi için Hızlı Bir Algoritma, "Bilgisayarla Görme, Grafik ve Görüntü İşleme, 30, 1985, s. 249–268
Ayrıca bakınız
- Boole cebri
- Hesaplamalı geometri
- Yapıcı katı geometri
- Geometri işleme
- Genel Çokgen Kesme Makinesi, kırpma işlemlerinin sonuçlarını hesaplayan bir C kütüphanesi
Dış bağlantılar
- UIUC Hesaplamalı Geometri Sayfaları
- Yapıcı düzlemsel geometri, yazan Dave Eberly.
- Yazılım
- Michael Leonov bir derlemiş poligon makaslarının karşılaştırılması.
- Angus Johnson ayrıca üç kırpma kitaplığını karşılaştırdı.
- SINED GmbH, üç çokgen kesme makinesinin performans ve bellek kullanımını karşılaştırdı.
- 5 kırpma kitaplığının karşılaştırması rogue-modron.blogspot.com
- 3B Boole işlemleri için ticari bir kitaplık: sgCore C ++ / C # kitaplığı.
- comp.graphics.algorithms SSS, 2B ve 3B Çokgenlerle matematik problemlerine çözümler.
- Matthias Kramm's gfxpoly, 2D çokgenler için ücretsiz bir C kitaplığı (BSD lisansı).
- Klaas Holwerda'nın Boole, 2B çokgenler için bir C ++ kitaplığı.
- David Kennison's Polip paketi Vatti algoritmasına dayalı bir FORTRAN kitaplığı.
- Klamer Schutte's Clippoly, C ++ ile yazılmış bir çokgen kesme aracı.
- Michael Leonov'un poly_Boolean Schutte algoritmasını genişleten bir C ++ kitaplığı.
- Angus Johnson's Clipper, açık kaynak kodlu ücretsiz bir kitaplık (Delphi, C ++ ve C # ile yazılmış) Vatti algoritması.
- GeoLib, C ++ ve C # ile kullanılabilen ticari bir kitaplık.
- Alan Murta's GPC, General Polygon Clipper kütüphanesi.
- PolygonLib 2D çokgenler için C ++ ve COM kitaplıkları (büyük çokgen kümeleri için optimize edilmiş, yerleşik uzamsal endeksler).