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.
$\begingroup$
$\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$– Sebastián MestreDec 12, 2017 at 0:54
-
$\begingroup$ Here is a good practical introduction on the topic: fgiesen.wordpress.com/2012/02/21/… $\endgroup$– Julien GuertaultDec 13, 2017 at 16:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
$\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