from collections import deque
from ddg.halfedge._get import (
count_edges_in_loop,
edge_loop,
in_edges,
interior_vertices,
is_boundary_edge,
out_edges,
)
from ddg.math.euclidean import distance as euclidean_distance
[docs]def bicolor_vertices(hds, color_attr="color", colors=[0, 1], initial_vertex_index=0):
"""
Bi-colors vertices of a half-edge data structure (bipartite simply connected graph).
Parameters
----------
hds : ddg.halfedge.Surface
color_attr : string (default='color')
Name of the vertex attribute that is set to distinguish the bi-coloring.
colors : iterable 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 , v2 : list, list
Two lists of vertices with new attributes.
Each list containing vertices of one color.
"""
hds.verts.add_attribute(color_attr)
v = list(hds.verts)[initial_vertex_index]
verts = [[v], []]
queue = deque([(v, 0)])
while len(queue) > 0:
v_act, v_color = queue.popleft()
for e in out_edges(v_act):
if e.head not in verts[1 - v_color]:
queue.append((e.head, 1 - v_color))
verts[1 - v_color].append(e.head)
setattr(v_act, color_attr, colors[v_color])
if len(verts[0]) + len(verts[1]) != len(hds.verts):
raise ValueError(
"Not able to bi-color grid. Maybe it has more than one connected component"
" or does not havequadrilateral faces."
)
return verts[0], verts[1]
[docs]def bicolor_faces(hds, color_attr="color", colors=[0, 1], initial_face_index=0):
"""
Bi-colors faces of a half-edge data structure (dual of a bipartite simply
connected graph).
Parameters
----------
hds : ddg.halfedge.Surface
color_attr : string (default='color')
Name of the face attribute that is set to distinguish the bi-coloring.
colors : iterable 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 , f2 : list, list
Two lists of faces with new attributes.
Each list containing faces of one color.
"""
hds.faces.add_attribute(color_attr)
f = list(hds.faces)[initial_face_index]
faces = [[f], []]
queue = deque([(f, 0)])
while len(queue) > 0:
f_act, f_color = queue.popleft()
for e in edge_loop(f_act.edge):
if e.opp.face is not None and e.opp.face not in faces[1 - f_color]:
queue.append((e.opp.face, 1 - f_color))
faces[1 - f_color].append(e.opp.face)
setattr(f_act, color_attr, colors[f_color])
if len(faces[0]) + len(faces[1]) != len(hds.faces):
raise ValueError(
"Not able to bi-color grid. Maybe it has more than one connected component"
" or it has interior faces with an odd number of vertices."
)
return faces[0], faces[1]
[docs]def bicolor_edges(
hds,
color_attr="color",
colors=[0, 1],
initial_edge_index=0,
return_single_edges=True,
):
"""
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
----------
hds : ddg.halfedge.Surface
color_attr : string (default='color')
Name of the edge attribute that is set to distinguish the bi-coloring.
colors : iterable 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_index : int (default=0)
Begins by setting colors[0] to the edge of given index
return_single_edges : bool (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.
"""
def edge_on_boundary(edge):
return is_boundary_edge(edge) or is_boundary_edge(edge.opp)
hds.edges.add_attribute(color_attr)
e = list(hds.edges)[initial_edge_index]
visited_edges = set()
edges = [[], []]
queue = deque([(e, 0)])
if any(count_edges_in_loop(f.edge) % 2 for f in hds.faces):
raise ValueError(
"Given hds contains a face with uneven valency. Thus it is not possible to"
" bi-color edges."
)
# The n != 1 check is necessary: There could be an interior face looking like
#
# o---o
# | |
# o-o |
# | |
# o---o
#
# So there could be a vertex with only one incoming edge which is not a tentacle,
# i.e. not a boundary vertex. This does not preclude a bi-coloring.
if any(
n != 1 and n % 2
for n in [len(list(in_edges(v))) for v in interior_vertices(hds)]
):
raise ValueError(
"Given hds contains an interior vertex with uneven valency. Thus it is not"
" possible to bi-color edges."
)
while queue and len(visited_edges) < len(hds.edges):
e_act, e_color = queue.pop()
edges[e_color].append(e_act)
if not return_single_edges:
edges[e_color].append(e_act.opp)
visited_edges.add(e_act)
visited_edges.add(e_act.opp)
next_edge = None
next_color = e_color
# append edges of vertex star of e_act in queue
while next_edge != e_act.opp:
if next_edge is None:
next_edge = e_act.opp
# two consecutive boundary edges with common vertex of odd valency,
# i.e. next edge has same color
if (
edge_on_boundary(next_edge)
and edge_on_boundary(next_edge.opp.nex)
and len(list(in_edges(next_edge.tail))) % 2 != 0
):
num_boundary_edges = len(
list([e for e in in_edges(next_edge.tail) if edge_on_boundary(e)])
)
if num_boundary_edges != 2 and not num_boundary_edges == len(
list(in_edges(next_edge.tail))
):
raise ValueError(
f"Vertex {next_edge.tail.index} is boundary vertex with odd"
f" valency ({len(list(in_edges(next_edge.tail)))}) and has not"
f" 2 but {num_boundary_edges} boundary edges."
)
next_edge = next_edge.opp.nex
next_color = next_color
else:
next_edge = next_edge.opp.nex
next_color = 1 - next_color
if next_edge not in visited_edges and next_edge.opp not in visited_edges:
queue.append((next_edge, next_color))
setattr(e_act, color_attr, colors[e_color])
setattr(e_act.opp, color_attr, colors[e_color])
return edges
[docs]def set_valency_attr(hds, cell_type="verts", attr_name="valency"):
"""
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
----------
hds : ddg.halfedge.Surface
cell_type : string (default='verts')
String defining the cells, either 'verts' or 'faces'.
attr_name : str (default='valency')
Name of the cell attribute that will store the assigned values.
Returns
-------
The newly generated attribute.
"""
attribute = getattr(hds, cell_type).add_attribute(attr_name, None)
for cell in getattr(hds, cell_type):
if cell_type == "verts":
v = len(list(in_edges(cell)))
else:
v = len([e for e in edge_loop(cell.edge) if e.face is not None])
setattr(cell, attr_name, v)
return attribute
[docs]def set_euclidean_length_attr(hds, co_attr="co", attr_name="length"):
"""
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
----------
hds : ddg.halfedge.Surface
The hds where vertices have a coordinate attribute that stores
Euclidean coordinates.
co_attr : string (default='co')
Name of the vertex attribute that stores the coordinates.
attr_name : string (default='length')
Name of the new edge attribute.
Raises
------
AttributeError:
If the vertices do not have the given coordinate attribute
Returns
-------
The newly generated attribute
"""
if not hasattr(hds.verts, co_attr):
raise AttributeError(
"The vertices of the given hds do not have the given coordinate attribute"
f" {co_attr}."
)
def function(edge):
return euclidean_distance(
getattr(edge.head, co_attr), getattr(edge.tail, co_attr)
)
return set_attr_by_function(hds, function, cell_type="edges", attr_name=attr_name)
[docs]def set_attr_by_function(hds, function, cell_type="verts", attr_name="attr"):
"""
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
----------
hds : ddg.halfedge.Surface
function : function 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_type : string (default='verts')
String defining the cells, either 'verts', 'edges' or 'faces'.
attr_name : str (default='attr')
Name of the cell attribute that will store the assigned values.
Returns
-------
The newly generated attribute.
"""
attribute = getattr(hds, cell_type).add_attribute(attr_name, None)
for cell in getattr(hds, cell_type):
setattr(cell, attr_name, function(cell))
return attribute
[docs]def set_minimal_valency_attr(
hds, cell_type="verts", attr_name="has_minimal_valency", attr_values=[True, False]
):
"""
Sets a cell attribute to true (or any given value) if the cell has minimal valency.
Parameters
----------
hds : ddg.halfedge.Surface
cell_type : string (default='verts')
String defining the cells, either 'verts', 'edges' or 'faces'.
attr_name : str (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
"""
valency_attribute = getattr(hds, cell_type).add_attribute(attr_name, None)
set_valency_attr(hds, cell_type, attr_name="valency")
min_valency = min([cell.valency for cell in getattr(hds, cell_type)])
for cell in getattr(hds, cell_type):
setattr(
cell,
attr_name,
attr_values[0] if cell.valency == min_valency else attr_values[1],
)
delattr(getattr(hds, cell_type), "valency")
return valency_attribute