Class Polyhedron_3<X extends Point_>

java.lang.Object
Jcg.polyhedron.Polyhedron_3<X>
Record Components:
X - the type of geometric coordinates (2D or 3D), real or integer coordinates
public class Polyhedron_3<X extends Point_> extends Object
Pointer-based implementation of the Half-edge data structure for polyhedral meshes (for representing planar and surface orientable meshes).

This data structure allows us to represent both planar maps (embedded in 2D) and 3D surface meshes (embedded in R^3).
The generic type X allows us to choose between the two cases: X may be set either as Point_2 or Point_3
Author:
Luca Castelli Aleardi (Ecole Polytechnique, INF562/INF574, 2010-2022)
See Also:
  • invalid reference 
    for the Manipulation of an orientable surface

  • Field Details

  • Constructor Details

    • Polyhedron_3

      public Polyhedron_3()

    • Polyhedron_3

      public Polyhedron_3(int n, int e, int f)
      Initialize a polyhedron wiith a given number of vertices, edges and faces
      Parameters:
      n - number of vertices
      e - number of half-edges
      f - number of faces

  • Method Details

    • clean

      public void clean()
      Remove all undefined (null references) vertices, half-edges and faces.
      Indices of vertices/edges/faces are reset.

    • DecorateVertices

      public void DecorateVertices()

    • sizeOfVertices

      public int sizeOfVertices()

    • sizeOfFacets

      public int sizeOfFacets()

    • sizeOfHalfedges

      public int sizeOfHalfedges()

    • vertexDegree

      public int vertexDegree(Vertex<X> v)
      compute the degree of a vertex

    • isClosed

      public boolean isClosed()
      Check whether the mesh is closed (no boundaries)
      Returns:
      true if there are no border edges

    • isPureBivalent

      public boolean isPureBivalent()
      Check whether all vertices have degree exactly two.
      Warning: not implemented yet
      Returns:
      true if all vertices have exactly two incident edges

    • isPureTrivalent

      public boolean isPureTrivalent()
      Check whether all vertices have degree exactly three.
      Warning: not implemented yet
      Returns:
      true if all vertices have exactly three incident edges

    • isPureTriangle

      public boolean isPureTriangle()
      Check whether the polyhedral surface is a triangle mesh (all faces are triangles)
      Returns:
      true iff the every face is a triangle

    • isPureQuad

      public boolean isPureQuad()
      Check whether the polyhedral surface is a quad mesh (all faces are quadrangles)
      Returns:
      true iff the every face is a quadrangle

    • isTriangle

      public boolean isTriangle(Halfedge<X> h)
      Warning: not implemented yet
      Parameters:
      h - half-edge
      Returns:
      true iff the connected component denoted by h is a triangle

    • genus

      public int genus()
      Return the genus of the mesh (given by Euler formula).
      Warning: works only for meshes with one connected component
      Returns:
      the genus of the mesh

    • numberOfBoundaries

      public int numberOfBoundaries()
      Compute and return the number of boundaries

    • isValid

      public boolean isValid(boolean borders)
      Check whether the polyhedral surface is combinatorially consistent: manifold polygonal mesh.

      If borders==true normalization of the border edges is checked too.
      This method checks that each facet is at least a triangle and that the two incident facets of a non-border edge are distinct.

    • isFace

      public boolean isFace(Halfedge<X> e1, Halfedge<X> e2, Halfedge<X> e3)
      Check whether three half-edges define a triangle face of the mesh. The three input half-edges are assumed to have a coherent orientation.

      Warning: it works only for triangulations

    • isCycle

      public boolean isCycle(Halfedge<X> e1, Halfedge<X> e2, Halfedge<X> e3)
      Check whether three edges define an (oriented) cycle of length 3 (a triangle, not necessarily a face).
      The three input half-edges are assumed to have a coherent orientation

      Warning: it works only for (closed) triangulations

    • isSeparatingCycle

      public boolean isSeparatingCycle(Halfedge<X> e1, Halfedge<X> e2, Halfedge<X> e3)
      Check whether three edges define an (oriented) cycle of length 3 (a triangle, not necessarily a face).
      The three input halfedges are assumed to have a coherent orientation

      Warning: it works only for (closed) triangulations

    • getSeparatingCycles

      public ArrayList<Halfedge<X>[]> getSeparatingCycles(Halfedge<X> e)
      Return all separating separating containing the half-edge 'e1'. All resulting triangles are oriented. A triangle is stored using an array of 3 hal-edges.

      Warning: it works only for (closed) triangulations
      Returns:
      the list of all (oriented) separating triangles

    • getSeparatingTriangles

      public ArrayList<Halfedge<X>[]> getSeparatingTriangles()
      Return all separating separating in the triangulation

      Warnings:
      -) it assumes that all edges and vertices have an index
      -) it works only for (closed) triangulations
      Returns:
      the list of all (oriented) separating triangles

    • flipEdge

      public void flipEdge(Halfedge<X> e)
      Perform the flip of an edge e=(u, v)
      Remarks:
      -) an edge can be flipped only if the two incident faces (u, v, w) and (u, v, z) are both triangles
      -) boundary edges cannot be flipped
      -) w and z must be not adjacent: otherwise we create a multiple edge
      Parameters:
      e - the half-edge to be flipped

    • createCenterVertex

      public void createCenterVertex(Face<X> f, X point)
      Split a face by inserting a new vertex


      Warning: it works only for triangular faces

      Remark: faces are assumed to be ccw oriented (for combinatorics)

    • eraseCenterVertex

      public void eraseCenterVertex(Vertex<X> v)
      Replace the star of a vertex v by a new face.
      Warning: to be completed, not implemented yet
      Parameters:
      v - the vertex to be removed

    • eraseCenterVertex

      public Halfedge eraseCenterVertex(Halfedge<X> e)
      Erase the vertex 'v' pointed by 'e', by replacing the star of 'v' by a new face.

      Warning: this method is not computationally efficient, requiring O(n) time: it remove all elements (6 halfedges, 1 vertex, 2 faces) from the corresponding collections ('ArrayList').

      Remarks:

      -) it only does work with vertices having degree 3
      -) the faces incident to vertex 'v' are assumed to exist (no holes incident to 'v')
      -) faces are assumed to be ccw oriented (only for combinatorics)

      Returns:
      the halfedge h which precedes 'e' in ccw direction (in the new triangular face)

    • makeHole

      public Halfedge<X> makeHole(Halfedge<X> h)

    • fillHole

      public Halfedge<X> fillHole(Halfedge h)

    • addTriangleToBorder

      public Halfedge<X> addTriangleToBorder(Halfedge h, X point)
      Creates a new triangle facet within the hole incident to 'h' by connecting the tip of 'h' with two new halfedges and a new vertex.
      Returns:
      the halfedge of the new edge that is incident to the new facet and the new vertex.

    • makeTriangle

      public Halfedge<X> makeTriangle(X p1, X p2, X p3)
      A triangle with border edges is added to the polyhedral surface.
      Returns:
      a non-border halfedge of the triangle.

    • splitFacet

      public Halfedge<X> splitFacet(Halfedge<X> h, Halfedge<X> g)
      Split the facet incident to h and g into two facets with a new diagonal between the two vertices denoted by h and g respectively.

      Returns h->next() after the operation, i.e., the new diagonal. The new face is to the right of the new diagonal, the old face is to the left.
      The time is proportional to the distance from h to g around the facet.

    • joinFacet

      public Halfedge<X> joinFacet(Halfedge<X> h)
      Join the the facets incident to the half-edge h.
      Returns h->prev() after the operation, i.e., one edge of the (merged) face.
      Warning: we assume that faces and edges are indexed.

      The time is proportional to the size of the two facets.
      Parameters:
      h - the half-edge to be removed (the two incident vertices must have degree at least three)

    • edgeCollapse

      public void edgeCollapse(Halfedge<Point_3> e)
      Perform the collapse of half-edge e=(u,v). The half-edge e is shared by triangles (u,v,w) and (v,u,z).

    • splitEdge

      public Halfedge<X> splitEdge(Halfedge<X> h, X p)
      Split the half-edge h=(u,v) by inserting a new vertex, with coordinates given by the point p. As a result, a new pair of half-edges is inserted in the mesh.

      Remark: it works also for meshes with boundaries.
      Assumption: the half-edge must be incident to a face: h.face!=null
      Parameters:
      h - the half-edge to be split
      p - coordinates of the new vertex to insert
      Returns:
      the new inserted half-edge, having target point is p

    • resetMeshIndices

      public void resetMeshIndices()
      Reset indices for all: vertices, faces and halfedges.
      Indices correspond to the order of storage in the collections (e.g., vertex v0 is the first in the ArrayList 'vertices')

    • verticesToString

      public String verticesToString()
      Return a string representing the list of vertices

    • facesToString

      public String facesToString()
      Return a string representing the list of faces

    • edgesToString

      public String edgesToString()
      Return a string representing the list of faces