ddg.halfedge package

Module contents

class ddg.halfedge.Surface[source]

Bases: object

Finite cell decomposition of a 2-dimensional manifold, possibly with boundary, represented by a half edge data structure.

add_vertex()[source]

Add an isolated vertex.

Returns:

vertex

add_edge(v1, v2, epre=None, enex=None)[source]

Insert an edge between two boundary vertices.

Parameters:

v1, v2vertex: Boundary vertices that the edge should connect.
epreedge or None (default=None): Defines the edge such that epre.nex is the first new edge. If this is None, a boundary edge pointing to v will be looked up.

Returns:

edge: The halfedge from v1 to v2.

add_face(n, v=[])[source]

Adds an n-gon to the surface. The polygon is not connected to any other polygons after addition.

Parameters:

nint: number of vertices of the polygon to be added
vlist: vertices that become vertices of the polygon new vertices are generated if there are non given

Returns:

face: the face that has been added

glue(e1, e2)[source]

Glues edges of the same surface such that the given halfedges form the new shared edge.

The given halfedges e1 and e2 will be preserved and become opposites of each other while their former opposites are eliminated. The vertices of the new halfedge pair will be the original head and tail of the first edge e1, except in the following special case: If the second edge e2 is a loop and the first edge e1 is not a loop, then the gluing operation identifies the original tail of e1 with the head of e1 and the original tail of e1 is removed.

Parameters:

e1edge: interior edge of a face with its opposite being a boundary edge, e1.opp will become e2
e2edge: interior edge of a face with its opposite being a boundary edge, e2.opp will become e1

Returns:

None

Raises:

ValueError: If the arguments e1 and e2 are not different boundary edges of the surface on which the method is called.

validate()[source]

Validate a halfedge object.

The following checks are run (in order). By “all attributes” we mean nex, pre, opp, head for edges; edge for faces; edge for vertices. By “nodes” we mean vertices, edges and faces, with a generic one denoted by v, e or f.

Checks that all attributes point to instances of the correct node class belonging to this surface or None, if allowed (e.face == None indicates a boundary edge, v.edge == None indicates an isolated vertex).
Checks that no attributes point to removed nodes, meaning nodes with surf == None.
Checks consistency of attributes of all nodes, namely:
- e.nex.pre is e
- e.face is e.nex.face
- e.head is e.nex.opp.head
- f.edge.face is f
- v.edge.head is v
Checks that all face boundaries are simple loops.
Checks that all vertex coboundaries are simple loops. A vertex coboundary is the “asterisk” shape of incoming and outgoing edges of a vertex.

Raises:

SurfaceError: If object is invalid.

validate_surface()[source]

Validate a 2D manifold.

Runs validate plus these additional checks:

Checks that object is not the empty set by checking if there are vertices.
Checks that for each edge, e.face and e.opp.face are not both None.
Checks that no two boundary edges have the same head.
Checks that there are no vertices with v.edge == None, i.e. isolated vertices.

Raises:

SurfaceError: If object is invalid or is not a 2D manifold.

validate_curve()[source]

Validate a 1D manifold.

Runs validate_graph plus these additional checks:

Checks that object is not the empty set by checking if there are vertices.
Checks that all vertices have valency 2, by checking e.nex.opp is e.opp.pre for every edge.
Checks that there are no vertices with v.edge == None, i.e. isolated vertices.

Raises:

SurfaceError: If object is invalid or is not a 1D manifold.

validate_graph()[source]

Validate a graph.

Runs validate and checks that there are no faces.

Raises:

SurfaceError: If object is invalid or has faces.

exception ddg.halfedge.SurfaceError[source]

Bases: Exception

args

with_traceback(): Exception.with_traceback(tb) – set self.__traceback__ to tb and return self.

ddg.halfedge.combinatorial_copy(surf)[source]

Returns a combinatorial copy of a halfedge datastructure object. The halfedge object is copied, the combinatorics of the copy are the same as of the original halfedge object. No (manually generated) cell attributes are copied or set.

Parameters:

surfddg.halfedge.Surface: The halfedge data that shall be copied.

Returns:

surfddg.halfedge.Surface: A combinatorial copy of the given halfedge data.

See also

ddg.halfedge.copy

ddg.halfedge.copy(surf, verts_attr_list=None, edges_attr_list=None, faces_attr_list=None, original_vertex_attr=None, original_edge_attr=None, original_face_attr=None)[source]

Returns a copy of a halfedge datastructure object, including the attributes on vertices, edges and faces that are stated to be copied.

The attributes that shall be copied are handed over in lists for vertices, edges and faces, containing their string names.

Parameters:

