Question 3 of 9: Programming — VLSI Wire Intersection Detection

Question 3: Programming — VLSI Wire Intersection Detection (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. 20 wires, each purely horizontal ($y_1=y_2$) or purely vertical ($x_1=x_2$), given as endpoint pairs.

Find. Every pair of wires that intersects, printed as their coordinate pairs.

Approach. Classify each wire once by orientation. Two wires of the same orientation are parallel and run-track spacing in real layouts keeps them from touching, so this check only tests each horizontal/vertical pair: a horizontal wire at $y=y_h$ spanning $[x_{\min},x_{\max}]$ crosses a vertical wire at $x=x_v$ spanning $[y_{\min},y_{\max}]$ exactly when $x_v$ falls inside the horizontal wire's $x$-span and $y_h$ falls inside the vertical wire's $y$-span.

1. Read all 20 wires into two arrays, split by orientation. Following the hint, classify each wire as it is read ($y_1=y_2 \Rightarrow$ horizontal, $x_1=x_2 \Rightarrow$ vertical) into a horizontal-wire array and a vertical-wire array, normalising each into (fixed coordinate, span-low, span-high) so the intersection test needs no further min/max work.
2. Write the program.

   #include <stdio.h>
   
   typedef struct { double fixed, lo, hi; } Seg;   /* horizontal: fixed=y; vertical: fixed=x */
   #define MAXW 20
   
   int main(void)
   {
       Seg h[MAXW], v[MAXW];
       int nh = 0, nv = 0, i, j;
       double x1, y1, x2, y2;
   
       for (i = 0; i < MAXW; i++) {
           scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
           if (y1 == y2) {                                  /* horizontal */
               h[nh].fixed = y1;
               h[nh].lo = (x1 < x2) ? x1 : x2;
               h[nh].hi = (x1 < x2) ? x2 : x1;
               nh++;
           } else {                                          /* vertical */
               v[nv].fixed = x1;
               v[nv].lo = (y1 < y2) ? y1 : y2;
               v[nv].hi = (y1 < y2) ? y2 : y1;
               nv++;
           }
       }
   
       for (i = 0; i < nh; i++) {
           for (j = 0; j < nv; j++) {
               if (v[j].fixed >= h[i].lo && v[j].fixed <= h[i].hi &&
                   h[i].fixed >= v[j].lo && h[i].fixed <= v[j].hi) {
                   printf("Horizontal (y=%.1f, x %.1f..%.1f) intersects "
                          "Vertical (x=%.1f, y %.1f..%.1f)\n",
                          h[i].fixed, h[i].lo, h[i].hi,
                          v[j].fixed, v[j].lo, v[j].hi);
               }
           }
       }
       return 0;
   }

3. Confirm against the question's own two example wires. The paper's (6,8:3,8) horizontal wire spans $x\in[3,6]$ at $y=8$; its (2,4:2,6) vertical wire is at $x=2$, spanning $y\in[4,6]$. Since $x=2$ does not fall in $[3,6]$, the program correctly reports no intersection for that pair — a vertical wire at $x=5$ over the same $y$-span, by contrast, does fall in $[3,6]$ and at $y=8$ (outside $[4,6]$) still would not cross, while one spanning $y\in[6,10]$ would. $$\boxed{\text{intersects}\big((6,8{:}3,8),\,(2,4{:}2,6)\big)=\text{false}}$$