util/show-edges.c

   1 #define _GNU_SOURCE
   2 #include <gtk/gtk.h>
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <gdk/gdkkeysyms.h>
   6 #include <math.h>
   7
   8 typedef struct _point {
   9     gdouble x, y;
  10 } point_t;
  11 typedef struct _box {
  12     point_t p1, p2;
  13 } box_t;
  14 typedef struct _line {
  15     point_t p1, p2;
  16 } line_t;
  17 typedef struct _trapezoid {
  18     gdouble top, bottom;
  19     line_t left, right;
  20 } trapezoid_t;
  21 typedef struct _traps {
  22     struct _traps *next, *prev;
  23     box_t extents;
  24     int num_traps;
  25     int size;
  26     trapezoid_t traps[0];
  27 } traps_t;
  28
  29 typedef struct _edge {
  30     line_t line;
  31     gdouble top, bottom;
  32     point_t p1, p2;
  33     int dir;
  34 } edge_t;
  35 typedef struct _edges {
  36     struct _edges *next, *prev;
  37     box_t extents;
  38     int num_edges;
  39     int size;
  40     edge_t edges[0];
  41 } edges_t;
  42
  43 typedef struct _TrapView {
  44     GtkWidget widget;
  45
  46     struct _TrapView *group_head;
  47     struct _TrapView *group_next;
  48     struct _TrapView *group_prev;
  49
  50     traps_t *traps_list;
  51     traps_t *current_traps;
  52
  53     edges_t *edges_list;
  54     edges_t *current_edges;
  55
  56     double px, py;
  57
  58     gint mag_x, mag_y;
  59     gint mag_size;
  60     gdouble mag_zoom;
  61     gboolean in_mag_drag;
  62     gint mag_drag_x, mag_drag_y;
  63 } TrapView;
  64
  65 typedef struct _TrapViewClass {
  66     GtkWidgetClass parent_class;
  67 } TrapViewClass;
  68
  69 G_DEFINE_TYPE (TrapView, trap_view, GTK_TYPE_WIDGET)
  70
  71 static gdouble
  72 _compute_intersection_x_for_y (const line_t *line,
  73                                gdouble y)
  74 {
  75     gdouble dx = line->p2.x - line->p1.x;
  76     gdouble dy = line->p2.y - line->p1.y;
  77     gdouble x;
  78
  79     if (y == line->p1.y)
  80         return line->p1.x;
  81     if (y == line->p2.y)
  82         return line->p2.x;
  83
  84     x = line->p1.x;
  85     if (dy != 0)
  86         x +=  (y - line->p1.y)*dx/dy;
  87     return x;
  88 }
  89
  90 static void
  91 _compute_intersection_point (const line_t *line,
  92                              gdouble y,
  93                              point_t *p)
  94 {
  95     p->x = _compute_intersection_x_for_y (line, p->y = y);
  96 }
  97
  98 static void
  99 trap_view_draw (TrapView *self, cairo_t *cr)
 100 {
 101     traps_t *traps;
 102     edges_t *edges;
 103     gdouble sf_x, sf_y, sf;
 104     gdouble mid, dim;
 105     gdouble x0, x1,  y0, y1;
 106     double dash[2] = {8, 8};
 107     double dots[2] = {0., 1.};
 108     int n;
 109     box_t extents;
 110     point_t p;
 111
 112     cairo_save (cr);
 113     cairo_save (cr);
 114     cairo_set_source_rgb (cr, 1, 1, 1);
 115     cairo_paint (cr);
 116     cairo_restore (cr);
 117
 118     traps = self->current_traps;
 119     edges = self->current_edges;
 120     if (traps == NULL && edges == NULL)
 121         return;
 122
 123     if (traps != NULL) {
 124         extents = traps->extents;
 125         if (edges != NULL) {
 126             if (edges->extents.p1.x < extents.p1.x)
 127                 extents.p1.x = edges->extents.p1.x;
 128             if (edges->extents.p1.y < extents.p1.y)
 129                 extents.p1.y = edges->extents.p1.y;
 130             if (edges->extents.p2.x > extents.p2.x)
 131                 extents.p2.x = edges->extents.p2.x;
 132             if (edges->extents.p2.y > extents.p2.y)
 133                 extents.p2.y = edges->extents.p2.y;
 134         }
 135     } else
 136         extents = edges->extents;
 137
 138     mid = (extents.p2.x + extents.p1.x) / 2.;
 139     dim = (extents.p2.x - extents.p1.x) / 2. * 1.25;
 140     sf_x = self->widget.allocation.width / dim / 2;
 141
 142     mid = (extents.p2.y + extents.p1.y) / 2.;
 143     dim = (extents.p2.y - extents.p1.y) / 2. * 1.25;
 144     sf_y = self->widget.allocation.height / dim / 2;
 145
 146     sf = MIN (sf_x, sf_y);
 147
 148     mid = (extents.p2.x + extents.p1.x) / 2.;
 149     dim = sf_x / sf * (extents.p2.x - extents.p1.x) / 2. * 1.25;
 150     x0 = mid - dim;
 151     x1 = mid + dim;
 152     mid = (extents.p2.y + extents.p1.y) / 2.;
 153     dim = sf_y / sf * (extents.p2.y - extents.p1.y) / 2. * 1.25;
 154     y0 = mid - dim;
 155     y1 = mid + dim;
 156
 157     if (traps != NULL) {
 158         cairo_save (cr);
 159         cairo_scale (cr, sf, sf);
 160         cairo_translate (cr, -x0, -y0);
 161         cairo_set_source_rgba (cr, 0, 1, 0, .2);
 162         for (n = 0; n < traps->num_traps; n++) {
 163             const trapezoid_t *t = &traps->traps[n];
 164
 165             _compute_intersection_point (&t->left, t->top, &p);
 166             cairo_move_to (cr, p.x, p.y);
 167             _compute_intersection_point (&t->right, t->top, &p);
 168             cairo_line_to (cr, p.x, p.y);
 169             _compute_intersection_point (&t->right, t->bottom, &p);
 170             cairo_line_to (cr, p.x, p.y);
 171             _compute_intersection_point (&t->left, t->bottom, &p);
 172             cairo_line_to (cr, p.x, p.y);
 173             cairo_close_path (cr);
 174             cairo_fill (cr);
 175         }
 176         cairo_restore (cr);
 177     }
 178
 179     if (edges == NULL) {
 180         cairo_save (cr);
 181
 182         /* top, bottom */
 183         cairo_save (cr); {
 184             cairo_matrix_t m;
 185             cairo_matrix_init_scale (&m, sf, sf);
 186             cairo_matrix_translate (&m, -x0, -y0);
 187
 188             cairo_set_line_width (cr, 1.);
 189             cairo_set_line_cap (cr, CAIRO_LINE_CAP_BUTT);
 190             for (n = 0; n < traps->num_traps; n++) {
 191                 const trapezoid_t *t = &traps->traps[n];
 192
 193                 _compute_intersection_point (&t->left, t->top, &p);
 194                 cairo_matrix_transform_point (&m, &p.x, &p.y);
 195                 cairo_move_to (cr, floor (p.x), floor (p.y) + .5);
 196                 cairo_set_dash (cr, dash, 2, fmod (floor (p.x), dash[0] + dash[1]));
 197
 198                 _compute_intersection_point (&t->right, t->top, &p);
 199                 cairo_matrix_transform_point (&m, &p.x, &p.y);
 200                 cairo_line_to (cr, ceil (p.x), floor (p.y) + .5);
 201                 cairo_stroke (cr);
 202
 203                 _compute_intersection_point (&t->left, t->bottom, &p);
 204                 cairo_matrix_transform_point (&m, &p.x, &p.y);
 205                 cairo_move_to (cr, floor (p.x), floor (p.y) + .5);
 206                 cairo_set_dash (cr, dash, 2, fmod (floor (p.x), dash[0] + dash[1]));
 207
 208                 _compute_intersection_point (&t->right, t->bottom, &p);
 209                 cairo_matrix_transform_point (&m, &p.x, &p.y);
 210                 cairo_line_to (cr, ceil (p.x), floor (p.y) + .5);
 211                 cairo_stroke (cr);
 212             }
 213         } cairo_restore (cr);
 214
 215         /* left extents */
 216         cairo_save (cr); {
 217             cairo_save (cr); {
 218                 cairo_scale (cr, sf, sf);
 219                 cairo_translate (cr, -x0, -y0);
 220
 221                 for (n = 0; n < traps->num_traps; n++) {
 222                     const trapezoid_t *t = &traps->traps[n];
 223                     cairo_move_to (cr, t->left.p1.x, t->left.p1.y);
 224                     cairo_line_to (cr, t->left.p2.x, t->left.p2.y);
 225                 }
 226             } cairo_restore (cr);
 227             cairo_set_source_rgb (cr, 1, 0, 0);
 228             cairo_set_line_width (cr, 1.);
 229             cairo_set_dash (cr, dash, 2, 0.);
 230             cairo_stroke (cr);
 231         } cairo_restore (cr);
 232
 233         /* left line */
 234         cairo_save (cr); {
 235             cairo_save (cr); {
 236                 cairo_scale (cr, sf, sf);
 237                 cairo_translate (cr, -x0, -y0);
 238
 239                 for (n = 0; n < traps->num_traps; n++) {
 240                     const trapezoid_t *t = &traps->traps[n];
 241                     _compute_intersection_point (&t->left, t->top, &p);
 242                     cairo_move_to (cr, p.x, p.y);
 243                     _compute_intersection_point (&t->left, t->bottom, &p);
 244                     cairo_line_to (cr, p.x, p.y);
 245                 }
 246             } cairo_restore (cr);
 247             cairo_set_source_rgb (cr, 1, 0, 0);
 248             cairo_stroke (cr);
 249         } cairo_restore (cr);
 250
 251         /* right extents */
 252         cairo_save (cr); {
 253             cairo_save (cr); {
 254                 cairo_scale (cr, sf, sf);
 255                 cairo_translate (cr, -x0, -y0);
 256
 257                 for (n = 0; n < traps->num_traps; n++) {
 258                     const trapezoid_t *t = &traps->traps[n];
 259                     cairo_move_to (cr, t->right.p1.x, t->right.p1.y);
 260                     cairo_line_to (cr, t->right.p2.x, t->right.p2.y);
 261                 }
 262             } cairo_restore (cr);
 263             cairo_set_source_rgb (cr, 0, 0, 1);
 264             cairo_set_line_width (cr, 1.);
 265             cairo_set_dash (cr, dash, 2, 0.);
 266             cairo_stroke (cr);
 267         } cairo_restore (cr);
 268
 269         /* right line */
 270         cairo_save (cr); {
 271             cairo_save (cr); {
 272                 cairo_scale (cr, sf, sf);
 273                 cairo_translate (cr, -x0, -y0);
 274
 275                 for (n = 0; n < traps->num_traps; n++) {
 276                     const trapezoid_t *t = &traps->traps[n];
 277                     _compute_intersection_point (&t->right, t->top, &p);
 278                     cairo_move_to (cr, p.x, p.y);
 279                     _compute_intersection_point (&t->right, t->bottom, &p);
 280                     cairo_line_to (cr, p.x, p.y);
 281                 } cairo_restore (cr);
 282                 cairo_set_source_rgb (cr, 0, 0, 1);
 283                 cairo_stroke (cr);
 284             } cairo_restore (cr);
 285         }
 286
 287         /* end-points */
 288         cairo_save (cr); {
 289             cairo_save (cr); {
 290                 cairo_scale (cr, sf, sf);
 291                 cairo_translate (cr, -x0, -y0);
 292
 293                 for (n = 0; n < traps->num_traps; n++) {
 294                     const trapezoid_t *t = &traps->traps[n];
 295                     _compute_intersection_point (&t->left, t->top, &p);
 296                     cairo_move_to (cr, p.x, p.y);
 297                     cairo_close_path (cr);
 298                     _compute_intersection_point (&t->left, t->bottom, &p);
 299                     cairo_move_to (cr, p.x, p.y);
 300                     cairo_close_path (cr);
 301                     _compute_intersection_point (&t->right, t->top, &p);
 302                     cairo_move_to (cr, p.x, p.y);
 303                     cairo_close_path (cr);
 304                     _compute_intersection_point (&t->right, t->bottom, &p);
 305                     cairo_move_to (cr, p.x, p.y);
 306                     cairo_close_path (cr);
 307                 }
 308             } cairo_restore (cr);
 309             cairo_set_source_rgb (cr, 0, 0, 0);
 310             cairo_set_dash (cr, dots, 2, 0.);
 311             cairo_set_line_cap (cr, CAIRO_LINE_CAP_ROUND);
 312             cairo_set_line_width (cr, 4.);
 313             cairo_stroke (cr);
 314         } cairo_restore (cr);
 315
 316         cairo_restore (cr);
 317     } else {
 318         cairo_save (cr);
 319
 320         for (n = 0; n < edges->num_edges; n++) {
 321             const edge_t *e = &edges->edges[n];
 322
 323             cairo_save (cr); {
 324                 cairo_scale (cr, sf, sf);
 325                 cairo_translate (cr, -x0, -y0);
 326                 cairo_move_to (cr, e->p1.x, e->p1.y);
 327                 cairo_line_to (cr, e->p2.x, e->p2.y);
 328             } cairo_restore (cr);
 329
 330             if (e->dir < 0) {
 331                 cairo_set_source_rgb (cr, 0, 0, 1);
 332                 cairo_set_dash (cr, dash, 2, dash[0]);
 333             } else {
 334                 cairo_set_source_rgb (cr, 1, 0, 0);
 335                 cairo_set_dash (cr, dash, 2, 0.);
 336             }
 337
 338             cairo_set_line_cap (cr, CAIRO_LINE_CAP_BUTT);
 339             cairo_set_line_width (cr, 1.);
 340             cairo_stroke (cr);
 341
 342             cairo_save (cr); {
 343                 cairo_scale (cr, sf, sf);
 344                 cairo_translate (cr, -x0, -y0);
 345                 cairo_move_to (cr, e->p1.x, e->p1.y);
 346                 cairo_close_path (cr);
 347                 cairo_move_to (cr, e->p2.x, e->p2.y);
 348                 cairo_close_path (cr);
 349             } cairo_restore (cr);
 350             cairo_set_source_rgb (cr, 0, 0, 0);
 351             cairo_set_dash (cr, dots, 2, 0.);
 352             cairo_set_line_cap (cr, CAIRO_LINE_CAP_ROUND);
 353             cairo_set_line_width (cr, 4.);
 354             cairo_stroke (cr);
 355         }
 356
 357         cairo_restore (cr);
 358     }
 359
 360     /* draw a zoom view of the area around the mouse */
 361     {
 362         cairo_save (cr);
 363         double zoom = self->mag_zoom;
 364         int size = self->mag_size;
 365
 366         /* bottom right */
 367         cairo_rectangle (cr, self->mag_x, self->mag_y, size, size);
 368         cairo_stroke_preserve (cr);
 369         cairo_set_source_rgb (cr, 1, 1, 1);
 370         cairo_fill_preserve (cr);
 371         cairo_clip (cr);
 372
 373         /* compute roi in extents */
 374         cairo_translate (cr, self->mag_x + size/2, self->mag_y + size/2);
 375
 376         if (traps != NULL) {
 377             cairo_save (cr);
 378             cairo_scale (cr, zoom, zoom);
 379             cairo_translate (cr, -(self->px / sf + x0), -(self->py /sf + y0));
 380             for (n = 0; n < traps->num_traps; n++) {
 381                 const trapezoid_t *t = &traps->traps[n];
 382
 383                 _compute_intersection_point (&t->left, t->top, &p);
 384                 cairo_move_to (cr, p.x, p.y);
 385                 _compute_intersection_point (&t->right, t->top, &p);
 386                 cairo_line_to (cr, p.x, p.y);
 387                 _compute_intersection_point (&t->right, t->bottom, &p);
 388                 cairo_line_to (cr, p.x, p.y);
 389                 _compute_intersection_point (&t->left, t->bottom, &p);
 390                 cairo_line_to (cr, p.x, p.y);
 391                 cairo_close_path (cr);
 392                 cairo_set_source_rgba (cr, 0, 1, 0, .2);
 393                 cairo_fill (cr);
 394             }
 395             cairo_restore (cr);
 396         }
 397
 398         if (edges == NULL) {
 399             cairo_save (cr); {
 400                 cairo_matrix_t m;
 401                 cairo_matrix_init_scale (&m, zoom, zoom);
 402                 cairo_matrix_translate (&m, -(self->px / sf + x0), -(self->py /sf + y0));
 403
 404                 cairo_set_source_rgb (cr, 0, 0, 0);
 405                 cairo_set_line_width (cr, 1.);
 406                 cairo_set_line_cap (cr, CAIRO_LINE_CAP_BUTT);
 407                 for (n = 0; n < traps->num_traps; n++) {
 408                     const trapezoid_t *t = &traps->traps[n];
 409
 410                     _compute_intersection_point (&t->left, t->top, &p);
 411                     cairo_matrix_transform_point (&m, &p.x, &p.y);
 412                     cairo_move_to (cr, floor (p.x), floor (p.y) + .5);
 413                     cairo_set_dash (cr, dash, 2, fmod (floor (p.x), dash[0] + dash[1]));
 414
 415                     _compute_intersection_point (&t->right, t->top, &p);
 416                     cairo_matrix_transform_point (&m, &p.x, &p.y);
 417                     cairo_line_to (cr, ceil (p.x), floor (p.y) + .5);
 418                     cairo_stroke (cr);
 419
 420                     _compute_intersection_point (&t->left, t->bottom, &p);
 421                     cairo_matrix_transform_point (&m, &p.x, &p.y);
 422                     cairo_move_to (cr, floor (p.x), floor (p.y) + .5);
 423                     cairo_set_dash (cr, dash, 2, fmod (floor (p.x), dash[0] + dash[1]));
 424
 425                     _compute_intersection_point (&t->right, t->bottom, &p);
 426                     cairo_matrix_transform_point (&m, &p.x, &p.y);
 427                     cairo_line_to (cr, ceil (p.x), floor (p.y) + .5);
 428                     cairo_stroke (cr);
 429                 }
 430             } cairo_restore (cr);
 431
 432             cairo_save (cr); { /* left extents */
 433                 cairo_save (cr); {
 434                     cairo_scale (cr, zoom, zoom);
 435                     cairo_translate (cr, -(self->px / sf + x0), -(self->py /sf + y0));
 436                     for (n = 0; n < traps->num_traps; n++) {
 437                         const trapezoid_t *t = &traps->traps[n];
 438                         cairo_move_to (cr, t->left.p1.x, t->left.p1.y);
 439                         cairo_line_to (cr, t->left.p2.x, t->left.p2.y);
 440                     }
 441                 } cairo_restore (cr);
 442                 cairo_set_source_rgb (cr, 1, 0, 0);
 443                 cairo_set_line_width (cr, .5);
 444                 cairo_set_dash (cr, dash, 2, 0.);
 445                 cairo_stroke (cr);
 446             } cairo_restore (cr);
 447             cairo_save (cr); { /* right extents */
 448                 cairo_save (cr); {
 449                     cairo_scale (cr, zoom, zoom);
 450                     cairo_translate (cr, -(self->px / sf + x0), -(self->py /sf + y0));
 451
 452                     for (n = 0; n < traps->num_traps; n++) {
 453                         const trapezoid_t *t = &traps->traps[n];
 454                         cairo_move_to (cr, t->right.p1.x, t->right.p1.y);
 455                         cairo_line_to (cr, t->right.p2.x, t->right.p2.y);
 456                     }
 457                 } cairo_restore (cr);
 458                 cairo_set_source_rgb (cr, 0, 0, 1);
 459                 cairo_set_line_width (cr, .5);
 460                 cairo_set_dash (cr, dash, 2, 0.);
 461                 cairo_stroke (cr);
 462             } cairo_restore (cr);
 463
 464             cairo_save (cr); { /* left lines */
 465                 cairo_save (cr);
 466                 cairo_scale (cr, zoom, zoom);
 467                 cairo_translate (cr, -(self->px / sf + x0), -(self->py /sf + y0));
 468                 for (n = 0; n < traps->num_traps; n++) {
 469                     const trapezoid_t *t = &traps->traps[n];
 470                     _compute_intersection_point (&t->left, t->top, &p);
 471                     cairo_move_to (cr, p.x, p.y);
 472                     _compute_intersection_point (&t->left, t->bottom, &p);
 473                     cairo_line_to (cr, p.x, p.y);
 474                 }
 475                 cairo_restore (cr);
 476                 cairo_set_source_rgb (cr, 1, 0, 0);
 477                 cairo_stroke (cr);
 478             } cairo_restore (cr);
 479             cairo_save (cr); { /* right lines */
 480                 cairo_save (cr);
 481                 cairo_scale (cr, zoom, zoom);
 482                 cairo_translate (cr, -(self->px / sf + x0), -(self->py /sf + y0));
 483                 for (n = 0; n < traps->num_traps; n++) {
 484                     const trapezoid_t *t = &traps->traps[n];
 485                     _compute_intersection_point (&t->right, t->top, &p);
 486                     cairo_move_to (cr, p.x, p.y);
 487                     _compute_intersection_point (&t->right, t->bottom, &p);
 488                     cairo_line_to (cr, p.x, p.y);
 489                 }
 490                 cairo_restore (cr);
 491                 cairo_set_source_rgb (cr, 0, 0, 1);
 492                 cairo_stroke (cr);
 493             } cairo_restore (cr);
 494
 495             /* end-points */
 496             cairo_save (cr); {
 497                 double dots[2] = {0., 1.};
 498
 499                 cairo_save (cr);
 500                 cairo_scale (cr, zoom, zoom);
 501                 cairo_translate (cr, -(self->px / sf + x0), -(self->py /sf + y0));
 502                 for (n = 0; n < traps->num_traps; n++) {
 503                     const trapezoid_t *t = &traps->traps[n];
 504                     _compute_intersection_point (&t->left, t->top, &p);
 505                     cairo_move_to (cr, p.x, p.y);
 506                     cairo_close_path (cr);
 507                     _compute_intersection_point (&t->left, t->bottom, &p);
 508                     cairo_move_to (cr, p.x, p.y);
 509                     cairo_close_path (cr);
 510                     _compute_intersection_point (&t->right, t->top, &p);
 511                     cairo_move_to (cr, p.x, p.y);
 512                     cairo_close_path (cr);
 513                     _compute_intersection_point (&t->right, t->bottom, &p);
 514                     cairo_move_to (cr, p.x, p.y);
 515                     cairo_close_path (cr);
 516                 }
 517                 cairo_restore (cr);
 518                 cairo_set_source_rgb (cr, 0, 0, 0);
 519                 cairo_set_dash (cr, dots, 2, 0.);
 520                 cairo_set_line_cap (cr, CAIRO_LINE_CAP_ROUND);
 521                 cairo_set_line_width (cr, 4.);
 522                 cairo_stroke (cr);
 523             } cairo_restore (cr);
 524         } else {
 525             cairo_save (cr);
 526
 527             for (n = 0; n < edges->num_edges; n++) {
 528                 const edge_t *e = &edges->edges[n];
 529
 530                 cairo_save (cr); {
 531                     cairo_scale (cr, zoom, zoom);
 532                     cairo_translate (cr, -(self->px / sf + x0), -(self->py /sf + y0));
 533                     cairo_move_to (cr, e->p1.x, e->p1.y);
 534                     cairo_line_to (cr, e->p2.x, e->p2.y);
 535                 } cairo_restore (cr);
 536
 537                 if (e->dir < 0) {
 538                     cairo_set_source_rgb (cr, 0, 0, 1);
 539                     cairo_set_dash (cr, dash, 2, dash[0]);
 540                 } else {
 541                     cairo_set_source_rgb (cr, 1, 0, 0);
 542                     cairo_set_dash (cr, dash, 2, 0.);
 543                 }
 544
 545                 cairo_set_line_cap (cr, CAIRO_LINE_CAP_BUTT);
 546                 cairo_set_line_width (cr, 1.);
 547                 cairo_stroke (cr);
 548
 549                 cairo_save (cr); {
 550                     cairo_scale (cr, zoom, zoom);
 551                     cairo_translate (cr, -(self->px / sf + x0), -(self->py /sf + y0));
 552                     cairo_move_to (cr, e->p1.x, e->p1.y);
 553                     cairo_close_path (cr);
 554                     cairo_move_to (cr, e->p2.x, e->p2.y);
 555                     cairo_close_path (cr);
 556                 } cairo_restore (cr);
 557                 cairo_set_source_rgb (cr, 0, 0, 0);
 558                 cairo_set_dash (cr, dots, 2, 0.);
 559                 cairo_set_line_cap (cr, CAIRO_LINE_CAP_ROUND);
 560                 cairo_set_line_width (cr, 4.);
 561                 cairo_stroke (cr);
 562             }
 563
 564             cairo_restore (cr);
 565         }
 566
 567         /* grid */
 568         cairo_save (cr); {
 569             int i;
 570
 571             cairo_translate (cr,
 572                              -zoom*fmod (self->px/sf + x0, 1.),
 573                              -zoom*fmod (self->py/sf + y0, 1.));
 574             for (i = -size/2/zoom - 1; i <= size/2/zoom + 1; i++) {
 575                 cairo_move_to (cr, zoom*i, -size/2);
 576                 cairo_line_to (cr, zoom*i, size/2 + zoom);
 577                 cairo_move_to (cr, -size/2, zoom*i);
 578                 cairo_line_to (cr, size/2 + zoom, zoom*i);
 579             }
 580             cairo_set_source_rgba (cr, .7, .7, .7, .5);
 581             cairo_set_line_width (cr, 1.);
 582             cairo_stroke (cr);
 583         } cairo_restore (cr);
 584     }
 585
 586     cairo_restore (cr);
 587 }
 588
 589
 590 static gdouble
 591 edge_length (const edge_t *e)
 592 {
 593     return hypot (e->p2.x - e->p1.x, e->p2.y - e->p1.y);
 594 }
 595
 596 static gdouble
 597 edges_compute_total_length (const edges_t *edges)
 598 {
 599     int n;
 600     gdouble len = 0.;
 601     for (n = 0; n < edges->num_edges; n++)
 602         len += edge_length (&edges->edges[n]);
 603     return len;
 604 }
 605
 606 static gdouble
 607 trapezoid_area (const trapezoid_t *t)
 608 {
 609     gdouble inner_left, inner_right;
 610     gdouble outer_left, outer_right;
 611     gdouble height;
 612     gdouble area;
 613
 614     /* split into 3 sections: a rectangle with a pair of triangular bookends */
 615     inner_left = _compute_intersection_x_for_y (&t->left, t->top);
 616     outer_left = _compute_intersection_x_for_y (&t->left, t->bottom);
 617     if (outer_left > inner_left) {
 618         gdouble t = outer_left;
 619         outer_left = inner_left;
 620         inner_left = t;
 621     }
 622
 623     inner_right = _compute_intersection_x_for_y (&t->right, t->top);
 624     outer_right = _compute_intersection_x_for_y (&t->right, t->bottom);
 625     if (outer_right > inner_right) {
 626         gdouble t = outer_right;
 627         outer_right = inner_right;
 628         inner_right = t;
 629     }
 630
 631     if (outer_left > outer_right) { /* reverse */
 632         gdouble t;
 633
 634         t = outer_left;
 635         outer_left = inner_right;
 636         inner_right = t;
 637
 638         t = inner_left;
 639         inner_left = outer_right;
 640         outer_right = t;
 641     }
 642
 643     height = t->bottom - t->top;
 644     area  = (inner_left - outer_left) * height / 2;
 645     area += (outer_right - inner_right) * height / 2;
 646     area += (inner_right - inner_left) * height;
 647
 648     return area;
 649 }
 650
 651 static gdouble
 652 traps_compute_total_area (const traps_t *traps)
 653 {
 654     int n;
 655     gdouble area = 0.;
 656     for (n = 0; n < traps->num_traps; n++)
 657         area += trapezoid_area (&traps->traps[n]);
 658     return area;
 659 }
 660
 661 static void
 662 trap_view_draw_labels (TrapView *self, cairo_t *cr)
 663 {
 664     PangoLayout *layout;
 665     gint width, height;
 666     GString *string;
 667     gchar *str;
 668     traps_t *traps;
 669     edges_t *edges;
 670
 671     string = g_string_new (NULL);
 672
 673     traps = self->current_traps;
 674     if (traps != NULL) {
 675         /* convert total area from fixed-point (assuming 24.8) */
 676         gdouble total_area = traps_compute_total_area (traps) / (256. * 256.);
 677         g_string_append_printf (string,
 678                                 "Number of trapezoids:\t%d\n"
 679                                 "Total area of trapezoids:\t%.2f\n",
 680                                 traps->num_traps,
 681                                 total_area);
 682     }
 683
 684     edges = self->current_edges;
 685     if (edges != NULL) {
 686         double total_length = edges_compute_total_length (edges) / 256.;
 687         g_string_append_printf (string,
 688                                 "Number of edges:\t%d\n"
 689                                 "Total length of edges: \t%.2f\n",
 690                                 edges->num_edges,
 691                                 total_length);
 692     }
 693
 694     str = g_string_free (string, FALSE);
 695     layout = gtk_widget_create_pango_layout (&self->widget, str);
 696     g_free (str);
 697
 698     pango_layout_get_pixel_size (layout, &width, &height);
 699
 700     cairo_move_to (cr, 10, 40);
 701     pango_cairo_show_layout (cr, layout);
 702     g_object_unref (layout);
 703 }
 704
 705 static gboolean
 706 trap_view_expose (GtkWidget *w, GdkEventExpose *ev)
 707 {
 708     TrapView *self = (TrapView *) w;
 709     cairo_t *cr;
 710
 711     cr = gdk_cairo_create (w->window);
 712     gdk_cairo_region (cr, ev->region);
 713     cairo_clip (cr);
 714
 715     trap_view_draw (self, cr);
 716     trap_view_draw_labels (self, cr);
 717
 718     cairo_destroy (cr);
 719     return FALSE;
 720 }
 721
 722 static void
 723 trap_view_advance (TrapView *self)
 724 {
 725     if (self->current_traps && self->current_traps->prev)
 726         self->current_traps = self->current_traps->prev;
 727     if (self->current_edges && self->current_edges->prev)
 728         self->current_edges = self->current_edges->prev;
 729     gtk_widget_queue_draw (&self->widget);
 730 }
 731
 732 static void
 733 trap_view_back (TrapView *self)
 734 {
 735     if (self->current_traps && self->current_traps->next)
 736         self->current_traps = self->current_traps->next;
 737     if (self->current_edges && self->current_edges->next)
 738         self->current_edges = self->current_edges->next;
 739     gtk_widget_queue_draw (&self->widget);
 740 }
 741
 742 static void
 743 trap_view_group_foreach (TrapView *group, GFunc func, gpointer data)
 744 {
 745     while (group) {
 746         func (group, data);
 747         group = group->group_next;
 748     }
 749 }
 750
 751 static gboolean
 752 trap_view_key_press (GtkWidget *w, GdkEventKey *ev)
 753 {
 754     TrapView *self = (TrapView *) w;
 755
 756     switch (ev->keyval) {
 757     case GDK_BackSpace:
 758         trap_view_group_foreach (self->group_head,
 759                                  (GFunc) trap_view_back,
 760                                  NULL);
 761         break;
 762
 763     case GDK_space:
 764         trap_view_group_foreach (self->group_head,
 765                                  (GFunc) trap_view_advance,
 766                                  NULL);
 767         break;
 768
 769     case GDK_Return:
 770         trap_view_group_foreach (self->group_head,
 771                                  (GFunc) trap_view_advance,
 772                                  NULL);
 773         break;
 774
 775     case GDK_Escape:
 776     case GDK_Q:
 777         gtk_main_quit ();
 778         break;
 779     }
 780
 781     return FALSE;
 782 }
 783
 784 static gboolean
 785 trap_view_button_press (GtkWidget *w, GdkEventButton *ev)
 786 {
 787     TrapView *self = (TrapView *) w;
 788
 789     if (ev->x < self->mag_x ||
 790         ev->y < self->mag_y ||
 791         ev->x > self->mag_x + self->mag_size ||
 792         ev->y > self->mag_y + self->mag_size)
 793     {
 794         if (ev->type == GDK_BUTTON_PRESS) {
 795             if (self->current_traps == NULL)
 796                 return FALSE;
 797
 798             if (ev->button == 1) {
 799                 trap_view_group_foreach (self->group_head,
 800                                          (GFunc) trap_view_advance,
 801                                          NULL);
 802             } else if (ev->button == 3) {
 803                 trap_view_group_foreach (self->group_head,
 804                                          (GFunc) trap_view_back,
 805                                          NULL);
 806             }
 807         }
 808     }
 809     else
 810     {
 811         self->in_mag_drag = TRUE;
 812         self->mag_drag_x = ev->x;
 813         self->mag_drag_y = ev->y;
 814     }
 815
 816     return FALSE;
 817 }
 818
 819 static gboolean
 820 trap_view_button_release (GtkWidget *w, GdkEventButton *ev)
 821 {
 822     TrapView *self = (TrapView *) w;
 823
 824     self->in_mag_drag = FALSE;
 825
 826     return FALSE;
 827 }
 828
 829 static void
 830 trap_view_update_mouse (TrapView *self, GdkEventMotion *ev)
 831 {
 832     self->px = ev->x;
 833     self->py = ev->y;
 834
 835     gtk_widget_queue_draw (&self->widget);
 836 }
 837
 838 static void
 839 trap_view_update_magnifier (TrapView *self, gint *xy)
 840 {
 841     self->mag_x = xy[0];
 842     self->mag_y = xy[1];
 843
 844     gtk_widget_queue_draw (&self->widget);
 845 }
 846
 847 static gboolean
 848 trap_view_motion (GtkWidget *w, GdkEventMotion *ev)
 849 {
 850     TrapView *self = (TrapView *) w;
 851
 852     if (self->in_mag_drag) {
 853         int xy[2];
 854
 855         xy[0] = self->mag_x + ev->x - self->mag_drag_x;
 856         xy[1] = self->mag_y + ev->y - self->mag_drag_y;
 857
 858         trap_view_group_foreach (self->group_head,
 859                                  (GFunc) trap_view_update_magnifier,
 860                                  xy);
 861
 862         self->mag_drag_x = ev->x;
 863         self->mag_drag_y = ev->y;
 864     } else if (ev->x < self->mag_x ||
 865                ev->y < self->mag_y ||
 866                ev->x > self->mag_x + self->mag_size ||
 867                ev->y > self->mag_y + self->mag_size)
 868     {
 869         trap_view_group_foreach (self->group_head,
 870                                  (GFunc) trap_view_update_mouse,
 871                                  ev);
 872     }
 873
 874     return FALSE;
 875 }
 876
 877 static void
 878 trap_view_realize (GtkWidget *widget)
 879 {
 880     GdkWindowAttr attributes;
 881
 882     GTK_WIDGET_SET_FLAGS (widget, GTK_REALIZED);
 883
 884     attributes.window_type = GDK_WINDOW_CHILD;
 885     attributes.x = widget->allocation.x;
 886     attributes.y = widget->allocation.y;
 887     attributes.width  = widget->allocation.width;
 888     attributes.height = widget->allocation.height;
 889     attributes.wclass = GDK_INPUT_OUTPUT;
 890     attributes.visual = gtk_widget_get_visual (widget);
 891     attributes.colormap = gtk_widget_get_colormap (widget);
 892     attributes.event_mask = gtk_widget_get_events (widget) |
 893                             GDK_BUTTON_PRESS_MASK |
 894                             GDK_BUTTON_RELEASE_MASK |
 895                             GDK_KEY_PRESS_MASK |
 896                             GDK_KEY_RELEASE_MASK |
 897                             GDK_POINTER_MOTION_MASK |
 898                             GDK_BUTTON_MOTION_MASK |
 899                             GDK_EXPOSURE_MASK;
 900
 901     widget->window = gdk_window_new (gtk_widget_get_parent_window (widget),
 902                                      &attributes,
 903                                      GDK_WA_X | GDK_WA_Y |
 904                                      GDK_WA_VISUAL | GDK_WA_COLORMAP);
 905     gdk_window_set_user_data (widget->window, widget);
 906
 907     widget->style = gtk_style_attach (widget->style, widget->window);
 908     gtk_style_set_background (widget->style, widget->window, GTK_STATE_NORMAL);
 909 }
 910
 911 static void
 912 trap_view_size_allocate (GtkWidget *w, GdkRectangle *r)
 913 {
 914     TrapView *self = (TrapView *) w;
 915
 916     GTK_WIDGET_CLASS (trap_view_parent_class)->size_allocate (w, r);
 917
 918     self->mag_x = w->allocation.width - self->mag_size - 10;
 919     self->mag_y = w->allocation.height - self->mag_size - 10;
 920 }
 921
 922 static void
 923 trap_view_finalize (GObject *obj)
 924 {
 925     G_OBJECT_CLASS (trap_view_parent_class)->finalize (obj);
 926 }
 927
 928 static void
 929 trap_view_class_init (TrapViewClass *klass)
 930 {
 931     GObjectClass *object_class = (GObjectClass *) klass;
 932     GtkWidgetClass *widget_class = (GtkWidgetClass *) klass;
 933
 934     object_class->finalize = trap_view_finalize;
 935
 936     widget_class->realize = trap_view_realize;
 937     widget_class->size_allocate = trap_view_size_allocate;
 938     widget_class->expose_event = trap_view_expose;
 939     widget_class->key_press_event = trap_view_key_press;
 940     widget_class->button_press_event = trap_view_button_press;
 941     widget_class->button_release_event = trap_view_button_release;
 942     widget_class->motion_notify_event = trap_view_motion;
 943 }
 944
 945 static void
 946 trap_view_init (TrapView *self)
 947 {
 948     self->mag_zoom = 10;
 949     self->mag_size = 200;
 950
 951     GTK_WIDGET_SET_FLAGS (self, GTK_CAN_FOCUS);
 952 }
 953
 954 static traps_t *
 955 _traps_add_trapezoid (TrapView *tv, traps_t *traps, const trapezoid_t *trap)
 956 {
 957     if (trap->top < traps->extents.p1.y)
 958         traps->extents.p1.y = trap->top;
 959     if (trap->bottom > traps->extents.p2.y)
 960         traps->extents.p2.y = trap->bottom;
 961
 962     if (trap->left.p1.x < traps->extents.p1.x)
 963         traps->extents.p1.x = trap->left.p1.x;
 964     if (trap->left.p2.x < traps->extents.p1.x)
 965         traps->extents.p1.x = trap->left.p2.x;
 966
 967     if (trap->right.p1.x > traps->extents.p2.x)
 968         traps->extents.p2.x = trap->right.p1.x;
 969     if (trap->right.p2.x > traps->extents.p2.x)
 970         traps->extents.p2.x = trap->right.p2.x;
 971
 972     if (traps->num_traps == traps->size) {
 973         int newsize = 2 * traps->size;
 974         void *newtraps;
 975
 976         newtraps = g_realloc (traps,
 977                               sizeof (traps_t) + newsize * sizeof (trapezoid_t));
 978         if (newtraps == NULL)
 979             return traps;
 980
 981         if (tv->current_traps == traps)
 982             tv->current_traps = newtraps;
 983
 984         traps = newtraps;
 985         traps->size = newsize;
 986
 987         if (traps->next != NULL)
 988             traps->next->prev = newtraps;
 989         if (traps->prev != NULL)
 990             traps->prev->next = newtraps;
 991         else
 992             tv->traps_list = newtraps;
 993     }
 994
 995     traps->traps[traps->num_traps++] = *trap;
 996
 997     return traps;
 998 }
 999
