#define LARGE_COORDINATE 1000000
#define SMALL_COORDINATE -LARGE_COORDINATE
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include "Xlibint.h"
#include "Xutil.h"
#include <X11/Xregion.h>
#include "poly.h"
static void
InsertEdgeInET(
EdgeTable *ET,
EdgeTableEntry *ETE,
int scanline,
ScanLineListBlock **SLLBlock,
int *iSLLBlock)
{
register EdgeTableEntry *start, *prev;
register ScanLineList *pSLL, *pPrevSLL;
ScanLineListBlock *tmpSLLBlock;
pPrevSLL = &ET->scanlines;
pSLL = pPrevSLL->next;
while (pSLL && (pSLL->scanline < scanline))
{
pPrevSLL = pSLL;
pSLL = pSLL->next;
}
if ((!pSLL) || (pSLL->scanline > scanline))
{
if (*iSLLBlock > SLLSPERBLOCK-1)
{
tmpSLLBlock =
(ScanLineListBlock *)Xmalloc(sizeof(ScanLineListBlock));
(*SLLBlock)->next = tmpSLLBlock;
tmpSLLBlock->next = (ScanLineListBlock *)NULL;
*SLLBlock = tmpSLLBlock;
*iSLLBlock = 0;
}
pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
pSLL->next = pPrevSLL->next;
pSLL->edgelist = (EdgeTableEntry *)NULL;
pPrevSLL->next = pSLL;
}
pSLL->scanline = scanline;
prev = (EdgeTableEntry *)NULL;
start = pSLL->edgelist;
while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
{
prev = start;
start = start->next;
}
ETE->next = start;
if (prev)
prev->next = ETE;
else
pSLL->edgelist = ETE;
}
static void
CreateETandAET(
register int count,
register XPoint *pts,
EdgeTable *ET,
EdgeTableEntry *AET,
register EdgeTableEntry *pETEs,
ScanLineListBlock *pSLLBlock)
{
register XPoint *top, *bottom;
register XPoint *PrevPt, *CurrPt;
int iSLLBlock = 0;
int dy;
if (count < 2) return;
AET->next = (EdgeTableEntry *)NULL;
AET->back = (EdgeTableEntry *)NULL;
AET->nextWETE = (EdgeTableEntry *)NULL;
AET->bres.minor_axis = SMALL_COORDINATE;
ET->scanlines.next = (ScanLineList *)NULL;
ET->ymax = SMALL_COORDINATE;
ET->ymin = LARGE_COORDINATE;
pSLLBlock->next = (ScanLineListBlock *)NULL;
PrevPt = &pts[count-1];
while (count--)
{
CurrPt = pts++;
if (PrevPt->y > CurrPt->y)
{
bottom = PrevPt, top = CurrPt;
pETEs->ClockWise = 0;
}
else
{
bottom = CurrPt, top = PrevPt;
pETEs->ClockWise = 1;
}
if (bottom->y != top->y)
{
pETEs->ymax = bottom->y-1;
dy = bottom->y - top->y;
BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
if (PrevPt->y > ET->ymax)
ET->ymax = PrevPt->y;
if (PrevPt->y < ET->ymin)
ET->ymin = PrevPt->y;
pETEs++;
}
PrevPt = CurrPt;
}
}
static void
loadAET(
register EdgeTableEntry *AET,
register EdgeTableEntry *ETEs)
{
register EdgeTableEntry *pPrevAET;
register EdgeTableEntry *tmp;
pPrevAET = AET;
AET = AET->next;
while (ETEs)
{
while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
{
pPrevAET = AET;
AET = AET->next;
}
tmp = ETEs->next;
ETEs->next = AET;
if (AET)
AET->back = ETEs;
ETEs->back = pPrevAET;
pPrevAET->next = ETEs;
pPrevAET = ETEs;
ETEs = tmp;
}
}
static void
computeWAET(
register EdgeTableEntry *AET)
{
register EdgeTableEntry *pWETE;
register int inside = 1;
register int isInside = 0;
AET->nextWETE = (EdgeTableEntry *)NULL;
pWETE = AET;
AET = AET->next;
while (AET)
{
if (AET->ClockWise)
isInside++;
else
isInside--;
if ((!inside && !isInside) ||
( inside && isInside))
{
pWETE->nextWETE = AET;
pWETE = AET;
inside = !inside;
}
AET = AET->next;
}
pWETE->nextWETE = (EdgeTableEntry *)NULL;
}
static int
InsertionSort(
register EdgeTableEntry *AET)
{
register EdgeTableEntry *pETEchase;
register EdgeTableEntry *pETEinsert;
register EdgeTableEntry *pETEchaseBackTMP;
register int changed = 0;
AET = AET->next;
while (AET)
{
pETEinsert = AET;
pETEchase = AET;
while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
pETEchase = pETEchase->back;
AET = AET->next;
if (pETEchase != pETEinsert)
{
pETEchaseBackTMP = pETEchase->back;
pETEinsert->back->next = AET;
if (AET)
AET->back = pETEinsert->back;
pETEinsert->next = pETEchase;
pETEchase->back->next = pETEinsert;
pETEchase->back = pETEinsert;
pETEinsert->back = pETEchaseBackTMP;
changed = 1;
}
}
return(changed);
}
static void
FreeStorage(
register ScanLineListBlock *pSLLBlock)
{
register ScanLineListBlock *tmpSLLBlock;
while (pSLLBlock)
{
tmpSLLBlock = pSLLBlock->next;
Xfree((char *)pSLLBlock);
pSLLBlock = tmpSLLBlock;
}
}
static int PtsToRegion(
register int numFullPtBlocks,
register int iCurPtBlock,
POINTBLOCK *FirstPtBlock,
REGION *reg)
{
register BOX *rects;
register XPoint *pts;
register POINTBLOCK *CurPtBlock;
register int i;
register BOX *extents;
register int numRects;
BOX *prevRects = reg->rects;
extents = ®->extents;
numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
if (!(reg->rects = (BOX *)Xrealloc((char *)reg->rects,
(unsigned) (sizeof(BOX) * numRects)))) {
Xfree(prevRects);
return(0);
}
reg->size = numRects;
CurPtBlock = FirstPtBlock;
rects = reg->rects - 1;
numRects = 0;
extents->x1 = MAXSHORT, extents->x2 = MINSHORT;
for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
i = NUMPTSTOBUFFER >> 1;
if (!numFullPtBlocks)
i = iCurPtBlock >> 1;
for (pts = CurPtBlock->pts; i--; pts += 2) {
if (pts->x == pts[1].x)
continue;
if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
pts[1].x == rects->x2 &&
(numRects == 1 || rects[-1].y1 != rects->y1) &&
(i && pts[2].y > pts[1].y)) {
rects->y2 = pts[1].y + 1;
continue;
}
numRects++;
rects++;
rects->x1 = pts->x; rects->y1 = pts->y;
rects->x2 = pts[1].x; rects->y2 = pts[1].y + 1;
if (rects->x1 < extents->x1)
extents->x1 = rects->x1;
if (rects->x2 > extents->x2)
extents->x2 = rects->x2;
}
CurPtBlock = CurPtBlock->next;
}
if (numRects) {
extents->y1 = reg->rects->y1;
extents->y2 = rects->y2;
} else {
extents->x1 = 0;
extents->y1 = 0;
extents->x2 = 0;
extents->y2 = 0;
}
reg->numRects = numRects;
return(TRUE);
}
Region
XPolygonRegion(
XPoint *Pts,
int Count,
int rule)
{
Region region;
register EdgeTableEntry *pAET;
register int y;
register int iPts = 0;
register EdgeTableEntry *pWETE;
register ScanLineList *pSLL;
register XPoint *pts;
EdgeTableEntry *pPrevAET;
EdgeTable ET;
EdgeTableEntry AET;
EdgeTableEntry *pETEs;
ScanLineListBlock SLLBlock;
int fixWAET = FALSE;
POINTBLOCK FirstPtBlock, *curPtBlock;
POINTBLOCK *tmpPtBlock;
int numFullPtBlocks = 0;
if (! (region = XCreateRegion())) return (Region) NULL;
pts = Pts;
if (((Count == 4) ||
((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
(((pts[0].y == pts[1].y) &&
(pts[1].x == pts[2].x) &&
(pts[2].y == pts[3].y) &&
(pts[3].x == pts[0].x)) ||
((pts[0].x == pts[1].x) &&
(pts[1].y == pts[2].y) &&
(pts[2].x == pts[3].x) &&
(pts[3].y == pts[0].y)))) {
region->extents.x1 = min(pts[0].x, pts[2].x);
region->extents.y1 = min(pts[0].y, pts[2].y);
region->extents.x2 = max(pts[0].x, pts[2].x);
region->extents.y2 = max(pts[0].y, pts[2].y);
if ((region->extents.x1 != region->extents.x2) &&
(region->extents.y1 != region->extents.y2)) {
region->numRects = 1;
*(region->rects) = region->extents;
}
return(region);
}
if (Count < 2) return region;
if (! (pETEs = (EdgeTableEntry *)
Xmalloc((unsigned) (sizeof(EdgeTableEntry) * Count)))) {
XDestroyRegion(region);
return (Region) NULL;
}
pts = FirstPtBlock.pts;
CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
pSLL = ET.scanlines.next;
curPtBlock = &FirstPtBlock;
if (rule == EvenOddRule) {
for (y = ET.ymin; y < ET.ymax; y++) {
if (pSLL != NULL && y == pSLL->scanline) {
loadAET(&AET, pSLL->edgelist);
pSLL = pSLL->next;
}
pPrevAET = &AET;
pAET = AET.next;
while (pAET) {
pts->x = pAET->bres.minor_axis, pts->y = y;
pts++, iPts++;
if (iPts == NUMPTSTOBUFFER) {
tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
curPtBlock->next = tmpPtBlock;
curPtBlock = tmpPtBlock;
pts = curPtBlock->pts;
numFullPtBlocks++;
iPts = 0;
}
EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
}
(void) InsertionSort(&AET);
}
}
else {
for (y = ET.ymin; y < ET.ymax; y++) {
if (pSLL != NULL && y == pSLL->scanline) {
loadAET(&AET, pSLL->edgelist);
computeWAET(&AET);
pSLL = pSLL->next;
}
pPrevAET = &AET;
pAET = AET.next;
pWETE = pAET;
while (pAET) {
if (pWETE == pAET) {
pts->x = pAET->bres.minor_axis, pts->y = y;
pts++, iPts++;
if (iPts == NUMPTSTOBUFFER) {
tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
curPtBlock->next = tmpPtBlock;
curPtBlock = tmpPtBlock;
pts = curPtBlock->pts;
numFullPtBlocks++; iPts = 0;
}
pWETE = pWETE->nextWETE;
}
EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
}
if (InsertionSort(&AET) || fixWAET) {
computeWAET(&AET);
fixWAET = FALSE;
}
}
}
FreeStorage(SLLBlock.next);
(void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
tmpPtBlock = curPtBlock->next;
Xfree((char *)curPtBlock);
curPtBlock = tmpPtBlock;
}
Xfree((char *)pETEs);
return(region);
}