home *** CD-ROM | disk | FTP | other *** search
/ gdead.berkeley.edu / gdead.berkeley.edu.tar / gdead.berkeley.edu / pub / cad-tools / ciftomann.tar / merge.c < prev    next >
C/C++ Source or Header  |  1988-01-28  |  10KB  |  509 lines
  1. #include "ciftomann.h"
  2. #include "intersection.h"
  3. #include "aeledge.h"
  4. #include <stdio.h>
  5. #include "fd.h"
  6.  
  7. static AEL_LIST AEList;
  8. static AEL_EDGE medge;
  9. static AEL_EDGEPTR AEdge;
  10. static int CurrentY;
  11. static int delta;
  12. static int invert_flag;
  13. static int Ymax, Xmax, Ymin, Xmin;
  14.  
  15. AEL_EDGEPTR MakeEdge();
  16. static AEL_EDGEPTR GetEdge();
  17. static AEL_EDGEPTR Mask_Mod();
  18.  
  19. /*
  20.  * Merge reads sorted edges from the standard input and through the
  21.  * use of a scanline algorithm, removes all overlaps. if any grow/shrink
  22.  * is desired, the information gained in constructing the scanline is
  23.  * used to determine which direction each edge should be moved.
  24.  */
  25.  
  26. main(argc,argv)
  27. int argc;
  28. char **argv;
  29. {
  30.  
  31.     AEL_EDGEPTR MEdge,
  32.             Position;
  33.  
  34.     sscanf(argv[3],"%d",&delta);
  35.  
  36.     if ( argv[1][1] == 'i' ) {
  37.     invert_flag = 1;
  38.         /* we wish to invert the fiqure, so
  39.          * emit edges of the bounding box in which
  40.          * we are inverting the figure
  41.          */
  42.     emit_invert_edge(argv[2]);
  43.     } else {
  44.     invert_flag = 0;
  45.     }
  46.  
  47.     ProgName = "merge";
  48.  
  49.     AEList.bottom = MakeEdge(INFINITY,INFINITY,-INFINITY,1,NIL,NIL);
  50.     AEList.top = MakeEdge(-INFINITY,-INFINITY,-INFINITY,1,NIL,NIL);
  51.  
  52.     AEList.top->next = AEList.bottom;
  53.     AEList.bottom->last = AEList.top;
  54.  
  55.     MEdge = GetEdge();
  56.  
  57.     if (MEdge == NIL) {
  58.     fprintf(stderr,"Warning, no geometry on this layer\n");
  59.     close_merge();
  60.     }
  61.  
  62.     do {
  63.  
  64.     CurrentY = MEdge->y;
  65.     AEdge = AEList.top;
  66.  
  67.     do {
  68.         
  69.         /*
  70.          * find where the edge should be inserted into the
  71.          * scanline
  72.          */
  73.  
  74.         while ( Greater_than_Equal(MEdge->x, AEdge->next->x) )
  75.         AEdge = AEdge->next;
  76.  
  77.         Position = AEdge->last;
  78.  
  79.         do {
  80.             /* update the scanline and emit the necessary
  81.              * edges
  82.              */
  83.         Update(MEdge);
  84.         AEdge = AEdge->next;
  85.         } while (MEdge->sense != 0);
  86.  
  87.         MEdge = GetEdge();
  88.  
  89.         if (Position != NIL)
  90.         AEdge = Position;
  91.         else
  92.         AEdge = AEList.top;
  93.  
  94.     } while (MEdge != NIL && MEdge->y == CurrentY);
  95.  
  96.     ClearEmit();
  97.  
  98.     } while (MEdge != NIL);
  99.  
  100.     if (AEList.top->next != AEList.bottom) 
  101.     panic("Unterminated upward edges at end of merge");
  102.  
  103.     close_merge();
  104. }
  105.  
  106. emit_invert_edge(bb_string)
  107. char *bb_string;
  108. {
  109.  
  110.     AEL_EDGE edge;
  111.  
  112.     sscanf(bb_string,"%d %d %d %d",&Xmin,&Ymin,&Xmax,&Ymax);
  113.  
  114.     edge.x = Xmin - delta;
  115.     edge.xend = Xmax + delta;
  116.     edge.y = Ymin - delta;
  117.     edge.sense = UP;
  118.  
  119. #ifdef DEBUG
  120.     fprintf(stderr,"merge emits %d->%d at %d : sense = %d\n",edge.x,
  121.         edge.xend,edge.y,edge.sense);
  122. #endif
  123.  
  124.     if ( fwrite((char *)&edge, sizeof(EDGE), 1, stdout) 
  125.         == 0 ) {
  126.     panic("Bad write in EmitEdge");
  127.     }
  128. }
  129.  
  130. close_merge()
  131. {
  132.     /* emit the upper bounding edge of the bounding
  133.      * box
  134.      */
  135.     if ( invert_flag ) {
  136.     AEL_EDGE edge;
  137.  
  138.     edge.x = Xmin - delta;
  139.     edge.xend = Xmax + delta;
  140.     edge.y = Ymax + delta;
  141.     edge.sense = DOWN;
  142.  
  143.  
  144. #ifdef DEBUG
  145.     fprintf(stderr,"merge emits %d->%d at %d : sense = %d\n",edge.x,
  146.             edge.xend,edge.y,edge.sense);
  147. #endif
  148.  
  149.     if ( fwrite((char *)&edge, sizeof(EDGE), 1, stdout) 
  150.         == 0 ) {
  151.         panic("Bad write in EmitEdge");
  152.     }
  153.     }
  154.  
  155.     exit(0);
  156. }
  157.  
  158. static Update(M)
  159. AEL_EDGEPTR M;
  160. {
  161.  
  162.     /* update the scanline and emit new edges when appropriate.
  163.      * the diagram for each case shows the relation between the
  164.      * new edge and the closest edge in the scanline 
  165.      */
  166.  
  167.     switch (Intersection(AEdge,M)) {
  168.  
  169.     case COINCIDENT :    /*     M---------M
  170.                     A---------A         */
  171.  
  172.         AEdge->sense += M->sense;
  173.         M->sense = 0;
  174.  
  175.         if (AEdge->sense == 0) {
  176.         AEdge = AEdge->last;
  177.         EmitEdge(AEdge->next,DOWN);
  178.         Remove(AEList,AEdge->next);
  179.         }
  180.         break;
  181.  
  182.     case A_LCOVERS_M :    /*    M---------M
  183.                     A------------A        */
  184.  
  185.         AEdge->x = M->xend;
  186.         InsertAbove(AEdge,M->x,M->xend,CurrentY,AEdge->sense + M->sense);
  187.         M->sense = 0;
  188.  
  189.         if (AEdge->last->sense == 0) {
  190.         EmitEdge(AEdge->last,DOWN);
  191.         Remove(AEList,AEdge->last);
  192.         }
  193.         break;
  194.  
  195.     case M_LCOVERS_A :    /*    M------------M
  196.                     A---------A        */
  197.  
  198.         M->x = AEdge->xend;
  199.         AEdge->sense += M->sense;
  200.  
  201.         if (AEdge->sense == 0) {
  202.         AEdge = AEdge->last;
  203.         EmitEdge(AEdge->next,DOWN);
  204.         Remove(AEList,AEdge->next);
  205.         }
  206.         break;
  207.  
  208.     case LDISJOINT :    /*    M------M
  209.                          A----A        */
  210.  
  211.     case LPOINT :        /*    M------M
  212.                            A-----A        */
  213.         
  214.         InsertAbove(AEdge,M->x,M->xend,CurrentY,M->sense);
  215.         if (M->sense < 0)
  216.         panic("Unmatched downward edge found");
  217.         else
  218.         EmitEdge(AEdge->last,UP);
  219.         M->sense = 0;
  220.         break;
  221.  
  222.  
  223.     case M_RCOVERS_A :    /*    M------------M
  224.                          A-------A        */
  225.  
  226.         InsertAbove(AEdge,M->x,AEdge->x,CurrentY,M->sense);
  227.         if (M->sense < 0)
  228.         panic("Unmatched downward edge found");
  229.         else
  230.         EmitEdge(AEdge->last,UP);
  231.         AEdge->sense += M->sense;
  232.         M->sense = 0;
  233.  
  234.         if (AEdge->sense == 0) {
  235.         AEdge = AEdge->last;
  236.         EmitEdge(AEdge->next,DOWN);
  237.         Remove(AEList,AEdge->next);
  238.         }
  239.         break;
  240.  
  241.     case LOVERLAP :        /*    M-------M
  242.                           A------A        */
  243.  
  244.         InsertAbove(AEdge,M->x,AEdge->x,CurrentY,M->sense);
  245.         if (M->sense < 0)
  246.         panic("Unmatched downward edge found");
  247.         else
  248.         EmitEdge(AEdge->last,UP);
  249.         InsertAbove(AEdge,AEdge->x,M->xend,CurrentY,AEdge->sense + M->sense);
  250.         M->sense = 0;
  251.  
  252.         AEdge->x = M->xend;
  253.         if (AEdge->last->sense == 0) {
  254.         EmitEdge(AEdge->last,DOWN);
  255.         Remove(AEList,AEdge->last);
  256.         }
  257.         break;
  258.  
  259.     case M_COVERS_A :    /*    M------------M
  260.                       A--------A        */
  261.  
  262.         InsertAbove(AEdge,M->x,AEdge->x,CurrentY,M->sense);
  263.         if (M->sense < 0)
  264.         panic("Unmatched downward edge found");
  265.         else
  266.         EmitEdge(AEdge->last,UP);
  267.         AEdge->sense += M->sense;
  268.         M->x = AEdge->xend;
  269.  
  270.         if (AEdge->sense == 0) {
  271.         AEdge = AEdge->last;
  272.         EmitEdge(AEdge->next,DOWN);
  273.         Remove(AEList,AEdge->next);
  274.         }
  275.         break;
  276.  
  277.     case RDISJOINT :    /*            M-----M
  278.                     A-----A            */
  279.         
  280.     case RPOINT :        /*           M-----M
  281.                     A------A        */
  282.         
  283.         break;
  284.  
  285.     case A_RCOVERS_M :    /*           M-----M
  286.                     A------------A        */
  287.  
  288.         InsertAbove(AEdge,AEdge->x,M->x,CurrentY,AEdge->sense);
  289.         AEdge->x = M->x;
  290.         AEdge->sense += M->sense;
  291.         M->sense = 0;
  292.  
  293.         if (AEdge->sense == 0) {
  294.         AEdge = AEdge->last;
  295.         EmitEdge(AEdge->next,DOWN);
  296.         Remove(AEList,AEdge->next);
  297.         }
  298.         break;
  299.  
  300.     case A_COVERS_M :    /*      M--------M
  301.                     A------------A        */
  302.  
  303.         InsertAbove(AEdge,AEdge->x,M->x,CurrentY,AEdge->sense);
  304.         InsertAbove(AEdge,M->x,M->xend,CurrentY,AEdge->sense + M->sense);
  305.         AEdge->x = M->xend;
  306.         M->sense = 0;
  307.  
  308.         if (AEdge->last->sense == 0) {
  309.         EmitEdge(AEdge->last,DOWN);
  310.         Remove(AEList,AEdge->last);
  311.         }
  312.         break;
  313.  
  314.     case ROVERLAP :        /*          M------M
  315.                     A-------A        */
  316.  
  317.         InsertAbove(AEdge,AEdge->x,M->x,CurrentY,AEdge->sense);
  318.         AEdge->x = M->x;
  319.         AEdge->sense += M->sense;
  320.         M->x = AEdge->xend;
  321.  
  322.         if (AEdge->sense == 0) {
  323.         AEdge = AEdge->last;
  324.         EmitEdge(AEdge->next,DOWN);
  325.         Remove(AEList,AEdge->next);
  326.         }
  327.         break;
  328.     }
  329. }
  330.  
  331. extern EDGE EdgeArray[];
  332. extern int NumEdges;
  333.  
  334.     /* read in an edge, throwing away zero length ones */
  335.  
  336. static AEL_EDGEPTR GetEdge()
  337. {
  338.     static EDGE redge;
  339.     int status;
  340.  
  341.  
  342.     do {
  343.  
  344.     if ( fread((char *)&redge, sizeof(EDGE), 1, stdin) == 0 ) {
  345.         return(NIL);
  346.     }
  347.  
  348.     } while (redge.x == redge.xend);
  349.  
  350. #ifdef DEBUG
  351.     fprintf(stderr,"merge reads %d->%d at %d : sense = %d\n",redge.x,
  352.         redge.xend,redge.y,redge.sense);
  353. #endif
  354.  
  355.     medge.x = redge.x;
  356.     medge.xend = redge.xend;
  357.     medge.y = redge.y;
  358.     medge.sense = redge.sense;
  359.     return(&medge);
  360. }
  361.  
  362. #define SAVE(edge) {\
  363.     redge.x = edge->x;\
  364.     redge.xend = edge->xend;\
  365.     redge.y = edge->y;\
  366.     redge.sense = edge->sense;\
  367.     Empty = 0;\
  368. }
  369.  
  370. static int Empty = 1;
  371. static EDGE redge;
  372.  
  373. static EmitEdge(in_edge,sense) 
  374.  
  375.     /* Edges are saved in redge, rather than immediately emitted
  376.        so that contiguous edges can be merged in a single edge.
  377.        This is a bit of a hack.
  378.      */
  379.  
  380. AEL_EDGEPTR in_edge;
  381. int sense;
  382. {
  383.  
  384.     AEL_EDGEPTR out_edge;
  385.  
  386.     /* do the necessary mask modifications */
  387.  
  388.     out_edge = Mask_Mod(in_edge,sense);
  389.  
  390.     if (Empty) 
  391.     SAVE(out_edge)
  392.     else {
  393.     if (redge.sense == out_edge->sense && redge.xend == out_edge->x)
  394.         redge.xend = out_edge->xend;     /* edges add */
  395.     else if (redge.sense == -out_edge->sense && 
  396.             redge.xend == out_edge->xend)
  397.         if (redge.x == out_edge->x)
  398.         Empty = 1;        /* edges cancel each other */
  399.         else 
  400.         redge.xend = out_edge->x;    /* edges subtract */
  401.     else {
  402.         /* they do not touch at all, so emit the saved edge
  403.            and replace it with the new out_edge */
  404.  
  405. #ifdef DEBUG
  406.         fprintf(stderr,"merge emits %d->%d at %d : sense = %d\n",redge.x,
  407.             redge.xend,redge.y,redge.sense);
  408. #endif
  409.  
  410.         if ( fwrite((char *)&redge, sizeof(EDGE), 1, stdout) 
  411.             == 0 ) {
  412.         panic("Bad write in EmitEdge");
  413.         }
  414.  
  415.         SAVE(out_edge);
  416.     }
  417.     }
  418. }
  419.  
  420. static ClearEmit() 
  421.  
  422.     /* flush the saved edge (if any) in EmitEdge's 'buffer' */
  423.  
  424. {
  425.     if (!Empty) {
  426.     
  427. #ifdef DEBUG
  428.     fprintf(stderr,"merge emits %d->%d at %d : sense = %d\n",redge.x,
  429.         redge.xend,redge.y,redge.sense);
  430. #endif
  431.  
  432.     if ( fwrite((char *)&redge, sizeof(EDGE), 1, stdout) 
  433.         == 0 ) {
  434.         panic("Bad write in EmitEdge");
  435.     }
  436.     
  437.     Empty = 1;
  438.     }
  439. }
  440.  
  441. static AEL_EDGEPTR Mask_Mod(oldedge,sense)
  442.  
  443.     /*     Modify the edges properly for the required grow/shrink.
  444.      * This is done here because I need the information contained
  445.      * in merge's active edge list to decide which way to transform
  446.      * the end points of the edges.
  447.      */
  448.  
  449. AEL_EDGEPTR oldedge;
  450. int sense;
  451. {
  452.  
  453.     static AEL_EDGE newedge;
  454.  
  455.     if (delta != 0) {
  456.  
  457.     if ( oldedge->x == oldedge->last->xend ) {
  458.         newedge.x = oldedge->x + delta;
  459.     } else {
  460.         newedge.x = oldedge->x - delta;
  461.     }
  462.  
  463.     if ( oldedge->xend == oldedge->next->x ) {
  464.         newedge.xend = oldedge->xend - delta;
  465.     } else {
  466.         newedge.xend = oldedge->xend + delta;
  467.     }
  468.  
  469.     if ( sense == UP ) {
  470.         newedge.y = CurrentY - delta;
  471.     } else {
  472.         newedge.y = CurrentY + delta;
  473.     }
  474.     
  475.     if ( invert_flag ) {
  476.         newedge.sense = -sense;
  477.     } else {
  478.         newedge.sense = sense;
  479.     }
  480.  
  481.     return(&newedge);
  482.  
  483.     } else {
  484.  
  485.     newedge = *oldedge;
  486.  
  487.     if ( invert_flag ) {
  488.         newedge.sense = -sense;
  489.     } else {
  490.         newedge.sense = sense;
  491.     }
  492.  
  493.     newedge.y = CurrentY;
  494.     return(&newedge);
  495.     }
  496. }
  497.  
  498. #ifdef DEBUG
  499. MDump() 
  500. {
  501.     AEL_EDGEPTR edge = AEList.top;
  502.  
  503.     while (edge != NIL) {
  504.     PrintEdge(edge);
  505.     edge = edge->next;
  506.     }
  507. }
  508. #endif 
  509.