surfddg.halfedge.Surface: The half-edge data that shall be copied.
verts_attr_listiterable of str (default=None): A list of strings naming the vertex attributes that shall be copied.
edges_attr_listiterable of str (default=None): A list of strings naming the edge attributes that shall be copied.
faces_attr_listiterable of str (default=None): A list of strings naming the face attributes that shall be copied.
original_vertex_attrstr (default=None): Defining whether an attribute that stores the corresponding original vertex shall be added to the vertices of the copy. Default is None, if a string is given this becomes the name of the new attribute.
original_edge_attrstr (default=None): Defining whether an attribute that stores the corresponding original edge shall be added to the edges of the copy. Default is None, if a string is given this becomes the name of the new attribute.
original_face_attrstr (default=None): Defining whether an attribute that stores the corresponding original face shall be added to the faces of the copy. Default is None, if a string is given this becomes the name of the new attribute.

Returns:

surfddg.halfedge.Surface: A copy of the given halfedge data, including the attributes on vertices, edges and faces that were stated.

See also

ddg.halfedge.combinatorial_copy

Notes

The attributes handed over need to be of a type that implements or allows copy.deepcopy().

ddg.halfedge.union(*surfaces, verts_attr_list=None, edges_attr_list=None, faces_attr_list=None)[source]

Disjoint union of surfaces as a single, new surface.

Parameters:

*surfacesobjects of type ddg.halfedge.Surface
verts_attr_list, edges_attr_list, faces_attr_listlist of str (default=None): Attributes to be copied. All input surfaces must have the attribute. Just like in copy(), the attribute values must support deepcopy().

Returns:

surfddg.halfedge.Surface

See also

ddg.halfedge.copy

Notes

The result will most likely be disconnected!

ddg.halfedge.from_json(filename)[source]

Create a surface from a json file. All keys will be mapped to respective attribute of the vertices, edges, and faces.

Parameters:

filename: string: file containing a json representing a halfedge surface

Returns:

surface

Raises:

ValueError: If required attributes are missing in the json string

ddg.halfedge.surface_to_ifs_json(surface, vertex_attrs=['co'])[source]

ddg.halfedge.to_json_string(surface, vertex_attrs=[], edge_attrs=[], face_attrs=[], write_index=False)[source]

Create a json string from a given halfedge surface. Additional attributes to be included in the json string need to be specified explicitly in the respective dictionaries. All the references to vertices, edges, and faces are realized using integer indices. The None face corresponds to -1

Parameters:

surfacehalfedge surface: The surface to be converted to a json string
vertex_attrslist of strings: vertex attributes to be contained in the json string in addition to edge
edge_attrs: edge attributes to be contained in the json string in addition to pre, nex, opp, head, face
face_attrs: face attributes to be contained in the json string in addition to edge

Returns:

string

ddg.halfedge.to_json(surface, filename, vertex_attrs=[], edge_attrs=[], face_attrs=[])[source]

Create a file in json format from a given halfedge surface. Additional attributes to be included in the json string need to be specified explicitly in the respective dictionaries. All the references to vertices, edges, and faces are realized using integer indices. The None face corresponds to -1

Parameters:

surfacehalfedge surface: The surface to be converted to a json string
filenamestring: file to be written
vertex_attrslist of strings: vertex attributes to be contained in the json string in addition to edge
edge_attrs: edge attributes to be contained in the json string in addition to pre, nex, opp, head, face
face_attrs: face attributes to be contained in the json string in addition to edge

ddg.halfedge.dehomogenize(hds, co_attr_homogeneous='co', co_attr_affine='co', in_place=True, atol=None, rtol=None)[source]

Dehomogenize a hds, removing infinity crossings.

Let x_i = 0 be the hyperplane at infinity. The function works by deleting vertices that are in this plane and edges (and therefore faces) that cross this plane. This depends on the representative vectors!

Parameters:

hdsSurface
co_attr_homogeneousstr (default=’co’): Name of attribute that stores homogeneous coordinates.
co_attr_affinestr (default=’co’): Name of attribute to store affine coordinates after dehomogenizing.
in_placebool (default=True): Whether to modify the hds or create a copy. The copy will only have the attributes co_attr_homogeneous and co_attr_affine.

Returns:

hdsSurface: The dehomogenized hds. Either the original, modified object or a copy with vertex attributes with names given in co_attr_homogeneous and co_attr_affine.

ddg.halfedge.laplace_invariant(edge, co_attr='co', line_family_attr=None, atol=0.0001)[source]

Function to compute the Laplace invariant of an interior edge.

Namely the cross ratio q(e.tail, L^{(i)}_{j}, e.head, L^{(i)}_{-j}), where L^{(i)}_{pm j} are the intersection points of the previous and next lines of the same line family with the line given by the given edge. A line family is interpreted as either one of the two directions (e.g. horizontal and vertical) introduced by the preimage lattice of mathbb{Z}^2.

