#include <stdint.h>
#include <stdio.h>

typedef struct { int8_t x, y; } Pt;

void output_line_segment(int8_t x1, int8_t y1, int8_t x2, int8_t y2) {
  fprintf(stdout, "line(%d,%d, %d,%d);\n", x1,y1,x2,y2); fflush(stdout);
}

void add_line_segment(int8_t x1, int8_t y1, int8_t x2, int8_t y2, Pt *out, int *pending) {
  if (*pending == 0) {
    out[0] = (Pt){x1, y1}; out[1] = (Pt){x2, y2};
    *pending = 1;
  } else {
    if (out[1].x == x1 && out[1].y == y1) {
      // Extend the previous line segment
      out[1].x = x2; out[1].y = y2;
    } else {
      // Print previous line segment and start a new one.
      output_line_segment(out[0].x, out[0].y, out[1].x, out[1].y);
      out[0] = (Pt){x1, y1}; out[1] = (Pt){x2, y2};
    }
  }
}

/* (x1,y1)-(x2,y2) is first line, (x3,y3)-(x4,y4) is second line.
   All coordinates fit in int8_t. Intersection is rounded to nearest int. */
void intersect(int8_t x1, int8_t y1, int8_t x2, int8_t y2,
               int8_t x3, int8_t y3, int8_t x4, int8_t y4,
               int8_t *x, int8_t *y) {
  int16_t s1_x, s1_y, s2_x, s2_y, s, t;
  s1_x = x2 - x1; s1_y = y2 - y1;
  s2_x = x4 - x3; s2_y = y4 - y3;
  t = (( s2_x * (y1 - y3) - s2_y * (x1 - x3))<<8) / (-s2_x * s1_y + s1_x * s2_y);
  *x = (int8_t)(x1 + ((t * s1_x)>>8) + /* Need consistent rounding!: */ (((t * s1_x)&255) != 0 ? 1 : 0));
  *y = (int8_t)(y1 + ((t * s1_y)>>8));
}

void clip_line_against_horizon(Pt FullA, Pt FullB, const Pt *poly, int n) {
  Pt out[2], A, B, clip, clipLeft, clipRight;
  int pending = 0, i;

  if (FullA.x > FullB.x) {
    fprintf(stderr, "Line not ordered.  Fixing.\n");
    B = FullA; A = FullB; FullA = A; FullB = B;
  }
  
  for (i = 1; i < n; i++) {
    
    clipLeft = poly[i-1];
    if (FullB.x <= clipLeft.x) return; // our line is done.
    clipRight = poly[i];
    if (FullA.x >= clipRight.x) continue; // not yet relevant - look to the next sector...
    A = FullA; B = FullB;

    // Some part of A<->B is in this segment.  Now clip to be within this segment.
    
    if (A.x < clipLeft.x) {
      // truncate line A<->B so A lies on left fence
      intersect(A.x,A.y, B.x,B.y, clipLeft.x,-128, clipLeft.x,127, &clip.x, &clip.y);
      A = clip;
    }
    
    if (clipLeft.x < A.x) {
      intersect(clipLeft.x,clipLeft.y, clipRight.x,clipRight.y, A.x,-128, A.x,127, &clip.x, &clip.y);
      clipLeft = clip;
    }
    
    if (B.x > clipRight.x) {
      // truncate line A<->B so that B lies on right fence
      intersect(A.x,A.y,B.x,B.y, clipRight.x,-128,clipRight.x,127, &clip.x, &clip.y);
      B = clip;
    }
    
    if (B.x < clipRight.x) {
      intersect(clipLeft.x,clipLeft.y,clipRight.x,clipRight.y, B.x,-128,B.x,127, &clip.x, &clip.y);
      clipRight = clip;
    }

    if (A.y >= clipLeft.y && B.y >= clipRight.y) {
      // line segment totally on or above horizon
      add_line_segment(A.x, A.y, B.x, B.y, out, &pending);
    } else if (A.y <= clipLeft.y && B.y <= clipRight.y) {
      // line segment totally below horizon - don't draw
    } else {
      // line crosses horizon
      if (A.y > clipLeft.y) {
        // line goes from above horizon (left) to below horizon (right) - we want the left part:
        intersect(A.x, A.y, B.x, B.y, clipLeft.x, clipLeft.y, clipRight.x, clipRight.y, &clip.x, &clip.y);
        add_line_segment(A.x, A.y, clip.x, clip.y, out, &pending);
      } else if (A.y < clipLeft.y) {
        // line goes from below horizon (left) to above horizon (right) - we want the right part:
        intersect(A.x, A.y, B.x, B.y,  clipLeft.x, clipLeft.y, clipRight.x, clipRight.y, &clip.x, &clip.y);
        add_line_segment(clip.x, clip.y, B.x, B.y, out, &pending);
      } else {
        // can't happen
        fprintf(stderr, "Bug.\n");
      }
    }
  }
  if (pending) {
    output_line_segment(out[0].x, out[0].y, out[1].x, out[1].y);
    pending = 0;
  }
}

int main(int argc, char **argv) {
  #define HORIZON_SEGMENTS 9
  Pt poly[HORIZON_SEGMENTS] = {
    { -128,   0 },
    {  -96, -10 },
    {  -64, -20 },
    {  -32, -10 },
    {    0,   0 },
    {   32,  20 },
    {   64, -15 },
    {   96,  -5 },
    {  127,   0 }
  };
  Pt q0 = { -128,  5 };
  Pt q1 = {  127,  5 };

  Pt c0, c1;
  fprintf(stdout, "// Line is from %d,%d to %d,%d\n", q0.x,q0.y, q1.x,q1.y);
  fprintf(stdout, "// Horizon is %d,%d", poly[0].x, poly[0].y);
  for (int i = 1; i < HORIZON_SEGMENTS; i++) fprintf(stdout, ", %d,%d", poly[i].x, poly[i].y);
  fprintf(stdout, "\n");

  clip_line_against_horizon(q0,q1, poly, HORIZON_SEGMENTS);

  return 0;
}