Here's some REALLY OLD fossilized code I wrote years ago to test a poly
filling algorithm. This code can be compiled by the old MS DOS (C 8.0)
compiler. It works DIRECTLY on an old DOS text screen, using the screen
memory address as a 80x25 array in which to draw the polygon and fill it.
If compiled, the program would probably work in a DOS Windows under Windows
9x.
The program expects you to move the cursor around, and enter each vertex of
the polygon (by pressing space). When done, you hit return, and the code
will draw the polygon using Bresenham lines. Then when you hit return
again, the code will attempt to fill the polygon.
Even though this code is written for a DOS text screen, the general line
drawing and polygon filling code should be portable without too much effort
(just yank out all the DOS junk). I don't think this code is recursive, so
it should be relatively Palm-friendly.
Doug.
-------------------- POLYFILL.C --------------------
#include <stdio.h>
#include <stdlib.h>
#include <bios.h>
#ifndef XMAX
#define XMAX 80
#endif
#ifndef YMAX
#define YMAX 25
#endif
#define VMAX 20
#define VRAM(x,y) (*vram)[y][x].chr
struct coord
{
int x;
int y;
} vc[VMAX];
typedef struct
{
char chr;
char att;
} VRam[YMAX][XMAX];
VRam far *vram = (VRam far *)0xb8000000;
void DrawLine(unsigned, unsigned, unsigned, unsigned, char);
unsigned GetCoord(unsigned *, unsigned *, char);
unsigned FillThatSucker(char);
void NodeDegreeInLAG(int *, int *, unsigned *, unsigned *);
void FillVram(char, unsigned);
void PutCursor(unsigned, unsigned);
unsigned Kybd(void);
int main(int argc, char *argv[])
{
int i, v;
unsigned ret;
char chr;
argc, argv;
while (1)
{
FillVram(' ', 0x07);
PutCursor(0, 0);
vc[0].x = vc[0].y = 0;
for (v = 0, chr = '0'; v < VMAX; v++)
{
if (v)
{
vc[v].x = vc[v-1].x;
vc[v].y = vc[v-1].y;
}
if (!(ret = GetCoord(&vc[v].x, &vc[v].y, chr)))
break;
if (ret == 13)
{
vc[v].x = vc[0].x;
vc[v].y = vc[0].y;
break;
}
chr += (chr == '9') ? (char)8 : (char)1;
}
if (!ret) break;
if (v < 3) continue;
for (i = 0; i < v; i++)
DrawLine(vc[i].x, vc[i].y, vc[i+1].x, vc[i+1].y,
'*');
if (Kybd() == 0x011b) break;
FillThatSucker('+');
if (Kybd() == 0x011b) break;
}
return (0);
}
void DrawLine(unsigned x1, unsigned y1, unsigned x2, unsigned y2, char chr)
{
unsigned x0, y0;
int dx, dy;
int i, Yadj, Err, Eadj, Ecor;
x0 = x1, y0 = y1;
dx = x2-x1, dy = y2-y1;
if (dx < 0)
{
dx = -dx;
dy = -dy;
x0 = x2, y0 = y2;
}
Yadj = 1;
if (dy < 0)
{
dy = -dy;
Yadj = -1;
}
if (dx < dy)
{ // scan y
Ecor = 2*dy;
Eadj = 2*dx;
Err = Eadj-dy;
for (i = 0; i <= dy; i++)
{
VRAM(x0,y0) = chr;
if (Err >= 0)
{
Err -= Ecor;
x0++;
}
Err += Eadj;
y0 += Yadj;
}
}
else
{ // scan x
Ecor = 2*dx;
Eadj = 2*dy;
Err = Eadj-dx;
for (i = 0; i <= dx; i++)
{
VRAM(x0,y0) = chr;
if (Err >= 0)
{
Err -= Ecor;
y0 += Yadj;
}
Err += Eadj;
x0++;
}
}
}
unsigned GetCoord(unsigned *xc, unsigned *yc, char chr)
{
unsigned key;
while ((key = Kybd() >> 8 & 0xff) != 0x01)
{
switch (key)
{
case 0x39: // Space
VRAM(*xc,*yc) = chr;
return (' ');
case 0x1c: // Return
return (13);
case 0x48: // Up
if ((*yc)-- == 0)
*yc = YMAX-1;
break;
case 0x50: // Down
if (++(*yc) >= YMAX)
*yc = 0;
break;
case 0x4b: // Left
if ((*xc)-- == 0)
*xc = XMAX-1;
break;
case 0x4d: // Right
if (++(*xc) >= XMAX)
*xc = 0;
break;
default:
break;
}
PutCursor(*xc, *yc);
}
return (0);
}
unsigned FillThatSucker(char chr)
{
int xf, yf;
unsigned ContourCount, above, below, ErrorFlag;
ErrorFlag = 0;
for (yf = 0; yf < YMAX; yf++)
{
ContourCount = 0;
xf = 0;
while (xf < XMAX) // XMAX could be backscanned
to avoid *++++++** *+++++++|
{
if (VRAM(xf,yf) == '*')
{
NodeDegreeInLAG(&xf, &yf, &above, &below);
if ((above == 1) && (below == 1))
ContourCount++;
if ((above+below) & 0xfffd) //
a+b == 0 or 2 else error
{
(*vram)[yf][xf-1].att = 0x0c;
// ??? ContourCount = 0;
// Force outside (looks better)
ErrorFlag++;
}
}
else
{
if (ContourCount & 0x0001)
// odd therefore inside
VRAM(xf,yf) = chr;
xf++;
}
}
}
return (ErrorFlag);
}
void NodeDegreeInLAG(int *xf, int *yf, unsigned *above, unsigned *below)
{
*above = *below = 0;
if (VRAM(*xf-1,*yf-1) == '*') (*above)++;
if (VRAM(*xf-1,*yf+1) == '*') (*below)++;
while (VRAM(*xf,*yf) == '*')
{
if ( (VRAM(*xf,*yf-1) == '*') && (VRAM(*xf-1,*yf-1) != '*')
) (*above)++;
if ( (VRAM(*xf,*yf+1) == '*') && (VRAM(*xf-1,*yf+1) != '*')
) (*below)++;
(*xf)++;
}
if ( (VRAM(*xf,*yf-1) == '*') && (VRAM(*xf-1,*yf-1) != '*') )
(*above)++;
if ( (VRAM(*xf,*yf+1) == '*') && (VRAM(*xf-1,*yf+1) != '*') )
(*below)++;
}
void FillVram(char chr, unsigned atr)
{
int i, j;
for (j = 0; j < YMAX; j++)
for (i = 0; i < XMAX; i++)
{
VRAM(i,j) = chr;
(*vram)[j][i].att = (char)atr;
}
}
void PutCursor(unsigned x, unsigned y)
{
union REGS Reg;
Reg.x.ax = 0x0200;
Reg.x.bx = 0x0000;
Reg.x.dx = (y << 8) | x;
int86(0x10, &Reg, &Reg);
}
unsigned Kybd(void)
{
return (_bios_keybrd(_KEYBRD_READ));
}
----------------------------------------
--
For information on using the Palm Developer Forums, or to unsubscribe, please see
http://www.palmos.com/dev/tech/support/forums/