If a boundary edge (or an edge where e.opp is a boundary edge) is given the return value is None.

Parameters:

edge: ddg.halfedge.Surface.edges: Edge to compute the laplace invariant from.
co_attr: str (default=’co’): Coordinate attribute at the vertices used for computation.
line_family_attr: NodeAttribute: Attribute of edges, that distinguishes the horizontal and vertical family of lines. If given, and True on an edge, than the reciprocal of the computed value is set to this edge.
atol: float (default=1e-4): Tolerance to verify computations for coefficients of the planes induces by the quads of either two edges.

Returns:

float, None: float for interior edges and None for boundary edges

ddg.halfedge.laplace_invariant_cross(v, laplace_inv_attr)[source]

Function to compute the product of the laplace invariants of the four edges incident to a single vertex.

Enumerating successive edges in a vertex star (L_0 * L_2) / (L_1 * L_3) is the value that is returned. For discrete Koenigs nets this value is 1.

Parameters:

v: ddg.halfedge.Surface.verts: Vertex to compute the laplace invariant from.
laplace_inv_attr: NodeAttribute of edges: Attribute to read the laplace invariants of the edges from. Can be set e.g. using the laplace_invariant function.

Returns:

float, None: None if the given vertex is a boundary vertex else the computed value

ddg.halfedge.laplace_invariant_quad(face, laplace_inv_attr)[source]

Function to return the product of the laplace invariants of the four edges incident to a face. Enumerating successive edges in a face (L_0 * L_2) / (L_1 * L_3) is the value that is returned. For a Q-net that is build from the intersection points of the diagonals of faces of a discrete Koenigs net (the Doliwa dual) this value is 1.

Parameters:

face: ddg.halfedge.Surface.faces: Face to compute the laplace invariant from.
laplace_inv_attr: NodeAttribute of edges: Attribute to read the laplace invariants of the edges from. Can be set e.g. using the laplace_invariant function.

Returns:

float, None: None if the given face is a boundary face else the computed value

ddg.halfedge.attach_pyramid(e)[source]

Attaches a pyramid to the loop of boundary edges along a given one.

One new triangle each is glued to every edge of the edge loop of consecutive boundary edges along e and as well glued to the previously added triangle, such that they all share the same tip and form a pyramid.

Parameters:

eedge: An edge of the boundary loop along which a pyramid will be attached.

Returns:

vertex: The newly added vertex which is the peak of the attached pyramid.

Raises:

ValueError: If the edge does not lie opposite to a boundary loop.

ddg.halfedge.bridge_loops(e1, e2)[source]

Creates a bridging loop between two not yet connected loops of boundary edges or components of a surface by gluing a circular strip of new edges and quad-faces in.

The loops of edges that shall be bridged should have the same number of edges. The bridging starts with a quad connecting ‘edge1’ and ‘edge2’.

Parameters:

e1edge: An interior halfedge opposite to a boundary loop that shall be bridged.
e2edge: An interior halfedge opposite to the boundary loop that shall be bridged to the first.

Returns:

None

Raises:

ValueError: If the loops don’t count the same number of edges.

ddg.halfedge.contract_edge(e)[source]

Contract an edge and remove the edge and its opposite from the surface.

Note that this can alter the manifold property if an adjacent face is a triangle or e.head and e.tail are boundary vertices:

  *-----*           *
 /|     |          /|
* |e    |  ->  *--* |
 \|     |          \|
  *-----*           *

*-----*-----*      *   *
|     |     |      |\ /|
|     |e    |  ->  | * |
|     |     |      |/ \|
*-----*-----*      *   *

Parameters:

eedge: to be contracted

Returns:

edge, edge: e.pre and e.opp.pre of the contracted edges. Be careful: these edges might also have been deleted if they coincided with e or e.opp

ddg.halfedge.contract_face(f)[source]

Contract a face to a vertex.

Note that this can alter the manifold property if neighboring faces of f are triangles or opposite sides of f are part of a boundary:

  *-----*
 /|     |
* |  f  |  ->  *--*
 \|     |
  *-----*

*-----*-----*-----*      *   *
|     |     |     |      |\ /|
|     |  f  |     |  ->  | * |
|     |     |     |      |/ \|
*-----*-----*-----*      *   *

Parameters:

fface: to be contracted

Returns:

vertex: the face was contracted to

ddg.halfedge.diagonals(hds, boundary_face_incidence=4, append_single_edges=True)[source]

Creates two hds’ with the diagonal combinatorics to the given hds.

The given hds will be bi-colored and if a vertex of one color is adjacent to more than two vertices of the other color this vertex will be replaced by a face build from the surrounding vertices. In this sense two new halfedge data structures are build. The vertices inherit all (manually set) attributes of the given vertices an additionally have an attribute ‘old_index’ storing the previous vertex index. The construction uses the ifs datastructure, if a vertex attribute ‘ifs_index’ and a face attribute ‘ifs_face_index’ exists, they will be removed.

