8
$\begingroup$

I ran into half-edges as part of the result of a Delaunay Triangulation library, but can't find an actual definition of what one is.

I understand vertices, edges and faces, but can't find a concrete definition of a half-edge.

$\endgroup$
2
  • $\begingroup$ as far as i know a half edge is a directed edge. That is, an edge with a defined begining and end rather than two points where order is irrelevant. I don't know how that would fit into a triangulation algorithm but i hope this helps. $\endgroup$ Dec 12, 2017 at 0:54
  • $\begingroup$ Here is a good practical introduction on the topic: fgiesen.wordpress.com/2012/02/21/… $\endgroup$ Dec 13, 2017 at 16:08

1 Answer 1

13
$\begingroup$

A half-edge is an edge split along its length, and having a directional component, that is, a beginning vertex and an end vertex. Where two polygons share an edge, each polygon gets a single half-edge between the same two vertices, which will have opposite directions if the winding order is consistent. These half-edges will have references to one another as two halves of a pair.

The full half edge data structure stores for each half-edge:

  • The polygon it belongs to
  • Previous and next half edges within the polygon
  • Its pair half-edge in a neighbouring polygon
  • Its origin vertex

This structure allows you to extract all sorts of connectivity information from a mesh, such as which edges or polygons lie around a particular vertex, simply by traversing the half-edges. There's a good article explaining it here.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer, I think I was partly thrown by the dissimilarity between the "half-edges" that the library provided (simply an array of indices) and the more fully fledged structures which came up when searching for half-edges. $\endgroup$ Dec 12, 2017 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.