(* Copyright (c) 1992 The Geometry Center; University of Minnesota
1300 South Second Street; Minneapolis, MN 55454, USA;
This file is part of CirclePack. CirclePack is free software; you can
redistribute it and/or modify it only under the terms given in the
file COPYING, which you should have received along with this file.
This and other software may be obtained via anonymous ftp from
geom.umn.edu; email: software@geom.umn.edu. *)
(* Author: Oliver Goodman *)
(* $Id: Triangulation.m,v 1.3 1992/07/17 16:09:52 oag Exp oag $ *)
(* Mathematica package for working with triangulations. Contains a
function for creating triangulation objects and several functions
which return information about a triangulation. For efficiency
reasons the information is computed only once then stored inside
the triangulation object. No checking is done that the triangulation
constructed is legal. (Eg does not have 3 faces bordering a single
edge.)
*)
BeginPackage["Triangulation`"]
Triangulation::usage = "Triangulation[faces, glue] returns a
Triangulation object. Specify faces as a list of triples of integers
and glue as a list of pairs of edges to be identified (where an edge
is a pair of integers). The following functions are defined for a
triangulation object: faces, glue, vertices, edges, corners,
allvertices, alledges, nv, ne, nc, euler, vN, eN."
faces::usage = "faces[triangulation] returns a list containing each
face of the triangulation as a triple of integers."
glue::usage = "glue[triangulation] returns a list of pairs of edges
which are identified in the triangulation."
vertices::usage = "vertices[triangulation] returns a list of integers
representing the vertices of the triangulation. In cases where
several integers represent the same vertex only one representitive
will be returned."
edges::usage = "edges[triangulation] returns a list of pairs of
integers representing the edges of the triangulation. In cases where
several possible pairs of integers represent the same edge only one
pair will be returned."
corners::usage = "corners[triangulation] returns a list of triples
of integers, each of which represents one corner of a face of the
triangulation."
allvertices::usage = "allvertices[triangulation] returns all representitives
of all vertices of the triangulation. See also vertices[]."
alledges::usage = "alledges[triangulation] returns a list of pairs of
integers representing the edges of the triangulation. In cases where
edges have been identified both representitives will be returned. See
also edges[]."
nv::usage = "nv[triangulation] returns the number of vertices in the
triangulation after any identifications have been performed."
ne::usage = "ne[triangulation] returns the number of edges in the
triangulation after any identifications have been performed."
nc::usage = "nc[triangulation] returns the number of corners in the
triangulation (as returned by the corners[] function)."
euler::usage = "euler[triangulation] returns the Euler characteristic
of the triangulation."
vN::usage = "vN[triangulation, v] returns the position of the vertex
represented by v in the list vertices[triangulation]."
eN::usage = "eN[triangulation, e] returns the position of the edge
represented by e in the list edges[triangulation]."
Begin["`Private`"]
faces[t_Triangulation]:= t[[1]]
glue[t_Triangulation]:= t[[2]]
vertices[t_Triangulation]:= t[[3]]
edges[t_Triangulation]:= t[[4]]
corners[t_Triangulation]:= t[[5]]
allvertices[t_Triangulation]:= t[[6]]
alledges[t_Triangulation]:= t[[7]]
nv[t_Triangulation]:= t[[8]]
ne[t_Triangulation]:= t[[9]]
nc[t_Triangulation]:= t[[10]]
euler[t_Triangulation]:= t[[11]]
vN[t_Triangulation, v_]:= Position[vertices[t], t[[12]][v]][[1,1]];
eN[t_Triangulation, e_]:= Position[edges[t], t[[13]][Sort[e]]][[1,1]];
(* unionFind finds a function which maps each vertex of a graph to
a representitive vertex in the same connected component. The graph
is given as a list of edges where each edge is a pair of vertices.
The representitive function r[x] gives the least y (in the canonical
ordering of vertices) in the connected component of x.
*)
unionFind[es_]:=Module[{r,p,x,j},
p[_]=x;
r[v_]:= If[p[v]===x, v, p[v]=r[p[v]]];
j[{a_,b_}]:= Block[{u=r[a],v=r[b]}, If[u=!=v, p[v]=u]];
Scan[j, Sort /@ es];
r[v_]:= r[v] = If[p[v]===x, v, p[v]=r[p[v]]];
r
]
Format[_Triangulation] = "Triangulation"
Triangulation[faces_,glue_]:= Module[{vr, er},
Block[{vertices, edges, corners, allvertices, alledges, nv, ne, nc, euler},
allvertices = Union @@ faces;
alledges = Union @@ ((Sort /@ faces) /.
{a_,b_,c_} :> {{a,b},{b,c},{a,c}});
(* define representitive functions for vertices and edges *)
vr = unionFind[Flatten[Transpose /@ glue,1]];
er = unionFind[Map[Sort,glue,{2}]];
(* list and count up vertices, edges and corners *)
nv = Length[vertices = Union[vr /@ Flatten[faces,1]]];
ne = Length[edges = Union[er /@ alledges]];
nc = Length[corners = Flatten[faces /.
{a_,b_,c_} :> {{a,b,c},{b,c,a},{c,a,b}}, 1]];
euler = Length[faces] - ne + nv;
(* define numbering functions for the vertices and edges *)
Triangulation[faces, glue, vertices, edges, corners, allvertices, alledges,
nv, ne, nc, euler, vr, er]
]]
End[]
EndPackage[]