Winged-Edgeデータ構造

ウィキペディア

Winged-Edgeデータ構造

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/12/11 12:50 UTC 版)

Winged-Edgeデータ構造（ウイングド・エッジデータこうぞう）とは計算幾何学において多角形モデルを表現するために使用される境界表現(B-rep)である。3つ以上の面が集まり辺を共有しているときに面、辺、および頂点の形状と位相を明示的に表現する。面は交差している辺の本来の方向に対して反時計回りに順序付けられる。さらにこの表現では下に示されているような数値的に不安定な状態も可能になる。

Winged-Edgeデータ構造ではネットワークが明示的に結び付けられているため、面、辺、頂点間を高速にトラバースすることができる。This rich form of specifying an unstructured grid is in contrast to simpler specifications of polygon meshes such as a node and element list, or the implied connectivity of a regular grid.

擬似コード

ここにWinged-Edgeを表現するのに適したデータ構造を載せる。"WE"という略称は"Winged Edge"を表わす。

class WE_Edge {
  WE_Vertex vert1, vert2;
  WE_Face aFace, bFace;
  WE_Edge aPrev, aNext, bPrev, bNext; // 時計回り
  WE_EdgeDataObject data;
}
class WE_Vertex {
  List<WE_Edge> edges;
  WE_VertexDataObject data;
}
class WE_Face {
  List<WE_Edge> edges;
  WE_FaceDataObject data;
}

関連項目

• en:Quad-edge data structure
• en:Combinatorial maps
• en:Doubly connected edge list
• en:Doubly linked face list

外部リンク

• Bruce G. Baumgart. 1972. Winged Edge Polyhedron Representation.. Technical Report. Stanford University, Stanford, CA, USA.
• Bruce G. Baumgart. 1975. A polyhedron representation for computer vision. In Proceedings of the May 19-22, 1975, national computer conference and exposition (AFIPS '75). ACM, New York, NY, USA, 589-596. DOI=10.1145/1499949.1500071 http://doi.acm.org/10.1145/1499949.1500071 ( Winged Edge Polyhedron Representation for Computer Vision )
• The Winged-Edge Data Structure, on Michigan Technological University
• Winged Edge, on university of Pisa