Packages

c

geotrellis.vector.mesh

HalfEdgeTable

class HalfEdgeTable extends Serializable

Mutable, non-thread safe class to keep track of half edges during Delaunay triangulation.

Half edge meshes are representations of piecewise linear, orientable, manifold surfaces, with or without boundary (no Mobius strips, edges are shared by at most two facets, every vertex has a single continuous fan of facets emanating from it). Every facet in the mesh is defined by a loop of half edges that are in a linked list, and every facet is joined to its neighboring facets by linking complementary half edges. In short, a half edge has three pieces of information: (1) a vertex reference (dest), (2) a complementary HalfEdge (flip), and (3) a pointer to the next edge on the boundary of a facet. These are sufficient to allow complete navigation of a mesh.

For convenience, derived navigation operations are provided. Consider the following diagram:

v1 <---------- v2 <---------- v3
^|     e1      ^|     e2      ^|
||             ||             ||
|| e3       e4 || e5       e6 ||
||             ||             ||
|V     e7      |V     e8      |V
v4 ----------> v5 ----------> v6

Starting from e1, getNext produces the sequence e1, e3, e7, e4, e1, ...

Starting from e2, getPrev produces the sequence e2, e6, e8, e5, e2, ...

getFlip(e4) == e5 and getFlip(e5) == e4

rotCCWSrc(e4) == getFlip(e7)

rotCWSrc(e4) == e8

rotCCWDest(e4) == e2

rotCWDest(e4) == getFlip(e1)

getDest(e4) == v2

getSrc(e4) == getDest(e5) == v5

The HalfEdgeTable contains an Array[Int] in chunks of three where each of these chunks is specified as follows: [i,e1,e2] where i is the vertex of the halfedge (where the half edge 'points' to) e1 is the halfedge index of the flip of the halfedge (the halfedge that points to the source) e2 is the halfedge index of the next half edge (counter-clockwise of the triangle)

Linear Supertypes
Serializable, Serializable, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. HalfEdgeTable
  2. Serializable
  3. Serializable
  4. AnyRef
  5. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new HalfEdgeTable(_size: Int)

Value Members

  1. def allVertices(): Iterable[Int]
  2. def appendTable(that: HalfEdgeTable, reindex: (Int) ⇒ Int = x => x): Int

    Adds the content of another HalfEdgeTable to the current table and adjusts the vertex indices of the merged table (not the base object's table), if desired.

    Adds the content of another HalfEdgeTable to the current table and adjusts the vertex indices of the merged table (not the base object's table), if desired. The edge indices in the added table will be incremented to maintain correctness. The offset added to the edge indices will be returned so that any external references may be adjusted to match.

  3. def createHalfEdge(v: Int, flip: Int, next: Int): Int

    Create an edge for a single vertex, with the specified flip and next set.

  4. def createHalfEdge(v: Int): Int

    Create an edge pointing to single vertex.

    Create an edge pointing to single vertex. This edge will have no flip or next set.

  5. def createHalfEdges(v1: Int, v2: Int, v3: Int): Int

    Create three half edges that flip and point to each other in a triangle.

    Create three half edges that flip and point to each other in a triangle.

    returns

    The outer halfedge pointing at v1

    Note

    It's up to the caller to set these edges in counter clockwise order

  6. def createHalfEdges(v1: Int, v2: Int): Int

    Create two half edges that both flip and point to each other

    Create two half edges that both flip and point to each other

    returns

    the half edge point at v2

  7. def edgeIncidentTo(i: Int): Int
  8. def foreachInLoop(e0: Int)(f: (Int) ⇒ Unit): Unit
  9. def getDest(e: Int): Int

    Returns the vertex index for this half edge (the one in which it points to)

  10. def getFlip(e: Int): Int
  11. def getNext(e: Int): Int
  12. def getPrev(e: Int): Int
  13. def getSrc(e: Int): Int

    Returns the source vertex index for this half edge (the one in which it points from)

  14. def join(e: Int, opp: Int): Unit
  15. def killEdge(e: Int): Unit
  16. def mapOverLoop[T](e0: Int)(f: (Int) ⇒ T): Seq[T]
  17. def maxEdgeIndex(): Int

    Joins together two sections of a mesh along a common edge.

    Joins together two sections of a mesh along a common edge.

    Occasionally, it will be necessary to merge two sections of a triangulation along a common edge. This function accepts as arguments two edge references which share the same endpoints. Specifically, e = [A -> B] and opp = [B -> A] where the flips of each edge are on the boundary of the mesh. The end result of this function is that getFlip(e) = opp and getFlip(opp) = e and the surrounding mesh is properly connected (assuming the input meshes were correctly connected).

  18. def navigate(e0: Int, trans: (Int) ⇒ Coordinate, addedCmds: Map[Char, (String, (Int) ⇒ Int)]): Unit

    Provides an interactive, text based means to explore a mesh.

    Provides an interactive, text based means to explore a mesh.

    e0

    the initial edge for the navigation

    trans

    a function that transforms vertex indices to Coordinates

    addedCmds

    a Map from Char to (String, Int => Int) where the character is the key that will select this operation in the interface, the string is descriptive of the operation, and the Int => Int function maps the current edge to a new edge, possibly with side effects

  19. def neighborsOf(vi: Int): Seq[Int]
  20. def onBoundary(vi: Int, boundary: Int): Boolean
  21. def registerFace(e: Int): Unit
  22. def reindexVertices(reindex: (Int) ⇒ Int): Unit
  23. def removeIncidentEdge(i: Int): Map[Int, Int]
  24. def rotCCWDest(e: Int): Int

    Returns the halfedge index of the halfedge you get from rotating this halfedge counter-clockwise from it's destination along the triangulation

  25. def rotCCWSrc(e: Int): Int

    Returns the halfedge index of the halfedge you get from rotating this halfedge counter-clockwise from it's source along the triangulation

  26. def rotCWDest(e: Int): Int

    Returns the halfedge index of the halfedge you get from rotating this halfedge clockwise from it's destination along the triangulation

  27. def rotCWSrc(e: Int): Int

    Returns the halfedge index of the halfedge you get from rotating this halfedge clockwise from it's source along the triangulation

  28. def setDest(e: Int, v: Int): Unit

    Sets the vertex index for this half edge (the one in which it points to)

  29. def setFlip(e: Int, flip: Int): Unit

    Sets a half edge's flip half edge

  30. def setIncidentEdge(i: Int, e: Int): Map[Int, Int]
  31. def setNext(e: Int, next: Int): Unit

    Sets a half edge's next half edge

  32. def setSrc(e: Int, v: Int): Unit

    Sets the source vertex index for this half edge (the one in which it points from)

  33. def showLoop(e0: Int): Unit