How do I construct a doubly connected edge list given a set of line segments?
Data structure (conventions consistent with the Wikipedia article):

struct half_edge;

struct vertex {
    struct half_edge *rep;  /* rep-&gt;tail == this */
};

struct face {
    struct half_edge *rep;  /* rep-&gt;left == this */
};

struct half_edge {
    struct half_edge *prev;  /* prev-&gt;next == this */
    struct half_edge *next;  /* next-&gt;prev == this */
    struct half_edge *twin;  /* twin-&gt;twin == this */
    struct vertex *tail;     /* twin-&gt;next-&gt;tail == tail &amp;&amp;
                                prev-&gt;twin-&gt;tail == tail */
    struct face *left;       /* prev-&gt;left == left &amp;&amp; next-&gt;left == left */
};



  Algorithm
  
  
  For each endpoint, create a vertex. 
  For each input segment, create two half-edges, and assign their tail vertices and twins. 
  For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order. 
  For every pair of half-edges e1, e2 in clockwise order, assign e1-&gt;twin-&gt;next = e2 and e2-&gt;prev = e1-&gt;twin. 
  Pick one of the half-edges and assign it as the representative for the endpoint. (Degenerate case: if there's only one half-edge e in the sorted list, set e-&gt;twin-&gt;next = e and e-&gt;prev = e-&gt;twin). The next pointers are a
  permutation on half-edges. 
  For every cycle, allocate and assign a face structure.