Okřídlený okraj - Winged edge

Grafické znázornění záznamu hrany. Všimněte si, že odkazy na hraně vypadají jako křídla.

v počítačová grafika, okřídlený okraj datová struktura je způsob, jak reprezentovat mnohoúhelníkové sítě v paměti počítače. Je to typ hraniční reprezentace a popisuje jak geometrii, tak i topologie modelu. Používají se tři typy záznamů: vrcholové záznamy, hranové záznamy a záznamy tváří. Vzhledem k odkazu na záznam hrany lze v konstantním čase odpovědět na několik typů dotazů na sousedství (dotazy na sousední hrany, vrcholy a tváře). Tento druh informací o sousedství je užitečný pro algoritmy jako např Dělicí povrch.

Funkce

The okřídlený okraj datová struktura výslovně popisuje geometrii a topologie ploch, hran a vrcholů, když se tři nebo více povrchů spojí a setkají se na společné hraně. Uspořádání je takové, že povrchy jsou uspořádány proti směru hodinových ručiček vzhledem k vrozené orientaci průsečíku. Reprezentace navíc umožňuje numericky nestabilní situace, jako je situace znázorněná níže.[je zapotřebí objasnění ]

Bod na edge.png

Datová struktura s okřídlenými hranami umožňuje rychlé procházení mezi plochami, hranami a vrcholy díky explicitně propojené struktuře sítě. Poskytuje dotazy na sousedství v konstantním čase s malou režií úložiště. Tato bohatá forma specifikace nestrukturovaná mřížka je na rozdíl od jednodušších specifikací mnohoúhelníkové sítě například seznam uzlů a prvků nebo implikovaná konektivita a pravidelná mřížka. Alternativou k datové struktuře s okřídlenými hranami je Poloviční datová struktura.

Struktura a pseudokód

Záznamy tváře a vrcholu jsou relativně jednoduché, zatímco záznam hrany je složitější. U každého vrcholu se v jeho záznamu ukládá pouze poloha vrcholu (např. Souřadnice) a odkaz na jednu hranu (další hrany lze najít podle dalších odkazů na hraně). Podobně každý záznam obličeje ukládá pouze odkaz na jeden z okrajů obklopujících obličej. Nakonec je struktura záznamu hrany následující. Předpokládá se, že hrana bude směrována. Záznam hrany obsahuje dva odkazy na vrcholy, které tvoří koncové body hrany, dva odkazy na plochy na obou stranách hrany a čtyři odkazy na předchozí a další hrany obklopující levou a pravou plochu. Stručně řečeno, záznam na hraně má odkazy na všechny své sousední záznamy, a to jak při procházení kolem sousedního vrcholu, tak kolem sousední plochy. 

třída Edge {Vertex * vert_origin, * vert_destination; Face * face_left, * face_right; Edge * edge_left_cw, * edge_left_ccw, * edge_right_cw, * edge_right_ccw;} třída Vertex {float x, y, z; Edge * edge;} třída Face {Edge * edge;}

Viz také

externí odkazy