Parameters:

hds: ddg.halfedge.Surface: Surface to create the hds’ from. It must be able to apply halfedge.set.bicolor_vertices to this.
boundary_face_incidence: int (default=4): If a boundary vertex is incident to at least this many vertices of the other color, then a face will be added in the above sense. If it is adjacent to less, only the edges will be added, excluding the edge along the boundary of the original surface.
append_single_edges: bool (default=True): If set to ‘True’ edges that do not belong to a face will be added (i.e., ‘tentacles’ at the corners of rectangular grid-like hds). This means the resulting hds might not be a manifold.

Returns:

hds1, hds2: The resulting hds’ of diagonal combinatoric.

Raises:

ddg.indexedfaceset.BoundaryException

If in the resulting surface two faces are only connected to each other by one vertex, like this:

/\/\
\/\/

ddg.halfedge.extrude(f, remove=True)[source]

Extrude a face of a surface, adding a new face between each halfedge.

Parameters:

fface: A face of a surface.
removebool (default=True): If True, remove the face f after extrusion.

Returns:

The extruded face.

ddg.halfedge.fill_hole(e)[source]

Fills a hole, i.e. a loop of boundary edges, with a face.

Parameters:

eedge: An interior halfedge belonging to the loop of boundary edges that is to fill.

Returns:

face

Raises:

ValueError: If there already is a face and no hole to fill.

ddg.halfedge.join_coplanar_faces(surf, co_attr='co', atol=None, rtol=None)[source]

Investigates whether a surface has triangulated, planar faces and if needed the triangulation will be removed, i.e. triangles will be joined to a face with more than three vertices.

Parameters:

surfsurface

The halfedge surface.

co_attrstr

The attribute name that contains the coordinate attribute of the vertices.

atol, rtolfloat or None (default=None)

Tolerances used to determine whether two faces are coplanar.

This function uses the global tolerance defaults if atol or rtol are set to None. See ddg.nonexact for details.

ddg.halfedge.join_neighbouring_faces(e)[source]

Joins two adjacent faces by removing the edge they have in common.

Parameters:

eedge: The edge to be removed of its corresponding surface.

Returns:

None

ddg.halfedge.remove_edge(e)[source]

Remove an edge from a surface.

Also removes faces that e or e.opp belong to.

Parameters:

eedge

ddg.halfedge.remove_face(f)[source]

Removes a specified face from its surface.

The corresponding halfedges will be retained and their face set to be None.

Parameters:

fface: The face to be removed of its corresponding surface.

Returns:

None

ddg.halfedge.remove_vertex(v)[source]

Remove a vertex from a surface.

Also removes all incoming and outgoing edges and any faces that these edges belong to.

Parameters:

vvertex: The vertex to be removed from the surface it belongs to.

ddg.halfedge.reverse_orientation(s)[source]

Function to reverse the orientation of edges of a surface.

Parameters:

s: ddg.halfedge.Surface: Surface to reverse the orientation on

ddg.halfedge.split_face_at(f, v1, v2)[source]

Insert a new edge between two vertices and thereby split a face into two.

Parameters:

fface: The face that will be split into two faces.
v1, v2vertex: The vertices between a new edge will be inserted to split the face. They need to be vertices in the boundary of f.

Returns:

new_edgeedge: Returns the just added halfedge which is pointing towards v2, i.e. with edge.head == v2 and edge.tail == v1.

ddg.halfedge.stellar_subdivide(f)[source]

Adds a new vertex and subdivides the given face by stellar subdivision.

The given face f subdivides into number of boundary edges many triangular faces. The former face is removed.

Parameters:

fface

Returns:

peakvertex: The newly added vertex.

See also

datastructures.halfedge.modify.subdivide: Subdivides a half-edge surface’s faces by bisecting the edges and connecting the new vertices.

ddg.halfedge.subdivide(surface, steps=1, co_attr='co')[source]

Subdivides a half-edge surface’s faces by bisecting the edges and connecting the new vertices.

Bisects every edge of the surface into two segments and a new vertex. Then the vertices of any face form a cycle in which the old and new vertices alternate. The new vertices are connected in this order. This procedure is repeated steps many times. The number of new faces is exponential in steps.

Parameters:

surfddg.halfege.Surface: The half-edge surface.
steps: int (default=1): Number of repeated subdivisions.
co_attrstr or None (default=’co’): A string can be given representing the attribute name that contains the coordinate attribute of the vertices. Then the vertex subdividing the edge is set to its midpoint. If None is given the subdivision is purely combinatorial.

Returns:

None

See also

