mirror of
https://github.com/RTimothyEdwards/magic.git
synced 2026-08-31 02:07:07 +02:00
R. Timothy Edwards
516c9d7635
and forcing it to be passed as an argument to all the callback functions for the search routines that require it. Magic now compiles and runs with the new code, but there are a number of known issues that need to be fixed up. Committing now so that I can rebase on the last update to the master branch.
346 lines
8.7 KiB
C
346 lines
8.7 KiB
C
|
|
#ifndef lint
|
|
static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/utils/maxrect.c,v 1.4 2010/09/24 19:53:20 tim Exp $";
|
|
#endif
|
|
|
|
#include <sys/types.h>
|
|
#include <stdio.h>
|
|
#include <string.h> /* for memcpy() */
|
|
|
|
#include "utils/maxrect.h"
|
|
#include "utils/malloc.h"
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* genCanonicalMaxwidth - checks to see that at least one dimension of a
|
|
* rectangular region does not exceed some amount. Searches on all
|
|
* tiles of types in "mask", unless mask is NULL, in which case it
|
|
* searches over all tiles whose client record matches that of the
|
|
* start tile.
|
|
*
|
|
* Side Effects:
|
|
* None.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
MaxRectsData *
|
|
genCanonicalMaxwidth(bbox, starttile, plane, mask)
|
|
Rect *bbox; /* Bounding box of geometry to search */
|
|
Tile *starttile; /* Any point in the geometry to search */
|
|
Plane *plane; /* Plane being searched */
|
|
TileTypeBitMask *mask; /* Mask of types to check */
|
|
{
|
|
int s;
|
|
Tile *tile, *tp;
|
|
TileTypeBitMask wrongtypes;
|
|
static MaxRectsData *mrd = (MaxRectsData *)NULL;
|
|
Rect boundorig;
|
|
|
|
/* Generate an initial array size of 8 for rlist and swap. */
|
|
if (mrd == (MaxRectsData *)NULL)
|
|
{
|
|
mrd = (MaxRectsData *)mallocMagic(sizeof(MaxRectsData));
|
|
mrd->rlist = (Rect *)mallocMagic(8 * sizeof(Rect));
|
|
mrd->swap = (Rect *)mallocMagic(8 * sizeof(Rect));
|
|
mrd->listdepth = 8;
|
|
}
|
|
if (mask == NULL)
|
|
mrd->match = TiGetClient(starttile);
|
|
else
|
|
mrd->match = CLIENTDEFAULT;
|
|
|
|
mrd->rlist[0] = *bbox;
|
|
boundorig = *bbox;
|
|
|
|
/* Do an area search on boundrect to find all materials not */
|
|
/* in oktypes. Each such tile clips or subdivides */
|
|
/* boundrect. Due to the way FindMaxRects is written for */
|
|
/* the DRC maxwidth rule, maxdist = 1 is required to avoid */
|
|
/* creating degenerate (zero size) areas. */
|
|
|
|
mrd->entries = 1;
|
|
mrd->maxdist = 1;
|
|
if (mask != NULL)
|
|
TTMaskCom2(&wrongtypes, mask);
|
|
else
|
|
TTMaskSetMask(&wrongtypes, &DBAllTypeBits);
|
|
|
|
DBSrPaintArea(starttile, plane, &boundorig, &wrongtypes, FindMaxRects, mrd);
|
|
if (mrd->entries == 0)
|
|
return NULL;
|
|
else
|
|
return (MaxRectsData *)mrd;
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* FindMaxRects ---
|
|
*
|
|
* Procedure used to split an area up into multiple sets of possible
|
|
* convex rectangles.
|
|
*
|
|
* Results:
|
|
* Return 0 to keep the search going.
|
|
*
|
|
* Side effects:
|
|
* Adds data to structure mrd; possibly expanding its memory allocation.
|
|
*
|
|
* Notes:
|
|
* This routine does *not* handle non-Manhattan geometry.
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
int
|
|
FindMaxRects(tile, dinfo, mrd)
|
|
Tile *tile;
|
|
TileType dinfo; /* (unused) */
|
|
MaxRectsData *mrd;
|
|
{
|
|
Rect area;
|
|
Rect *rlist, *sr, *tmp;
|
|
int s, entries;
|
|
|
|
if (mrd->match != CLIENTDEFAULT)
|
|
if (TiGetClient(tile) == mrd->match)
|
|
return 0;
|
|
|
|
entries = 0;
|
|
TiToRect(tile, &area);
|
|
|
|
rlist = mrd->swap;
|
|
for (s = 0; s < mrd->entries; s++)
|
|
{
|
|
/* Watch out for (M)INFINITY values! */
|
|
|
|
sr = &(mrd->rlist[s]);
|
|
if (GEO_OVERLAP(sr, &area))
|
|
{
|
|
/* Top */
|
|
if (area.r_ytop < INFINITY - 2)
|
|
if (sr->r_ytop >= area.r_ytop + mrd->maxdist)
|
|
{
|
|
rlist[entries] = *sr;
|
|
rlist[entries].r_ybot = area.r_ytop;
|
|
entries++;
|
|
}
|
|
/* Bottom */
|
|
if (area.r_ybot > MINFINITY + 2)
|
|
if (sr->r_ybot <= area.r_ybot - mrd->maxdist)
|
|
{
|
|
rlist[entries] = *sr;
|
|
rlist[entries].r_ytop = area.r_ybot;
|
|
entries++;
|
|
}
|
|
/* Left */
|
|
if (area.r_xbot > MINFINITY + 2)
|
|
if (sr->r_xbot <= area.r_xbot - mrd->maxdist)
|
|
{
|
|
rlist[entries] = *sr;
|
|
rlist[entries].r_xtop = area.r_xbot;
|
|
entries++;
|
|
}
|
|
/* Right */
|
|
if (area.r_xtop < INFINITY - 2)
|
|
if (sr->r_xtop >= area.r_xtop + mrd->maxdist)
|
|
{
|
|
rlist[entries] = *sr;
|
|
rlist[entries].r_xbot = area.r_xtop;
|
|
entries++;
|
|
}
|
|
|
|
}
|
|
else
|
|
{
|
|
/* Copy sr to the new list */
|
|
rlist[entries] = *sr;
|
|
entries++;
|
|
}
|
|
|
|
/* If we have more rectangles than we allocated space for, */
|
|
/* double the list size and continue. */
|
|
|
|
if (entries > (mrd->listdepth - 4)) // was entries == mrd->listdepth
|
|
{
|
|
Rect *newrlist;
|
|
|
|
mrd->listdepth <<= 1; /* double the list size */
|
|
|
|
newrlist = (Rect *)mallocMagic(mrd->listdepth * sizeof(Rect));
|
|
memcpy((void *)newrlist, (void *)mrd->rlist,
|
|
(size_t)mrd->entries * sizeof(Rect));
|
|
// for (s = 0; s < entries; s++)
|
|
// newrlist[s] = mrd->rlist[s];
|
|
freeMagic(mrd->rlist);
|
|
mrd->rlist = newrlist;
|
|
|
|
newrlist = (Rect *)mallocMagic(mrd->listdepth * sizeof(Rect));
|
|
memcpy((void *)newrlist, (void *)mrd->swap,
|
|
(size_t)entries * sizeof(Rect));
|
|
// for (s = 0; s < entries; s++)
|
|
// newrlist[s] = mrd->swap[s];
|
|
freeMagic(mrd->swap);
|
|
mrd->swap = newrlist;
|
|
|
|
rlist = mrd->swap;
|
|
}
|
|
}
|
|
|
|
/* Sort areas and remove areas enclosed by other areas */
|
|
/* Is this routine too time-consuming (short answer: yes)? */
|
|
|
|
/*
|
|
for (s = 0; s < entries - 1; s++)
|
|
{
|
|
int r, t;
|
|
for (t = s + 1, r = 0; t < entries; t++)
|
|
{
|
|
if (GEO_SURROUND(&rlist[t], &rlist[s]))
|
|
{
|
|
rlist[s] = rlist[t];
|
|
r++;
|
|
}
|
|
else if (GEO_SURROUND(&rlist[s], &rlist[t]))
|
|
r++;
|
|
else if (r > 0)
|
|
rlist[t - r] = rlist[t];
|
|
}
|
|
entries -= r;
|
|
}
|
|
*/
|
|
|
|
/* copy rlist back to mrd by swapping "rlist" and "swap" */
|
|
mrd->entries = entries;
|
|
tmp = mrd->rlist;
|
|
mrd->rlist = rlist;
|
|
mrd->swap = tmp;
|
|
|
|
if (entries > 0)
|
|
return 0; /* keep the search going */
|
|
else
|
|
return 1; /* no more max size areas; stop the search */
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* FindMaxRectangle ---
|
|
*
|
|
* This is a general-purpose routine to be called from anywhere
|
|
* that expands an area to the largest area rectangle containing
|
|
* tiles connected to the given types list. It can be called, for
|
|
* example, from the router code to expand a point label into the
|
|
* maximum size rectangular terminal.
|
|
*
|
|
* If expandtypes is NULL, then searching is done over tiles that
|
|
* match by the ClientData record instead of types.
|
|
*
|
|
* Results:
|
|
* Pointer to a rectangle containing the maximum size area found.
|
|
* This pointer should not be deallocated!
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
Rect *
|
|
FindMaxRectangle(bbox, startpoint, plane, expandtypes)
|
|
Rect *bbox; /* bounding box of area searched */
|
|
Point *startpoint;
|
|
Plane *plane; /* plane of types to expand */
|
|
TileTypeBitMask *expandtypes; /* types to expand in */
|
|
{
|
|
MaxRectsData *mrd;
|
|
Tile *starttile;
|
|
TileType tt;
|
|
int rectArea;
|
|
int maxarea = 0;
|
|
int s, sidx = -1;
|
|
|
|
/* Find tile in def that surrounds or touches startpoint */
|
|
starttile = PlaneGetHint(plane);
|
|
GOTOPOINT(starttile, startpoint);
|
|
mrd = genCanonicalMaxwidth(bbox, starttile, plane, NULL);
|
|
|
|
/* Return only the largest rectangle found */
|
|
|
|
for (s = 0; s < mrd->entries; s++)
|
|
{
|
|
rectArea = (mrd->rlist[s].r_xtop - mrd->rlist[s].r_xbot) *
|
|
(mrd->rlist[s].r_ytop - mrd->rlist[s].r_ybot);
|
|
if (rectArea > maxarea)
|
|
{
|
|
maxarea = rectArea;
|
|
sidx = s;
|
|
}
|
|
}
|
|
|
|
if (sidx < 0)
|
|
{
|
|
Rect origrect;
|
|
|
|
TiToRect(starttile, &origrect);
|
|
sidx = 0;
|
|
mrd->rlist[0] = origrect;
|
|
}
|
|
return &(mrd->rlist[sidx]);
|
|
}
|
|
|
|
/*
|
|
*-------------------------------------------------------------------------
|
|
*
|
|
* FindMaxRectangle2 ---
|
|
*
|
|
* This routine differs from FindMaxRectangle in passing a starting
|
|
* tile to the routine.
|
|
*
|
|
* Results:
|
|
* Pointer to a rectangle containing the maximum size area found.
|
|
* This pointer should not be deallocated!
|
|
*
|
|
*-------------------------------------------------------------------------
|
|
*/
|
|
|
|
Rect *
|
|
FindMaxRectangle2(bbox, starttile, plane, expandtypes)
|
|
Rect *bbox; /* bounding box of area searched */
|
|
Tile *starttile; /* use this tile to start */
|
|
Plane *plane; /* plane of types to expand */
|
|
TileTypeBitMask *expandtypes; /* types to expand in, may be NULL */
|
|
{
|
|
MaxRectsData *mrd;
|
|
TileType tt;
|
|
int rectArea;
|
|
int maxarea = 0;
|
|
int s, sidx = -1;
|
|
|
|
/* Find tile in def that surrounds or touches startpoint */
|
|
mrd = genCanonicalMaxwidth(bbox, starttile, plane, expandtypes);
|
|
|
|
/* Return only the largest rectangle found */
|
|
|
|
for (s = 0; s < mrd->entries; s++)
|
|
{
|
|
rectArea = (mrd->rlist[s].r_xtop - mrd->rlist[s].r_xbot) *
|
|
(mrd->rlist[s].r_ytop - mrd->rlist[s].r_ybot);
|
|
if (rectArea > maxarea)
|
|
{
|
|
maxarea = rectArea;
|
|
sidx = s;
|
|
}
|
|
}
|
|
|
|
if (sidx < 0)
|
|
{
|
|
Rect origrect;
|
|
|
|
TiToRect(starttile, &origrect);
|
|
sidx = 0;
|
|
mrd->rlist[0] = origrect;
|
|
}
|
|
return &(mrd->rlist[sidx]);
|
|
}
|
|
|