blind-find-rectangle.c (3127B)
1 /* See LICENSE file for copyright and license details. */ 2 #include "common.h" 3 4 USAGE("[-a min-area] [-h min-height] [-w min-width] X Y Z [alpha]") 5 6 struct pair { 7 size_t x; 8 size_t w; 9 }; 10 11 static struct stream stream; 12 static size_t min_width = 1; 13 static size_t min_height = 1; 14 static size_t min_area = 1; 15 static struct pair *stack = NULL; 16 static size_t *cache = NULL; 17 static char *buf = NULL; 18 19 static void 20 process(const void *colour) 21 { 22 size_t y, x, x0, w, w0, h, top, area; 23 size_t best_area, x1, x2, y1, y2; 24 for (;;) { 25 top = x1 = x2 = y1 = y2 = best_area = 0; 26 memset(cache, 0, (stream.width + 1) * sizeof(*cache)); 27 for (y = 0; eread_row(&stream, buf); y++) { 28 w = 0; 29 for (x = 0; x <= stream.width; x++) { 30 if (x != stream.width) { 31 if (!memcmp(buf + x * stream.pixel_size, colour, stream.pixel_size)) 32 cache[x] += 1; 33 else 34 cache[x] = 0; 35 } 36 if (cache[x] > w) { 37 stack[top].x = x; 38 stack[top++].w = w; 39 w = cache[x]; 40 } else if (cache[x] < w) { 41 do { 42 x0 = stack[--top].x; 43 w0 = stack[top].w; 44 area = w * (x - x0); 45 if (area > best_area) { 46 best_area = area; 47 x1 = x0; 48 x2 = x - 1; 49 y1 = y - w + 1; 50 y2 = y; 51 } 52 w = w0; 53 } while (cache[x] < w); 54 if ((w = cache[x])) { 55 stack[top].x = x0; 56 stack[top++].w = w0; 57 } 58 } 59 } 60 fprintf(stderr, "%zu\n", y); 61 } 62 if (!y) 63 break; 64 w = x2 - x1 + 1; 65 h = y2 - y1 + 1; 66 if (best_area < min_area || w < min_width || h < min_height) 67 printf("0 0 0 0\n"); 68 else 69 printf("%zu %zu %zu %zu\n", x1, y1, w, h); 70 } 71 } 72 73 int 74 main(int argc, char *argv[]) 75 { 76 double colour_lf[4]; 77 float colour_f[4]; 78 double X, Y, Z, alpha = 1; 79 80 ARGBEGIN { 81 case 'a': 82 min_area = etozu_flag('a', UARGF(), 1, SIZE_MAX); 83 break; 84 case 'h': 85 min_height = etozu_flag('h', UARGF(), 1, SIZE_MAX); 86 break; 87 case 'w': 88 min_width = etozu_flag('w', UARGF(), 1, SIZE_MAX); 89 break; 90 default: 91 usage(); 92 } ARGEND; 93 94 if (argc != 3 && argc != 4) 95 usage(); 96 97 X = etolf_arg("the X value", argv[0]); 98 Y = etolf_arg("the Y value", argv[1]); 99 Z = etolf_arg("the Z value", argv[2]); 100 if (argc > 3) 101 alpha = etolf_arg("the alpha value", argv[3]); 102 103 eopen_stream(&stream, NULL); 104 echeck_dimensions(&stream, WIDTH, NULL); 105 if (stream.width == SIZE_MAX) 106 eprintf("video is too wide\n"); 107 if (stream.width > SIZE_MAX / stream.height) 108 eprintf("video is too large\n"); 109 110 stack = emalloc2(stream.width + 1, sizeof(*stack)); 111 cache = emalloc2(stream.width + 1, sizeof(*cache)); 112 buf = emalloc(stream.row_size); 113 114 if (argc > 3) 115 CHECK_ALPHA(&stream); 116 CHECK_N_CHAN(&stream, 1, 3 + !!stream.alpha); 117 if (stream.encoding == DOUBLE) { 118 colour_lf[0] = X; 119 colour_lf[1] = Y; 120 colour_lf[2] = Z; 121 colour_lf[3] = alpha; 122 process(colour_lf); 123 } else if (stream.encoding == FLOAT) { 124 colour_f[0] = (float)X; 125 colour_f[1] = (float)Y; 126 colour_f[2] = (float)Z; 127 colour_f[3] = (float)alpha; 128 process(colour_f); 129 } else { 130 eprintf("pixel format %s is not supported, try xyza\n", stream.pixfmt); 131 } 132 133 fshut(stdout, "<stdout>"); 134 free(stack); 135 free(cache); 136 free(buf); 137 return 0; 138 }