350 lines
8.6 KiB
C
350 lines
8.6 KiB
C
/* CIFreadpoly.c -
|
|
*
|
|
* This file contains procedures that turn polygons into
|
|
* rectangles, as part of CIF file reading.
|
|
*
|
|
* *********************************************************************
|
|
* * Copyright (C) 1985, 1990 Regents of the University of California. *
|
|
* * Permission to use, copy, modify, and distribute this *
|
|
* * software and its documentation for any purpose and without *
|
|
* * fee is hereby granted, provided that the above copyright *
|
|
* * notice appear in all copies. The University of California *
|
|
* * makes no representations about the suitability of this *
|
|
* * software for any purpose. It is provided "as is" without *
|
|
* * express or implied warranty. Export of this software outside *
|
|
* * of the United States of America may require an export license. *
|
|
* *********************************************************************
|
|
*/
|
|
|
|
#ifndef lint
|
|
static const char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/cif/CIFrdpoly.c,v 1.3 2010/06/24 12:37:15 tim Exp $";
|
|
#endif /* not lint */
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h> /* For qsort() */
|
|
#include "utils/magic.h"
|
|
#include "utils/geometry.h"
|
|
#include "tiles/tile.h"
|
|
#include "utils/hash.h"
|
|
#include "database/database.h"
|
|
#include "cif/CIFint.h"
|
|
#include "cif/CIFread.h"
|
|
#include "calma/calma.h"
|
|
#include "utils/malloc.h"
|
|
|
|
#define HEDGE 0 /* Horizontal edge */
|
|
#define REDGE 1 /* Rising edge */
|
|
#define FEDGE -1 /* Falling edge */
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* cifLowX --
|
|
*
|
|
* This is a comparison procedure called by qsort.
|
|
*
|
|
* Results:
|
|
* 1 if a.x > b.x,
|
|
* -1 if a.x < b.x,
|
|
* 0 otherwise.
|
|
*
|
|
* Side effects:
|
|
* None.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
int
|
|
cifLowX(
|
|
const void *aa,
|
|
const void *bb)
|
|
{
|
|
const CIFPath **a = (const CIFPath **)aa;
|
|
const CIFPath **b = (const CIFPath **)bb;
|
|
|
|
const Point *p, *q;
|
|
|
|
p = &(*a)->cifp_point;
|
|
q = &(*b)->cifp_point;
|
|
if (p->p_x < q->p_x)
|
|
return (-1);
|
|
if (p->p_x > q->p_x)
|
|
return (1);
|
|
return (0);
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* cifLowY --
|
|
*
|
|
* This is another comparison procedure called by qsort.
|
|
*
|
|
* Results:
|
|
* 1 if a.y > b.y
|
|
* -1 if a.y < b.y
|
|
* 0 otherwise
|
|
*
|
|
* Side effects:
|
|
* None.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
int
|
|
cifLowY(
|
|
const void *aa,
|
|
const void *bb)
|
|
{
|
|
const Point **a = (const Point **)aa;
|
|
const Point **b = (const Point **)bb;
|
|
if ((*a)->p_y < (*b)->p_y)
|
|
return (-1);
|
|
if ((*a)->p_y > (*b)->p_y)
|
|
return (1);
|
|
return (0);
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* cifOrient --
|
|
*
|
|
* This procedure assigns a direction to each of the edges in a
|
|
* polygon.
|
|
*
|
|
* Results:
|
|
* TRUE is returned if all of the edges are horizontal or vertical,
|
|
* FALSE is returned otherwise. If FALSE is returned, not all of
|
|
* the directions will have been filled in.
|
|
*
|
|
* Side effects:
|
|
* The parameter dir is filled in with the directions, which are
|
|
* each one of HEDGE, REDGE, or FEDGE.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
bool
|
|
cifOrient(
|
|
CIFPath *edges[], /* Array of edges to be categorized. */
|
|
int nedges, /* Size of arrays. */
|
|
int dir[]) /* Array to hold directions. */
|
|
{
|
|
Point *p, *q;
|
|
int n;
|
|
|
|
for (n = 0; n < nedges; n++)
|
|
{
|
|
/* note - path list should close on itself */
|
|
p = &edges[n]->cifp_point;
|
|
q = &edges[n]->cifp_next->cifp_point;
|
|
if (p->p_y == q->p_y)
|
|
{
|
|
/* note - point may connect to itself here */
|
|
dir[n] = HEDGE;
|
|
continue;
|
|
}
|
|
if (p->p_x == q->p_x)
|
|
{
|
|
if (p->p_y < q->p_y)
|
|
{
|
|
dir[n] = REDGE;
|
|
continue;
|
|
}
|
|
if (p->p_y > q->p_y)
|
|
{
|
|
dir[n] = FEDGE;
|
|
continue;
|
|
}
|
|
/* Point connects to itself */
|
|
dir[n] = HEDGE;
|
|
continue;
|
|
}
|
|
/* It's not Manhattan, folks. */
|
|
return (FALSE);
|
|
}
|
|
return (TRUE);
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* cifCross --
|
|
*
|
|
* This procedure is used to see if an edge crosses a particular
|
|
* area.
|
|
*
|
|
* Results:
|
|
* TRUE is returned if edge is vertical and if it crosses the
|
|
* y-range defined by ybot and ytop. FALSE is returned otherwise.
|
|
*
|
|
* Side effects:
|
|
* None.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
bool
|
|
cifCross(
|
|
CIFPath *edge, /* Pointer to first of 2 path points in edge */
|
|
int dir, /* Direction of edge */
|
|
int ybot,
|
|
int ytop) /* Range of interest */
|
|
{
|
|
int ebot, etop;
|
|
|
|
switch (dir)
|
|
{
|
|
case REDGE:
|
|
ebot = edge->cifp_point.p_y;
|
|
etop = edge->cifp_next->cifp_point.p_y;
|
|
return (ebot <= ybot && etop >= ytop);
|
|
|
|
case FEDGE:
|
|
ebot = edge->cifp_next->cifp_point.p_y;
|
|
etop = edge->cifp_point.p_y;
|
|
return (ebot <= ybot && etop >= ytop);
|
|
|
|
}
|
|
|
|
return (FALSE);
|
|
}
|
|
|
|
/*
|
|
* ----------------------------------------------------------------------------
|
|
*
|
|
* CIFPolyToRects --
|
|
*
|
|
* Converts a manhattan polygon (specified as a path) into a
|
|
* linked list of rectangles.
|
|
*
|
|
* Results:
|
|
* The return value is a linked list of rectangles, or NULL if
|
|
* something went wrong.
|
|
*
|
|
* Side effects:
|
|
* Memory is allocated to hold the list of rectangles. It is
|
|
* the caller's responsibility to free up the memory.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
*/
|
|
|
|
LinkedRect *
|
|
CIFPolyToRects(
|
|
CIFPath *path, /* Path describing a polygon. */
|
|
Plane *plane, /* Plane to draw on */
|
|
const PaintResultType *resultTbl,
|
|
PaintUndoInfo *ui,
|
|
bool isCalma) /* TRUE for Calma, FALSE for CIF */
|
|
{
|
|
int npts = 0, n, *dir, curr, wrapno;
|
|
int xbot, xtop, ybot, ytop;
|
|
Point **pts;
|
|
CIFPath *p, **edges, *tail = 0;
|
|
LinkedRect *rex = 0, *new;
|
|
|
|
/* Close path list. */
|
|
|
|
for (tail = path; tail->cifp_next; tail = tail->cifp_next);
|
|
|
|
if ((tail->cifp_x != path->cifp_x) || (tail->cifp_y != path->cifp_y))
|
|
{
|
|
if (isCalma)
|
|
CalmaReadError("Boundary is not closed.\n" );
|
|
|
|
p = (CIFPath *) mallocMagic ((unsigned) sizeof (CIFPath));
|
|
p->cifp_x = path->cifp_x;
|
|
p->cifp_y = path->cifp_y;
|
|
p->cifp_next = (CIFPath *) 0;
|
|
tail->cifp_next = p;
|
|
}
|
|
|
|
CIFMakeManhattanPath(path, plane, resultTbl, ui);
|
|
|
|
for (p = path; p->cifp_next; p = p->cifp_next, npts++);
|
|
pts = (Point **)mallocMagic(npts * sizeof(Point *));
|
|
dir = (int *)mallocMagic(npts * sizeof(int));
|
|
edges = (CIFPath **)mallocMagic(npts * sizeof(CIFPath *));
|
|
npts = 0;
|
|
|
|
for (p = path; p->cifp_next; p = p->cifp_next, npts++)
|
|
{
|
|
pts[npts] = &(p->cifp_point);
|
|
edges[npts] = p;
|
|
}
|
|
|
|
if (npts < 4)
|
|
{
|
|
if (npts > 0)
|
|
CIFReadError("polygon with fewer than 4 points.\n" );
|
|
goto done;
|
|
}
|
|
|
|
/* Sort points by low y, edges by low x */
|
|
|
|
qsort ((char *) pts, npts, (int) sizeof (Point *), cifLowY);
|
|
qsort ((char *) edges, npts, (int) sizeof (CIFPath *), cifLowX);
|
|
|
|
/* Find out which direction each edge points. */
|
|
|
|
if (!cifOrient (edges, npts, dir))
|
|
{
|
|
CIFReadError("non-manhattan polygon.\n" );
|
|
goto done;
|
|
}
|
|
|
|
/* Scan the polygon from bottom to top. At each step, process
|
|
* a minimum-sized y-range of the polygon (i.e. a range such that
|
|
* there are no vertices inside the range). Use wrap numbers
|
|
* based on the edge orientations to determine how much of the
|
|
* x-range for this y-range should contain material.
|
|
*/
|
|
|
|
for (curr = 1; curr < npts; curr++)
|
|
{
|
|
/* Find the next minimum-sized y-range. */
|
|
|
|
ybot = pts[curr-1]->p_y;
|
|
while (ybot == pts[curr]->p_y)
|
|
if (++curr >= npts) goto done;
|
|
ytop = pts[curr]->p_y;
|
|
|
|
/* Process all the edges that cross the y-range, from left
|
|
* to right.
|
|
*/
|
|
|
|
for (wrapno=0, n=0; n < npts; n++)
|
|
{
|
|
if (wrapno == 0) xbot = edges[n]->cifp_x;
|
|
if (!cifCross(edges[n], dir[n], ybot, ytop))
|
|
continue;
|
|
wrapno += dir[n] == REDGE ? 1 : -1;
|
|
if (wrapno == 0)
|
|
{
|
|
xtop = edges[n]->cifp_point.p_x;
|
|
if (xbot == xtop) continue;
|
|
new = (LinkedRect *) mallocMagic(sizeof(LinkedRect));
|
|
new->r_r.r_xbot = xbot;
|
|
new->r_r.r_ybot = ybot;
|
|
new->r_r.r_xtop = xtop;
|
|
new->r_r.r_ytop = ytop;
|
|
new->r_next = rex;
|
|
rex = new;
|
|
}
|
|
}
|
|
}
|
|
|
|
/* Normally, the loop exits directly to done, below. It
|
|
* only falls through here if the polygon has a degenerate
|
|
* spike at its top (i.e. if there's only one point with
|
|
* highest y-coordinate).
|
|
*/
|
|
|
|
done:
|
|
freeMagic((char *)edges);
|
|
freeMagic((char *)dir);
|
|
freeMagic((char *)pts);
|
|
return (rex);
|
|
}
|