ddg.halfedge.modify.stellar_subdivide: Adds a new vertex and subdivides the given face by stellar subdivision.

ddg.halfedge.subdivide_edge(e, number_of_segments)[source]

Subdivides an edge into the given number of segments.

Parameters:

eedge: A halfedge of the edge that will be subdivided.
number_of_segmentsint: The number of segments the edge will be subdivided into.

Returns:

list containing

segment of newly subdivided edge based at e.tail
segment of newly subdivided edge based at e.opp.tail
List of all vertices that were added by subdivision.

ddg.halfedge.zip_digon(f)[source]

Zips a digon to an edge

Parameters:

fface: A digon

Returns:

f.edge.oppedge

Raises:

ValueError if parameter f is not a digon

ddg.halfedge.bicolor_edges(hds, color_attr='color', colors=[0, 1], initial_edge_index=0, return_single_edges=True)[source]

Bi-colors single edges of a half-edge data structure (using a bfs algorithm) where a single edge corresponds to the join of e and e.opp (non-directed). Therefore e.color and e.opp.color always coincide. For this necessarily all interior vertices must have even valency (or 1, counting single edges) and all faces an even amount of adjacent edges. Boundary vertices may have uneven degree, given that there are exactly two consecutive boundary edges that will be assigned with the same color (for example considering a rectangular quad grid with all vertical and horizontal edges colored respectively).

Parameters:

hdsddg.halfedge.Surface
color_attrstring (default=’color’): Name of the edge attribute that is set to distinguish the bi-coloring.
colorsiterable of shape (2,) (default=[0,1]): Values set to the edge attribute ‘color_attr’. For the two families of edges, the attribute value is set to colors[0], colors[1], respectively.
initial_edge_indexint (default=0): Begins by setting colors[0] to the edge of given index
return_single_edgesbool (default=True): If True the lists returned will consist of one halfedge for each two incident vertices, otherwise both halfedges will be added to the corresponding list.

Returns:

[e1 , e2][list, list]: List of two lists of half-edges with new attributes. Each list containing half-edges of one color.

ddg.halfedge.bicolor_faces(hds, color_attr='color', colors=[0, 1], initial_face_index=0)[source]

Bi-colors faces of a half-edge data structure (dual of a bipartite simply connected graph).

Parameters:

hdsddg.halfedge.Surface
color_attrstring (default=’color’): Name of the face attribute that is set to distinguish the bi-coloring.
colorsiterable of shape (2,) (default=[0,1]): Values set to the face attribute ‘color_attr’. For the two families of face, the attribute value is set to colors[0], colors[1], respectively.

Returns:

f1 , f2list, list: Two lists of faces with new attributes. Each list containing faces of one color.

ddg.halfedge.bicolor_vertices(hds, color_attr='color', colors=[0, 1], initial_vertex_index=0)[source]

Bi-colors vertices of a half-edge data structure (bipartite simply connected graph).

Parameters:

hdsddg.halfedge.Surface
color_attrstring (default=’color’): Name of the vertex attribute that is set to distinguish the bi-coloring.
colorsiterable of shape (2,) (default=[0,1]): Values set to the vertex attribute ‘color_attr’. For the two families of vertices, the attribute value is set to colors[0], colors[1], respectively.

Returns:

v1 , v2list, list: Two lists of vertices with new attributes. Each list containing vertices of one color.

ddg.halfedge.set_attr_by_function(hds, function, cell_type='verts', attr_name='attr')[source]

Utility to set attributes of cells of a hds using a manually defined function. The function itself should get a single cell as the first argument. Further arguments can be passed using *args or **kwargs.

Parameters:

hdsddg.halfedge.Surface
functionfunction of signature function(cell): This function will be called for each cell of the corresponding cell type. The return value will be set as the cell’s attribute value.
cell_typestring (default=’verts’): String defining the cells, either ‘verts’, ‘edges’ or ‘faces’.
attr_namestr (default=’attr’): Name of the cell attribute that will store the assigned values.

Returns:

The newly generated attribute.

ddg.halfedge.set_euclidean_length_attr(hds, co_attr='co', attr_name='length')[source]

Adds a length attribute to all edges of the surface.

It stores the Euclidean length on edges, calculated via vertex-coordinates of incident vertices.

Parameters:

hdsddg.halfedge.Surface: The hds where vertices have a coordinate attribute that stores Euclidean coordinates.
co_attrstring (default=’co’): Name of the vertex attribute that stores the coordinates.
attr_namestring (default=’length’): Name of the new edge attribute.

Returns:

The newly generated attribute

Raises:

AttributeError:: If the vertices do not have the given coordinate attribute

ddg.halfedge.set_minimal_valency_attr(hds, cell_type='verts', attr_name='has_minimal_valency', attr_values=[True, False])[source]