1000 static traps_t *
1001 traps_new (TrapView *tv)
1002 {
1003     traps_t *t;
1004
1005     t = g_malloc (sizeof (traps_t) + 16 * sizeof (trapezoid_t));
1006     t->prev = NULL;
1007     t->next = tv->traps_list;
1008     if (tv->traps_list)
1009         tv->traps_list->prev = t;
1010     tv->traps_list = t;
1011
1012     if (tv->current_traps == NULL)
1013         tv->current_traps = t;
1014
1015     t->size = 16;
1016     t->num_traps = 0;
1017     t->extents.p1.x = G_MAXDOUBLE;
1018     t->extents.p1.y = G_MAXDOUBLE;
1019     t->extents.p2.x = -G_MAXDOUBLE;
1020     t->extents.p2.y = -G_MAXDOUBLE;
1021
1022     return t;
1023 }
1024
1025 static edges_t *
1026 _edges_add_edge (TrapView *tv, edges_t *edges, edge_t *e)
1027 {
1028     if (e->top < edges->extents.p1.y)
1029         edges->extents.p1.y = e->top;
1030     if (e->bottom > edges->extents.p2.y)
1031         edges->extents.p2.y = e->bottom;
1032
1033     _compute_intersection_point (&e->line, e->top, &e->p1);
1034     _compute_intersection_point (&e->line, e->bottom, &e->p2);
1035
1036     if (e->p1.x < edges->extents.p1.x)
1037         edges->extents.p1.x = e->p1.x;
1038     if (e->p2.x < edges->extents.p1.x)
1039         edges->extents.p1.x = e->p2.x;
1040
1041     if (e->p1.x > edges->extents.p2.x)
1042         edges->extents.p2.x = e->p1.x;
1043     if (e->p2.x > edges->extents.p2.x)
1044         edges->extents.p2.x = e->p2.x;
1045
1046     if (edges->num_edges == edges->size) {
1047         int newsize = 2 * edges->size;
1048         void *newedges;
1049
1050         newedges = g_realloc (edges,
1051                               sizeof (edges_t) + newsize * sizeof (edge_t));
1052         if (newedges == NULL)
1053             return edges;
1054
1055         if (tv->current_edges == edges)
1056             tv->current_edges = newedges;
1057
1058         edges = newedges;
1059         edges->size = newsize;
1060
1061         if (edges->next != NULL)
1062             edges->next->prev = newedges;
1063         if (edges->prev != NULL)
1064             edges->prev->next = newedges;
1065         else
1066             tv->edges_list = newedges;
1067     }
1068
1069     edges->edges[edges->num_edges++] = *e;
1070
1071     return edges;
1072 }
1073
1074 static edges_t *
1075 edges_new (TrapView *tv)
1076 {
1077     edges_t *t;
1078
1079     t = g_malloc (sizeof (edges_t) + 16 * sizeof (edge_t));
1080     t->prev = NULL;
1081     t->next = tv->edges_list;
1082     if (tv->edges_list)
1083         tv->edges_list->prev = t;
1084     tv->edges_list = t;
1085
1086     if (tv->current_edges == NULL)
1087         tv->current_edges = t;
1088
1089     t->size = 16;
1090     t->num_edges = 0;
1091     t->extents.p1.x = G_MAXDOUBLE;
1092     t->extents.p1.y = G_MAXDOUBLE;
1093     t->extents.p2.x = -G_MAXDOUBLE;
1094     t->extents.p2.y = -G_MAXDOUBLE;
1095
1096     return t;
1097 }
1098
1099 int
1100 main (int argc, char **argv)
1101 {
1102     TrapView *tv, *tv2, *group_head = NULL, *group_prev = NULL;
1103     traps_t *traps;
1104     edges_t *edges;
1105     GtkWidget *window, *hbox;
1106     FILE *file;
1107     char *line = NULL;
1108     size_t len = 0;
1109
1110     gtk_init (&argc, &argv);
1111
1112     hbox = gtk_hbox_new (TRUE, 0);
1113
1114     tv = g_object_new (trap_view_get_type (), NULL);
1115     gtk_box_pack_start (GTK_BOX (hbox), &tv->widget, TRUE, TRUE, 0);
1116     gtk_widget_show (&tv->widget);
1117
1118     tv->group_prev = group_prev;
1119     tv->group_next = NULL;
1120     if (group_prev)
1121         group_prev->group_next = tv;
1122     group_prev = tv;
1123     if (group_head == NULL)
1124         group_head = tv;
1125     tv->group_head = group_head;
1126
1127     file = fopen (argv[1], "r");
1128     if (file != NULL) {
1129         edges = edges_new (tv);
1130         while (getline (&line, &len, file) != -1) {
1131             edge_t e;
1132
1133             if (sscanf (line,
1134                         "(%lf, %lf), (%lf, %lf) %lf %lf %d",
1135                         &e.line.p1.x, &e.line.p1.y,
1136                         &e.line.p2.x, &e.line.p2.y,
1137                         &e.top, &e.bottom,
1138                         &e.dir) == 7) {
1139                 edges = _edges_add_edge (tv, edges, &e);
1140             } else {
1141                 if (edges->num_edges) {
1142                     g_print ("read %d edges\n", edges->num_edges);
1143                     g_print ("extents=(%lg, %lg), (%lg, %lg)\n",
1144                              edges->extents.p1.x, edges->extents.p1.y,
1145                              edges->extents.p2.x, edges->extents.p2.y);
1146                     edges = edges_new (tv);
1147                 }
1148             }
1149         }
1150
1151         if (edges->num_edges) {
1152             g_print ("read %d edges\n", edges->num_edges);
1153             g_print ("extents=(%lg, %lg), (%lg, %lg)\n",
1154                      edges->extents.p1.x, edges->extents.p1.y,
1155                      edges->extents.p2.x, edges->extents.p2.y);
1156         }
1157
1158         fclose (file);
1159     }
1160
1161     file = fopen (argv[2], "r");
1162     if (file != NULL) {
1163         traps = traps_new (tv);
1164         while (getline (&line, &len, file) != -1) {
1165             trapezoid_t t;
1166
1167             if (sscanf (line,
1168                         "%lf %lf L:(%lf, %lf), (%lf, %lf) R:(%lf, %lf), (%lf, %lf)",
1169                         &t.top, &t.bottom,
1170                         &t.left.p1.x, &t.left.p1.y,
1171                         &t.left.p2.x, &t.left.p2.y,
1172                         &t.right.p1.x, &t.right.p1.y,
1173                         &t.right.p2.x, &t.right.p2.y) == 10) {
1174                 traps = _traps_add_trapezoid (tv, traps, &t);
1175             } else {
1176                 if (traps->num_traps) {
1177                     g_print ("read %d trapezoids\n", traps->num_traps);
1178                     g_print ("extents=(%lg, %lg), (%lg, %lg)\n",
1179                              traps->extents.p1.x, traps->extents.p1.y,
1180                              traps->extents.p2.x, traps->extents.p2.y);
1181                     traps = traps_new (tv);
1182                 }
1183             }
1184         }
1185
1186         if (traps->num_traps) {
1187             g_print ("read %d trapezoids\n", traps->num_traps);
1188             g_print ("extents=(%lg, %lg), (%lg, %lg)\n",
1189                      traps->extents.p1.x, traps->extents.p1.y,
1190                      traps->extents.p2.x, traps->extents.p2.y);
1191         }
1192
1193         fclose (file);
1194     }
1195
1196     free (line);
1197
1198     tv2 = g_object_new (trap_view_get_type (), NULL);
1199     gtk_box_pack_start (GTK_BOX (hbox), &tv2->widget, TRUE, TRUE, 0);
1200     gtk_widget_show (&tv2->widget);
1201
1202     tv2->traps_list = tv->traps_list;
1203     tv2->current_traps = tv->current_traps;
1204
1205     tv2->group_prev = group_prev;
1206     tv2->group_next = NULL;
1207     group_prev->group_next = tv2;
1208     group_prev = tv2;
1209     tv2->group_head = group_head;
1210
1211     window = gtk_window_new (GTK_WINDOW_TOPLEVEL);
1212     g_signal_connect (window, "delete-event",
1213                       G_CALLBACK (gtk_main_quit), NULL);
1214     gtk_widget_set_size_request (window, 800, 800);
1215     gtk_container_add (GTK_CONTAINER (window), hbox);
1216     gtk_widget_show (hbox);
1217     gtk_widget_show (window);
1218
1219     gtk_main ();
1220     return 0;
1221 }