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 >
Wrap
C/C++ Source or Header
|
1988-01-28
|
10KB
|
509 lines
#include "ciftomann.h"
#include "intersection.h"
#include "aeledge.h"
#include <stdio.h>
#include "fd.h"
static AEL_LIST AEList;
static AEL_EDGE medge;
static AEL_EDGEPTR AEdge;
static int CurrentY;
static int delta;
static int invert_flag;
static int Ymax, Xmax, Ymin, Xmin;
AEL_EDGEPTR MakeEdge();
static AEL_EDGEPTR GetEdge();
static AEL_EDGEPTR Mask_Mod();
/*
* Merge reads sorted edges from the standard input and through the
* use of a scanline algorithm, removes all overlaps. if any grow/shrink
* is desired, the information gained in constructing the scanline is
* used to determine which direction each edge should be moved.
*/
main(argc,argv)
int argc;
char **argv;
{
AEL_EDGEPTR MEdge,
Position;
sscanf(argv[3],"%d",&delta);
if ( argv[1][1] == 'i' ) {
invert_flag = 1;
/* we wish to invert the fiqure, so
* emit edges of the bounding box in which
* we are inverting the figure
*/
emit_invert_edge(argv[2]);
} else {
invert_flag = 0;
}
ProgName = "merge";
AEList.bottom = MakeEdge(INFINITY,INFINITY,-INFINITY,1,NIL,NIL);
AEList.top = MakeEdge(-INFINITY,-INFINITY,-INFINITY,1,NIL,NIL);
AEList.top->next = AEList.bottom;
AEList.bottom->last = AEList.top;
MEdge = GetEdge();
if (MEdge == NIL) {
fprintf(stderr,"Warning, no geometry on this layer\n");
close_merge();
}
do {
CurrentY = MEdge->y;
AEdge = AEList.top;
do {
/*
* find where the edge should be inserted into the
* scanline
*/
while ( Greater_than_Equal(MEdge->x, AEdge->next->x) )
AEdge = AEdge->next;
Position = AEdge->last;
do {
/* update the scanline and emit the necessary
* edges
*/
Update(MEdge);
AEdge = AEdge->next;
} while (MEdge->sense != 0);
MEdge = GetEdge();
if (Position != NIL)
AEdge = Position;
else
AEdge = AEList.top;
} while (MEdge != NIL && MEdge->y == CurrentY);
ClearEmit();
} while (MEdge != NIL);
if (AEList.top->next != AEList.bottom)
panic("Unterminated upward edges at end of merge");
close_merge();
}
emit_invert_edge(bb_string)
char *bb_string;
{
AEL_EDGE edge;
sscanf(bb_string,"%d %d %d %d",&Xmin,&Ymin,&Xmax,&Ymax);
edge.x = Xmin - delta;
edge.xend = Xmax + delta;
edge.y = Ymin - delta;
edge.sense = UP;
#ifdef DEBUG
fprintf(stderr,"merge emits %d->%d at %d : sense = %d\n",edge.x,
edge.xend,edge.y,edge.sense);
#endif
if ( fwrite((char *)&edge, sizeof(EDGE), 1, stdout)
== 0 ) {
panic("Bad write in EmitEdge");
}
}
close_merge()
{
/* emit the upper bounding edge of the bounding
* box
*/
if ( invert_flag ) {
AEL_EDGE edge;
edge.x = Xmin - delta;
edge.xend = Xmax + delta;
edge.y = Ymax + delta;
edge.sense = DOWN;
#ifdef DEBUG
fprintf(stderr,"merge emits %d->%d at %d : sense = %d\n",edge.x,
edge.xend,edge.y,edge.sense);
#endif
if ( fwrite((char *)&edge, sizeof(EDGE), 1, stdout)
== 0 ) {
panic("Bad write in EmitEdge");
}
}
exit(0);
}
static Update(M)
AEL_EDGEPTR M;
{
/* update the scanline and emit new edges when appropriate.
* the diagram for each case shows the relation between the
* new edge and the closest edge in the scanline
*/
switch (Intersection(AEdge,M)) {
case COINCIDENT : /* M---------M
A---------A */
AEdge->sense += M->sense;
M->sense = 0;
if (AEdge->sense == 0) {
AEdge = AEdge->last;
EmitEdge(AEdge->next,DOWN);
Remove(AEList,AEdge->next);
}
break;
case A_LCOVERS_M : /* M---------M
A------------A */
AEdge->x = M->xend;
InsertAbove(AEdge,M->x,M->xend,CurrentY,AEdge->sense + M->sense);
M->sense = 0;
if (AEdge->last->sense == 0) {
EmitEdge(AEdge->last,DOWN);
Remove(AEList,AEdge->last);
}
break;
case M_LCOVERS_A : /* M------------M
A---------A */
M->x = AEdge->xend;
AEdge->sense += M->sense;
if (AEdge->sense == 0) {
AEdge = AEdge->last;
EmitEdge(AEdge->next,DOWN);
Remove(AEList,AEdge->next);
}
break;
case LDISJOINT : /* M------M
A----A */
case LPOINT : /* M------M
A-----A */
InsertAbove(AEdge,M->x,M->xend,CurrentY,M->sense);
if (M->sense < 0)
panic("Unmatched downward edge found");
else
EmitEdge(AEdge->last,UP);
M->sense = 0;
break;
case M_RCOVERS_A : /* M------------M
A-------A */
InsertAbove(AEdge,M->x,AEdge->x,CurrentY,M->sense);
if (M->sense < 0)
panic("Unmatched downward edge found");
else
EmitEdge(AEdge->last,UP);
AEdge->sense += M->sense;
M->sense = 0;
if (AEdge->sense == 0) {
AEdge = AEdge->last;
EmitEdge(AEdge->next,DOWN);
Remove(AEList,AEdge->next);
}
break;
case LOVERLAP : /* M-------M
A------A */
InsertAbove(AEdge,M->x,AEdge->x,CurrentY,M->sense);
if (M->sense < 0)
panic("Unmatched downward edge found");
else
EmitEdge(AEdge->last,UP);
InsertAbove(AEdge,AEdge->x,M->xend,CurrentY,AEdge->sense + M->sense);
M->sense = 0;
AEdge->x = M->xend;
if (AEdge->last->sense == 0) {
EmitEdge(AEdge->last,DOWN);
Remove(AEList,AEdge->last);
}
break;
case M_COVERS_A : /* M------------M
A--------A */
InsertAbove(AEdge,M->x,AEdge->x,CurrentY,M->sense);
if (M->sense < 0)
panic("Unmatched downward edge found");
else
EmitEdge(AEdge->last,UP);
AEdge->sense += M->sense;
M->x = AEdge->xend;
if (AEdge->sense == 0) {
AEdge = AEdge->last;
EmitEdge(AEdge->next,DOWN);
Remove(AEList,AEdge->next);
}
break;
case RDISJOINT : /* M-----M
A-----A */
case RPOINT : /* M-----M
A------A */
break;
case A_RCOVERS_M : /* M-----M
A------------A */
InsertAbove(AEdge,AEdge->x,M->x,CurrentY,AEdge->sense);
AEdge->x = M->x;
AEdge->sense += M->sense;
M->sense = 0;
if (AEdge->sense == 0) {
AEdge = AEdge->last;
EmitEdge(AEdge->next,DOWN);
Remove(AEList,AEdge->next);
}
break;
case A_COVERS_M : /* M--------M
A------------A */
InsertAbove(AEdge,AEdge->x,M->x,CurrentY,AEdge->sense);
InsertAbove(AEdge,M->x,M->xend,CurrentY,AEdge->sense + M->sense);
AEdge->x = M->xend;
M->sense = 0;
if (AEdge->last->sense == 0) {
EmitEdge(AEdge->last,DOWN);
Remove(AEList,AEdge->last);
}
break;
case ROVERLAP : /* M------M
A-------A */
InsertAbove(AEdge,AEdge->x,M->x,CurrentY,AEdge->sense);
AEdge->x = M->x;
AEdge->sense += M->sense;
M->x = AEdge->xend;
if (AEdge->sense == 0) {
AEdge = AEdge->last;
EmitEdge(AEdge->next,DOWN);
Remove(AEList,AEdge->next);
}
break;
}
}
extern EDGE EdgeArray[];
extern int NumEdges;
/* read in an edge, throwing away zero length ones */
static AEL_EDGEPTR GetEdge()
{
static EDGE redge;
int status;
do {
if ( fread((char *)&redge, sizeof(EDGE), 1, stdin) == 0 ) {
return(NIL);
}
} while (redge.x == redge.xend);
#ifdef DEBUG
fprintf(stderr,"merge reads %d->%d at %d : sense = %d\n",redge.x,
redge.xend,redge.y,redge.sense);
#endif
medge.x = redge.x;
medge.xend = redge.xend;
medge.y = redge.y;
medge.sense = redge.sense;
return(&medge);
}
#define SAVE(edge) {\
redge.x = edge->x;\
redge.xend = edge->xend;\
redge.y = edge->y;\
redge.sense = edge->sense;\
Empty = 0;\
}
static int Empty = 1;
static EDGE redge;
static EmitEdge(in_edge,sense)
/* Edges are saved in redge, rather than immediately emitted
so that contiguous edges can be merged in a single edge.
This is a bit of a hack.
*/
AEL_EDGEPTR in_edge;
int sense;
{
AEL_EDGEPTR out_edge;
/* do the necessary mask modifications */
out_edge = Mask_Mod(in_edge,sense);
if (Empty)
SAVE(out_edge)
else {
if (redge.sense == out_edge->sense && redge.xend == out_edge->x)
redge.xend = out_edge->xend; /* edges add */
else if (redge.sense == -out_edge->sense &&
redge.xend == out_edge->xend)
if (redge.x == out_edge->x)
Empty = 1; /* edges cancel each other */
else
redge.xend = out_edge->x; /* edges subtract */
else {
/* they do not touch at all, so emit the saved edge
and replace it with the new out_edge */
#ifdef DEBUG
fprintf(stderr,"merge emits %d->%d at %d : sense = %d\n",redge.x,
redge.xend,redge.y,redge.sense);
#endif
if ( fwrite((char *)&redge, sizeof(EDGE), 1, stdout)
== 0 ) {
panic("Bad write in EmitEdge");
}
SAVE(out_edge);
}
}
}
static ClearEmit()
/* flush the saved edge (if any) in EmitEdge's 'buffer' */
{
if (!Empty) {
#ifdef DEBUG
fprintf(stderr,"merge emits %d->%d at %d : sense = %d\n",redge.x,
redge.xend,redge.y,redge.sense);
#endif
if ( fwrite((char *)&redge, sizeof(EDGE), 1, stdout)
== 0 ) {
panic("Bad write in EmitEdge");
}
Empty = 1;
}
}
static AEL_EDGEPTR Mask_Mod(oldedge,sense)
/* Modify the edges properly for the required grow/shrink.
* This is done here because I need the information contained
* in merge's active edge list to decide which way to transform
* the end points of the edges.
*/
AEL_EDGEPTR oldedge;
int sense;
{
static AEL_EDGE newedge;
if (delta != 0) {
if ( oldedge->x == oldedge->last->xend ) {
newedge.x = oldedge->x + delta;
} else {
newedge.x = oldedge->x - delta;
}
if ( oldedge->xend == oldedge->next->x ) {
newedge.xend = oldedge->xend - delta;
} else {
newedge.xend = oldedge->xend + delta;
}
if ( sense == UP ) {
newedge.y = CurrentY - delta;
} else {
newedge.y = CurrentY + delta;
}
if ( invert_flag ) {
newedge.sense = -sense;
} else {
newedge.sense = sense;
}
return(&newedge);
} else {
newedge = *oldedge;
if ( invert_flag ) {
newedge.sense = -sense;
} else {
newedge.sense = sense;
}
newedge.y = CurrentY;
return(&newedge);
}
}
#ifdef DEBUG
MDump()
{
AEL_EDGEPTR edge = AEList.top;
while (edge != NIL) {
PrintEdge(edge);
edge = edge->next;
}
}
#endif