Sets a cell attribute to true (or any given value) if the cell has minimal valency.

Parameters:

hdsddg.halfedge.Surface
cell_typestring (default=’verts’): String defining the cells, either ‘verts’, ‘edges’ or ‘faces’.
attr_namestr (default=’has_minimal_valency’): Name of the cell attribute that will store the assigned values.
attr_values:: Values to be stored in the attribute that indicate whether the cell has minimal valency or not.

Returns:

The newly generated attribute

ddg.halfedge.set_valency_attr(hds, cell_type='verts', attr_name='valency')[source]

Sets an attribute that stores the valency of vertices or faces of a halfedge surface, Depending on the given cell type the valency is the number of neighbouring vertices of a vertex, or the number of neighbouring faces of a face.

Parameters:

hdsddg.halfedge.Surface
cell_typestring (default=’verts’): String defining the cells, either ‘verts’ or ‘faces’.
attr_namestr (default=’valency’): Name of the cell attribute that will store the assigned values.

Returns:

The newly generated attribute.

ddg.halfedge.coordinate_polyline(e)[source]

ddg.halfedge.coordinate_polylines(hed)[source]

Finds parallel coordinate lines in a grid-like half-edge data structure with quadrilateral faces.

Parameters:

hedhalf-edge data structure

Returns:

x_lines, y_linesdeque , deque: Consists of deques consisting of half-edges representing the polylines. Each polyline is only represented by one chain of half-edges with fixed direction

Notes

The y-direction ist given by v0.edge where v0 ist the first vertex of hed.verts.

ddg.halfedge.integrate_one_form(hds, start_vertex, start_vertex_co, co_attr, edge_attr, boundary_attr=None)[source]

Lays out a surface using edge directions and lengths via breadth-first traversal. I.e. integrates a discrete one-form with values stored on hds.edges.

Parameters:

hdsddg.halfedge.Surface

Halfedge object with combinatorics and edge attributes.

start_vertexhds.verts

Initial vertex to start from.

start_vertex_conp.ndarray, shape (3,)

3D position of the start_vertex.

co_attrstr

Name of the vertex attribute to store the new coordinates.

edge_attrstr

Name of the edge attribute storing new edge vectors (shape (3,)). The edge vectors must be scaled to desired length.

boundary_attrstr (default = None)

Vertex attribute with values True/False. If a string is given,: the BFS stops further traversal from that vertex. Useful for example for vertices close to infinity.

Returns:

hdsddg.halfedge.Surface: Same halfedge object with new vertex coordinates stored under co_attr.

ddg.halfedge.verify_closure_one_form(hds, edge_attr, tol=1e-06)[source]

Verifies closure of a discrete one-form with edge lenths and directions stored in an attribute called edge_attr.

Parameters:

hdsddg.halfedge.Surface: Halfedge object.
edge_attr: str: Name of the edge attribute storing the new scaled edge vectors.
tolfloat(default: 1e-6): Tolerance for the error considered acceptable.

Returns:

int: Number of faces with large closure errors.

ddg.halfedge.arrow(resolution=20, heights=(0, 0.7, 0.7, 1), radii=(0.05, 0.05, 0.125), co_attr='co')[source]

Create an arrow as a half-edge surface.

This is useful to visualise vectors.

By default, the arrow will point up. The bottom will be at (0, 0, 0) and the head at (0, 0, 1).

Parameters:

resolutionint (default=20): Number of vertices around the center of rotation. Minimum is 3.
heightsfloat sequence of length 4 (default=(0, 0.7, 0.7, 1)): First element defines height of the bottom of the stick, the second the height of the top of the stick, the third the height of the base of the tip and the forth the height of the tip of the head.
radiifloat sequence of length 3 (default=(0.05, 0.05, 0.125)): First element defines the radius of the bottom of the stick, second the radius of the top of the stick and the third the radius of the base of the tip.
co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: An arrow.

ddg.halfedge.convexhull_3d(A, join_coplanar_triangles=True, co_attr='co')[source]

Creates a halfedge surface of the convex hull of the input points.

Parameters:

Aarray: Input array of 3 dimensional coordinates of the form [ , , ] Dimension of the input points has to be three, i.e. non-planar.
join_coplanar_trianglesbool (default=True): If True, planar faces will stay triangulated. Otherwise the triangulation will be removed and result in one bigger face.
co_attrstr (default=”co”): The name of the vertex attribute that stores the coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: The convex hull.

Notes

Coordinate attribute The coordinate attribute co_attr assigned to the vertices is of type numpy.ndarray and contains the coordinates of the input.

ddg.halfedge.cube(co_attr='co')[source]

Create a cube as a half-edge surface.

By default, standard coordinates of a unit cube, centered at (0, 0, 0), will be assigned to the vertices.

