"""Module 'halfedge' defines the half edge data strucure.
Create a hafedge data structure representing a surface:
"""
from ddg.datastructures.halfedge import _node
from ddg.datastructures.halfedge.get import (
in_edges,
is_boundary_edge,
is_boundary_vertex,
out_edges,
)
from ddg.datastructures.halfedge.modify import _insert_edge, _link_edge_in
[docs]class Surface(object):
"""Finite cell decomposition of a 2-dimensional manifold, possibly
with boundary, represented by a half edge data structure.
"""
def __init__(self):
verts = _node.NodeClass(self, "Verts", ("edge",))
edges = _node.NodeClass(self, "Edges", ("opp", "nex", "pre", "head", "face"))
faces = _node.NodeClass(self, "Faces", ("edge",))
verts.__repr__ = lambda v: "Verts(index={}, edge={}, surface={})".format(
v.index,
v.edge.index if v.edge else "None",
"%x" % id(v.surf) if v.surf else "None",
)
edges.__repr__ = (
lambda e: "Edges(index={}, head={}, face={}, surface={})".format(
e.index,
e.head.index if e.head else "None",
e.face.index if e.face else "None",
"%x" % id(e.surf) if e.surf else "None",
)
)
faces.__repr__ = lambda f: "Faces(index={}, edge={}, surface={})".format(
f.index,
f.edge.index if f.edge else "None",
"%x" % id(f.surf) if f.surf else "None",
)
def get_tail(e):
return e.opp.head
edges.tail = property(get_tail, None, None)
self.verts = verts
self.edges = edges
self.faces = faces
self.name = "halfedge_object"
[docs] def add_vertex(self):
"""Add an isolated vertex.
Returns
-------
vertex
"""
return self.verts()
[docs] def add_edge(self, v1, v2, epre=None, enex=None):
"""Insert an edge between two boundary vertices.
Parameters
----------
v1, v2 : vertex
Boundary vertices that the edge should connect.
epre : edge 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.
"""
if v1.surf is not self:
raise ValueError(f"{v1.surf=} is not self.")
if v2.surf is not self:
raise ValueError(f"{v2.surf=} is not self.")
if not is_boundary_vertex(v1):
raise ValueError(f"{v1=} is not a boundary vertex.")
if not is_boundary_vertex(v2):
raise ValueError(f"{v2=} is not a boundary vertex.")
if epre is not None:
if not is_boundary_edge(epre):
raise ValueError(f"{epre=} is not a boundary edge.")
if epre.head is not v1:
raise ValueError(f"{epre.head=} is not {v1=}.")
if enex is not None:
if not is_boundary_edge(enex):
raise ValueError(f"{enex=} is not a boundary edge.")
if enex.tail is not v2:
raise ValueError(f"{enex.tail=} is not {v2=}.")
v1_is_isolated = v1.edge is None
v2_is_isolated = v2.edge is None
# Look up the boundary edges now so we don't accidentally get one of the
# newly added edges. I'm not sure if this can happen, but let's be sure.
if not v1_is_isolated:
# Look up an incoming boundary edge if None was given
if epre is None:
for edge in in_edges(v1):
if is_boundary_edge(edge):
epre = edge
break
eoppnex = epre.nex
if not v2_is_isolated:
# Look up an outgoing boundary edge if None was given
if enex is None:
for edge in out_edges(v2):
if is_boundary_edge(edge):
enex = edge
break
eopppre = enex.pre
# This sets v1.edge to e.opp if v1.edge is None, so v1.edge can't be used
# anymore to check if v1 is isolated
e = _insert_edge(v1, v2)
# Loop case
# I don't even know if this is allowed in halfedge. It works
# combinatorially but doesn't make sense for visualization purposes.
if v1 is v2:
# e becomes part of the boundary where the tentacle was attached
# e.opp -> e.opp -> ... becomes its own boundary loop
eoppnex = e.opp
eopppre = e.opp
if v1_is_isolated:
# v1 == v2 is the same isolated vertex.
# There will just be two boundary cycles e -> e -> ... and
# e.opp -> e.opp -> ...
epre = e
enex = e
else:
if v1_is_isolated:
epre = e.opp
eoppnex = e
if v2_is_isolated:
enex = e.opp
eopppre = e
_link_edge_in(epre, e, enex)
_link_edge_in(eopppre, e.opp, eoppnex)
return e
[docs] def add_face(self, n, v=[]):
"""
Adds an n-gon to the surface. The polygon is not connected to
any other polygons after addition.
Parameters
----------
n : int
number of vertices of the polygon to be added
v : list
vertices that become vertices of the polygon
new vertices are generated if there are non given
Returns
-------
face
the face that has been added
"""
tn = 2 * n
if not v:
v = [self.verts() for _ in range(n)]
else:
if n != len(v):
raise ValueError(
"Only "
+ str(len(v))
+ " of "
+ str(n)
+ " polygon vertices were specified."
)
e = [self.edges() for _ in range(tn)]
f = self.faces()
f.edge = e[0]
for i in range(n):
vi = v[i]
ei = e[2 * i]
eiopp = e[2 * i + 1]
ei.opp = eiopp
eiopp.opp = ei
einex = e[(2 * i + 2) % tn]
einexopp = e[(2 * i + 3) % tn]
ei.nex = einex
einex.pre = ei
eiopp.pre = einexopp
einexopp.nex = eiopp
ei.face = f
ei.head = einexopp.head = vi
vi.edge = ei
return f
[docs] def glue(self, e1, e2):
"""
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
----------
e1 : edge
interior edge of a face with its opposite being a boundary edge,
`e1.opp` will become `e2`
e2 : edge
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.
"""
edges = self.edges
if (type(e1) is not edges) or (type(e2) is not edges):
raise ValueError("Arguments must be edges of this surface.")
if e1 is e2:
raise ValueError("Cannot glue edge to itself.")
e1opp = e1.opp
e2opp = e2.opp
if (e1opp.face is not None) or (e2opp.face is not None):
raise ValueError("(e1.opp.face is not None) or (e2.opp.face is not None)")
e1head = e1.head
e1tail = e1opp.head
if (e2opp.head is e2.head) and (e1opp.head is not e1.head):
# Need to identify e1's tail with e1's head
self.verts.remove(e1tail)
e = e1opp
while True:
e.head = e1head
e = e.nex.opp
if e is e1opp:
break
e1tail = e1head
# Identify e2's head with e1's tail, if they are not already equal
if e2.head is not e1tail:
self.verts.remove(e2.head)
e = e2
while True:
e.head = e1tail
e = e.nex.opp
if e is e2:
break
# Identify e2's tail with e1's head, if they are not already equal
if e2.tail is not e1head:
self.verts.remove(e2.tail)
e = e2opp
while True:
e.head = e1head
e = e.nex.opp
if e is e2opp:
break
# Update pre and nex of e1's and e2's opp.nex and opp.pre
e1oppnex, e1opppre = e1opp.nex, e1opp.pre
e2oppnex, e2opppre = e2opp.nex, e2opp.pre
e2opppre.nex = e1oppnex if e1oppnex is not e1opp else e2oppnex
e1oppnex.pre = e2opppre if e2opppre is not e2opp else e1opppre
e2oppnex.pre = e1opppre if e1opppre is not e1opp else e2opppre
e1opppre.nex = e2oppnex if e2oppnex is not e2opp else e1oppnex
# Remove the former opposite edges.
# Take care: Their heads may link back to them.
if e1opp.head.edge is e1opp:
e1opp.head.edge = e2.nex.opp
edges.remove(e1opp)
if e2opp.head.edge is e2.opp:
e2opp.head.edge = e1.nex.opp
edges.remove(e2opp)
# glue e1 and e2:
e1.opp = e2
e2.opp = e1
[docs] def validate(self):
"""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.
"""
# not complete
#
# really? what's missing?
verts = self.verts
edges = self.edges
faces = self.faces
# Check that all attributes (pre, opp, edge etc.) point to instances of
# the respective node class belonging to this surface
for e in edges:
if not isinstance(e.nex, edges):
raise SurfaceError("e.nex is not an edge of the same surface.", e)
if not isinstance(e.pre, edges):
raise SurfaceError("e.pre is not an edge of the same surface.", e)
if not isinstance(e.opp, edges):
raise SurfaceError("e.opp is not an edge of the same surface.", e)
if not isinstance(e.head, verts):
raise SurfaceError("e.head is not a vertex of the same surface.", e)
if not ((e.face is None) or isinstance(e.face, faces)):
raise SurfaceError(
"e.face is not None or a face of the same surface.", e
)
for f in faces:
if not isinstance(f.edge, edges):
raise SurfaceError("f.edge is not an edge of the same surface.", f)
for v in verts:
if not (v.edge is None or isinstance(v.edge, edges)):
raise SurfaceError(
"v.edge is neither None nor an edge of the same surface.", v
)
# If a node is "removed", its surface is set to None, but it is
# still an instance of the node class and still exists in these
# attributes.
for e in edges:
if e.nex.surf is None:
raise SurfaceError("e.nex has been removed.", e)
if e.pre.surf is None:
raise SurfaceError("e.pre has been removed.", e)
if e.opp.surf is None:
raise SurfaceError("e.opp has been removed.", e)
if e.head.surf is None:
raise SurfaceError("e.head has been removed.", e)
if (e.face is not None) and (e.face.surf is None):
raise SurfaceError("e.face has been removed.", e)
for f in faces:
if f.edge.surf is None:
raise SurfaceError("f.edge has been removed.", f)
for v in verts:
if v.edge is not None and v.edge.surf is None:
raise SurfaceError("v.edge has been removed.", v)
# Check consistency
for e in edges:
if e.nex.pre is not e:
raise SurfaceError("e.nex.pre is not e.", e)
# Possibly missing "e.pre.nex is not e"?
if e.face is not e.nex.face:
raise SurfaceError("e.face is not e.nex.face.", e)
if e.head is not e.nex.opp.head:
raise SurfaceError("e.head is not e.nex.opp.head.", e)
for f in faces:
if f.edge.face is not f:
raise SurfaceError("f.edge.face is not f.", f)
for v in verts:
if v.edge is not None and v.edge.head is not v:
raise SurfaceError("v.edge.head is not v.", v)
# This does nothing for graphs.
# Probably not the most efficient to do this starting with a full set.
eset = {e for e in edges if e.face is not None}
for f in faces:
e = e0 = f.edge
while True:
eset.remove(e)
e = e.nex
if e is e0:
break
if eset:
raise SurfaceError("Not all face boundaries are simple loops.")
# A vertex coboundary is the "asterisk" shape of all halfedges going in
# and coming out of a vertex. Starting with an incoming edge, these can
# be traversed by doing e.nex.opp repeatedly and this should always be
# a simple loop.
# We check for this by walking these loops for every vertex and listing
# incoming edges until we reach the edge we started with. After doing
# this for every vertex, every halfedge should be listed exactly once.
# Probably not the most efficient to do this starting with a full set.
eset = set(edges)
for v in verts:
if v.edge is None:
continue
e = e0 = v.edge
while True:
eset.remove(e)
e = e.nex.opp
if e is e0:
break
if eset:
raise SurfaceError("Not all vertex coboundaries are simple loops.")
# Possibly missing: All boundary components are simple loops.
[docs] def validate_surface(self):
"""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.
"""
self.validate()
if not self.verts:
raise SurfaceError("Object is empty")
for e in self.edges:
if (e.face is None) and (e.opp.face is None):
raise SurfaceError("e.face and e.opp.face are both None.", e)
# Starting with a boundary edge e, we walk the vertex coboundary of
# e.head as in validate() until we find another incoming boundary edge.
# If this is not e, it has the same head as e.
for e in self.edges:
if e.face is not None:
continue
e1 = e
while True:
e1 = e1.nex.opp
if e1.face is None:
break
if e1 is not e:
raise SurfaceError(
"Two boundary edges have the same head.", e, e1, e.head
)
for v in self.verts:
if v.edge is None:
raise SurfaceError(f"Vertex {v} is isolated.")
[docs] def validate_curve(self):
"""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.
"""
self.validate_graph()
if not self.verts:
raise SurfaceError("Object is empty")
for e in self.edges:
if e.nex.opp is not e.opp.pre:
raise SurfaceError(f"Valency at vertex {e.head} is not 2.")
for v in self.verts:
if v.edge is None:
raise SurfaceError(f"Vertex {v} is isolated.")
[docs] def validate_graph(self):
"""Validate a graph.
Runs `validate` and checks that there are no faces.
Raises
------
SurfaceError
If object is invalid or has faces.
"""
self.validate()
if self.faces:
raise SurfaceError("Object has faces.")
[docs]class SurfaceError(Exception):
pass
if __name__ == "__main__":
import doctest
doctest.testmod(optionflags=doctest.ELLIPSIS)