/*
   Drawing on actual vector hardware incurs a hidden cost: any movement from one screen
   location to another is as expensive as drawing a line on the screen, so this short
   piece of code collects all the lines that would have been drawn on the fly, and
   sorts them into a drawing order that reduces the amount of movement between lines
   that are not connected to each other.

   This is a greedy algorithm.  A dynamic programming solution would give better results
   but computing the full N*N table of ditances between lines would take longer to compute.

   To slightly optimise this calculation, we can compare the squared distance rather than
   the actual distance that the turned-off beam would move, because the relative ordering
   of distances is preserved when squared (and computing the square root to determine the
   true distance is an unnecessary CPU expense).

   Actually, thinking about the hardware, it's a horizontal deflection being executed at
   the same time as a vertical deflection, so the time taken is going to be proportional
   to only the longer of the two distances, i.e. greater(dx, dy).
*/

// Euclidean distance between two points
static double relative_distance(vertexidx a, vertexidx b) {
    double dx = screen[a].x - screen[b].x, dy = screen[a].y - screen[b].y;
    // return sqrt(dx*dx + dy*dy);
    // return dx*dx + dy*dy;
    return (dx > dy ? dx : dy);
}

// Find the next nearest unused edge (from current point)
static vertexidx find_nearest(Model *m, const vertexidx current, int *reversed) {
  double d, nearest_dist;
  vertexidx nearest_vertex = 0;

  nearest_dist = relative_distance(current, m->edge[0].from); *reversed = 0;
  for (edgeidx e = 0; e < m->max_edges; e++) {
    if (!used[e]) {
      if ((d = relative_distance(current, m->edge[e].from)) < nearest_dist) {
        nearest_dist = d; nearest_vertex = e; *reversed = 0;
      }    
      if ((d = relative_distance(current, m->edge[e].to)) < nearest_dist) {
        nearest_dist = d; nearest_vertex = e; *reversed = 1;
      }
    }
  }
  return nearest_vertex;
}

static void reorder_edges(Model *m, int *order, int *reverse) {
  // 'edge' itself can not be modified so we indirect via an 'order[]' array to reorder.
  int rev;
  edgeidx e, next;
  vertexidx current;

  for (int i = 0; i < m->max_edges; i++) used[i] = FALSE;  // Mark all as unused

  order[0] = reverse[0] = 0; used[0] = TRUE; current = m->edge[0].to;
  for (e = 1; e < m->max_edges; e++) {
    if ((next = find_nearest(m, current, &rev)) < 0) break; // No more edges
    order[e] = next; reverse[e] = rev; used[next] = TRUE;
    current = rev ? m->edge[next].from : m->edge[next].to; // move on to the other end of 'next'.
  }
}