Parameters:

co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: A cube.

ddg.halfedge.cylinder(resolution=20, fill_caps=True, top_radius=1, bot_radius=1, length=1, center=(0, 0, 0), normal=(0, 0, 1), co_attr='co')[source]

Create a cylinder as a half-edge surface.

Parameters:

resolution: int (default=20): The number of vertices on each side.
fill_capsbool (default=True): If True, include the faces of the bottom and the top.
top_radiusfloat (default=1): The radius of the top of the cylinder.
bot_radiusfloat (default=1): The radius of the bottom of the cylinder
lengthfloat (default=1): The length of the cylinder.
centerarray_like of shape (3,) (default=(0, 0, 0)): The center of the bottom of the cylinder.
normalarray_like of shape (3,) (default=(0, 0, 1)): The normal of the cylinder’s top and bottom faces.
co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: A cylinder.

ddg.halfedge.disc(circle_subdivisions=20, fill_face=True, radius=1, center=(0, 0, 0), normal=(0, 0, 1), co_attr='co')[source]

Create a disc as a half-edge surface.

By default, the disc is embedded in R^3 with center (0, 0, 0), radius 1 and normal vector (0, 0, 1).

Parameters:

circle_subdivisions: int (default=20): Number of vertices on the boundary of the circle or disc.
fill_face: bool (default=True): If True, fill the edge loop with a face.
radiusfloat (default=1): The radius of the disc.
centerarray_like of shape (3,) (default=(0, 0, 0)): The center of the disc as an array_like in 3D space.
normalarray_like of shape (3,) (default=(0, 0, 1)): The normal vector of the disc.
co_attrstr (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: A disc.

ddg.halfedge.dodecahedron(co_attr='co')[source]

Create a dodecahedron as a half-edge surface.

By default, standard coordinates of a unit dodecahedron, centered at [0, 0, 0], will be assigned to the vertices and can be accessed via the attribute coordinate co.

Parameters:

co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: A dodecahedron.

ddg.halfedge.grid(shape, co_attr='co')[source]

Create a triangle grid as a half-edge surface.

The shape defines the number of vertices in each direction. Both 2D and 3D grids are supported.

Parameters:

shapetuple of length 2 or 3: Shape of the grid. The first entry is the number of vertices in the x-direction, the second the number of vertices in the y-direction and the third (if given) the number of vertices in the z-direction.
co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: A quadrilateral grid.

ddg.halfedge.icosahedron(co_attr='co')[source]

Create an icosahedron as a half-edge surface.

By default, standard coordinates of a unit icosahedron, centered at [0, 0, 0], will be assigned to the vertices and can be accessed via the attribute coordinate co.

Parameters:

co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: An icosahedron.

ddg.halfedge.icosphere(subdivision_steps=1, radius=1, co_attr='co')[source]

Create an icosphere as a half-edge surface.

By default, standard coordinates of a unit icosphere, centered at [0, 0, 0], will be assigned to the vertices and can be accessed via the attribute coordinate co.

Parameters:

subdivision_stepsint (default=1): Number of subdivisions performed, e.g. 0 for the icosahedron, 1 to subdivide each face of the icosahedron into 4 triangles, 2 to subdivide each face of the icosahedron into 16 triangles and so on.
radiusfloat (default=1): radius of the icosphere
co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: An icosphere.

Notes

Coordinate attribute The coordinate attribute co_attr assigned to the vertices is of type numpy.ndarray and contains the standard coordinates of a unit icosphere.

ddg.halfedge.octahedron(co_attr='co')[source]

Create an octahedron as a half-edge surface.

By default, standard coordinates of a unit octahedron, centered at [0,0,0], will be assigned to the vertices and can be accessed via the attribute coordinate co.

Parameters:

co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: An octahedron.

ddg.halfedge.tetrahedron(co_attr='co')[source]

Create a tetrahedron as a half-edge surface.

By default, standard coordinates of a unit tetrahedron, centered at (0, 0, 0), will be assigned to the vertices.

Parameters:

co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: A tetrahedron.

ddg.halfedge.triangle_grid(shape, co_attr='co')[source]

Create a triangle grid as a halfedge.

The shape defines the number of vertices in each direction. Both 2D and 3D grids are supported.

Parameters:

shapetuple of length 2 or 3: Shape of the grid. The first entry is the number of vertices in the x-direction, the second the number of vertices in the y-direction and the third (if given) the number of vertices in the z-direction.
co_attrstr, optional (default=”co”): The name of the vertex attribute that stores the coordinates. If co_attr=None, don’t assign any coordinates.

Returns:

sddg.datastructures.halfedge.surface.Surface: A triangle grid.

ddg.halfedge.boundary_edges(surf)[source]

Get a list of all boundary half-edges of a surface.

Parameters:

surfddg.halfedge.Surface

Yields:

edge: All boundary half-edges of a surface.

ddg.halfedge.boundary_vertices(surf)[source]

Get all boundary vertices of a surface.

Parameters:

surfsurface

Yields:

vertex: All boundary vertices of a surface.

ddg.halfedge.complement(cells, type, surface)[source]

Parameters:

cells: iterable: Iterable of cells of a surface to find the complement from.
type: str: Type of the cells, “verts”, “edges” or “faces”
surface: ddg.halfedge.Surface: Surface that the cells belong to.

Returns:

set: set of complement cells

ddg.halfedge.count_edges_in_loop(e)[source]

Counts the number of consecutive half-edges in a loop along a given one.

Parameters:

eedge: The edge whose number of consecutive half-edges in a loop is counted.

Returns:

int: The number of half-edges belonging to the edge loop along e.

ddg.halfedge.edge_loop(e)[source]

Get all consecutive edges of a given edge, forming a loop.

Parameters:

eedge: Starting edge of the edge loop.

Yields:

edge: The consecutive edges in a loop starting with argument edge e.

ddg.halfedge.edge_loop_from_face(f)[source]

Get the edges of a face in cyclic order.

Parameters:

fface

Yields:

edge: The edges of the face f in cyclic order.

ddg.halfedge.face_vertices(f)[source]

Get the boundary vertices of a face in cyclic order.

Parameters:

fface

Yields:

vertex: The boundary vertices of the face f in cyclic order.

ddg.halfedge.in_edges(v)[source]

Get the incoming edges of a vertex,

Parameters:

vvertex

Yields:

edge: All edges pointing to the vertex v (i.e., edge.head = v).

ddg.halfedge.interior_edges(surf)[source]

Get all interior half-edges of a surface.

Parameters:

surfddg.halfedge.Surface

Yields:

edge: All interior half-edges of a surface.

ddg.halfedge.interior_vertices(surf)[source]

Get all interior vertices of a surface.

Parameters:

surfddg.halfedge.Surface

Yields:

vertex: All interior vertices of a surface.

ddg.halfedge.is_boundary_edge(e)[source]

Checks whether a half-edge lies on the boundary of the surface.

Parameters:

eedge: The edge that is checked for being a boundary edge.

Returns:

bool: True if e is a boundary edge, False if not.

ddg.halfedge.is_boundary_vertex(v)[source]

Checks whether a vertex lies on the boundary of the surface..

Parameters:

vvertex: The vertex that is checked for being a boundary vertex.

Returns:

bool: True if v is a boundary vertex, False if not.

ddg.halfedge.is_connected(s)[source]

Whether a half-edge object is connected.

The empty set counts as connected.

Parameters:

sddg.halfedge.Surface

Returns:

bool

ddg.halfedge.is_triangulation(surf)[source]

Checks if a surface is a triangulation.

Parameters:

surfddg.halfedge.Surface: The surface that is checked for being a triangulation.

Returns:

bool

ddg.halfedge.length_from_co(e, co_attr='co')[source]

Calculates the euclidean length of an edge, provided its vertices have coordinates.

Parameters:

eedge: The edge whose length will be calculated.
co_attrstring (default=’co’): Name of the vertex attribute storing the coordinates.

Returns:

ffloat: The length of the edge ‘e’.

Raises:

AttributeError: If head or tail of the edge has no coordinate attribute ‘co’.

ddg.halfedge.number_of_edges(f)[source]

Counts the number of half-edges associated with the given face.

Parameters:

fface: The face whose number of half-edges is counted.

Returns:

int: The number of half-edges belonging to face f.

ddg.halfedge.opposite_edge_at_head(e)[source]

ddg.halfedge.opposite_edge_in_face(e)[source]

ddg.halfedge.out_edges(v)[source]

Get the outgoing edges of a vertex.

Parameters:

vvertex

Yields:

edge: All edges pointing away from the vertex v (i.e., edge.tail == v).

ddg.halfedge.single_edges(surf)[source]

Yields a generator that iterates through half of the half-edges of a surface

Parameters:

surf: surface: The half-edge data through which must be iterated

Yields:

edge:: half of the half-edges

ddg.halfedge.some_edge(s)[source]

Get one edge of the given surface.

Parameters:

sddg.halfedge.Surface

Returns:

eedge: One of the edges of the given surface.

ddg.halfedge.some_face(s)[source]

Get one face of the given surface.

Parameters:

sddg.halfedge.Surface

Returns:

fface: One of the faces of the given surface.

ddg.halfedge.some_vertex(s)[source]

Get one vertex of the given surface.

Parameters:

sddg.halfedge.Surface

Returns:

vvertex: One of the vertices of the given surface.

ddg.halfedge package

Submodules

Module contents