Dört kenarlı - Quad-edge

Bir dört kenarlı veri yapısı a, bilgisayar temsili topolojisi a iki boyutlu veya üç boyutlu harita , a,, grafik bir (kapalı) ile çekilmiş bir yüzeye . İlk olarak Jorge Stolfi ve Leonidas J. Guibas tarafından tanımlanmıştır . Daha önceki kanatlı kenar veri yapısının bir çeşididir .

Genel Bakış

Dört kenarlı yapının arkasındaki temel fikir, kapalı bir poligonal ağ topolojisindeki tek bir kenarın tam olarak iki yüz ve tam olarak iki köşe arasında oturduğunun tanınmasıdır.

Quad-Edge Veri Yapısı
Quad-Edge Veri Yapısı

Dört kenarlı veri yapısı, grafiğin topolojisini kodlamak için bitişik köşeler ve yüzler etrafında bağlı olduğu kenarlarla birlikte bir kenarı temsil eder. Dört kenarlı veri türünün örnek bir uygulaması aşağıdaki gibidir 

typedef struct {
  quadedge_ref e[4];
} quadedge;

typedef struct {
  quadedge *next;
  unsigned int rot;
} quadedge_ref;

Her dört kenar, bitişik dört kenara dört referans içerir. Dört referansın her biri, bir tepe veya yüz etrafında saat yönünün tersine bir sonraki kenarı işaret eder. Bu referansların her biri, kenarın başlangıç ​​noktasını, sağ yüzü, hedef köşeyi veya sol yüzü temsil eder. Her dört kenarlı referans bir dört kenarı işaret eder ve işaret ettiği 'kolun' dönüşünü (0'dan 3'e).

Bu gösterimden dolayı, dört kenar:

  • bir grafiği, ikilisini ve ayna görüntüsünü temsil eder .
  • grafiğin ikilisi, basitçe tepe noktasının ve yüzün ne olduğu konusundaki konvansiyonu tersine çevirerek elde edilebilir; ve
  • 1. ve 2. derece köşeleri ve yüzleri kabul eden bir haritanın en genel biçimini temsil edebilir.

Detaylar

Dört kenarlı yapı, adını depolandıkları genel mekanizmadan alır. Tek bir Kenar yapısı, kavramsal olarak iki yüze, iki köşeye ve 4 kenara kadar referansları depolar. Saklanan dört kenar, depolanan iki yüze eklenen iki köşeden başlayan kenarlardır.

Kullanımlar

Winged Edge'e çok benzer şekilde , dört kenarlı yapılar, bir 2D veya 3D poligonal ağın topolojisini depolamak için programlarda kullanılır . Geçerli bir dört kenarlı yapı oluşturmak için ağın kendisinin kapatılmasına gerek yoktur.

Dört kenarlı bir yapı kullanarak, topolojide yineleme yapmak oldukça kolaydır. Çoğunlukla, dört kenarlı topolojilere arayüz, yönlendirilmiş kenarlardan geçer. Bu, iki köşenin açık adlara (başlangıç ​​ve bitiş) sahip olmasına izin verir ve bu, yüzlere de açık adlar verir (sol ve sağ, başlangıçta duran ve son yöne bakan bir kişiye göre). Dört kenara da köşelere ve yüzlere bağlı olarak adlar verilir: başlangıç-sol, başlangıç-sağ, sol-son ve sağ-son. Yönlendirilmiş bir kenar, ters yönde kenar oluşturmak için ters çevrilebilir.

Belirli bir yüzün etrafında yineleme yapmak, yalnızca o yüzün solda olduğu tek bir yönlendirilmiş kenara sahip olmayı (geleneksel olarak) ve ardından orijinal kenara ulaşılana kadar tüm başlangıç-sol kenarları boyunca yürümeyi gerektirir.

Ayrıca bakınız

Referanslar

Dış bağlantılar