/* quick point/polygon intersection */

#include "exec/types.h"
#include "intuition/intuition.h"

#include <macros.h>

struct Library *IntuitionBase=NULL, *GfxBase=NULL;
void *OpenLibrary();

struct Window *Window=NULL, *OpenWindow();
struct Screen *Screen=NULL, *OpenScreen();
struct ViewPort *vp;							/* view port */
struct RastPort *rp;							/* rast port */

USHORT colors[8] = { 0x007,0x00C,0xFFF,0x00F,0x407,0xFFF,0x33F,0xF00 };

struct NewScreen NewScreen = { 0,0,320,200, 3, 0,1, NULL, CUSTOMSCREEN, };

struct NewWindow back_ground =
{	0,0,320,200, 0,1,
	MENUPICK | MOUSEMOVE | MOUSEBUTTONS,
	NOCAREREFRESH | ACTIVATE | SMART_REFRESH | BORDERLESS | REPORTMOUSE,
	NULL,NULL,NULL,NULL,NULL,320,200,320,200,CUSTOMSCREEN,
};

#define DF1	ITEMTEXT | ITEMENABLED | HIGHCOMP
#define DF3	ITEMTEXT | ITEMENABLED | HIGHCOMP | COMMSEQ
#define DF4	ITEMTEXT | ITEMENABLED | HIGHCOMP | COMMSEQ | CHECKIT

struct IntuiText
	addp_tx = { 18,1,JAM2,4,1,NULL,(UBYTE *)"Add Points" },
	movp_tx = { 18,1,JAM2,4,1,NULL,(UBYTE *)"Move Points" },
	delp_tx = { 18,1,JAM2,4,1,NULL,(UBYTE *)"Delete Points" };
struct MenuItem
	addp_mi = { NULL	,0,00,150,10,DF4|CHECKED,0xB,(APTR)&addp_tx,0,'A' },
	movp_mi = { &addp_mi,0,10,150,10,DF4,        0xD,(APTR)&movp_tx,0,'M' },
	delp_mi = { &movp_mi,0,20,150,10,DF4,        0xE,(APTR)&delp_tx,0,'D' };
struct Menu menu2 =
	{	NULL, 100,0,56,10, MENUENABLED | MIDRAWN, "Edit", &delp_mi };

struct IntuiText
	abou_tx = { 5,1,JAM2,4,1,NULL,(UBYTE *)"By David Joiner" },
	svex_tx = { 5,1,JAM2,4,1,NULL,(UBYTE *)"Save and Exit" },
	quit_tx = { 5,1,JAM2,4,1,NULL,(UBYTE *)"Exit, No Save" };
struct MenuItem
	abou_mi = { NULL	,0,00,150,10,DF1,0,(APTR)&abou_tx       },
	svex_mi = { &abou_mi,0,10,150,10,DF3,0,(APTR)&svex_tx,0,'S' },
	quit_mi = { &svex_mi,0,20,150,10,DF3,0,(APTR)&quit_tx,0,'X' };
struct Menu menu1 =
	{	&menu2, 1,0,56,10, MENUENABLED | MIDRAWN, "File", &quit_mi };

#define ADD_POINTS		(addp_mi.Flags & CHECKED)
#define MOVE_POINTS		(movp_mi.Flags & CHECKED)
#define DEL_POINTS		(delp_mi.Flags & CHECKED)

#define SCAT	goto exit_pgm;

struct XY {
	long	x,y;
};

#define NUMPOINTS	13

struct XY points[] = {
	39,93, 75,51, 61,43, 140,43, 149,55, 176,45, 192,113, 151,74, 118,165,
	98,85, 101,129, 60,156, 47,156
};

short editcount = 0, dragpoint = -1;

short	delta_x, delta_y;

struct XY editpoints[50];

main()
{	if ((IntuitionBase = OpenLibrary("intuition.library",0)) == NULL) SCAT;
	if ((GfxBase = OpenLibrary("graphics.library",0)) == NULL) SCAT;
	if ((Screen = OpenScreen(&NewScreen)) == NULL) SCAT;
	vp = &(Screen->ViewPort);
	LoadRGB4(vp,colors,8);

	back_ground.Screen = Screen;
	if ((Window = OpenWindow(&back_ground)) == NULL) SCAT;
	rp = Window->RPort;

	SetMenuStrip(Window,&menu1);

	SetAPen(rp,1);

	ptest();

	while (TRUE)
	{	ULONG class; USHORT code, length; SHORT mx, my; APTR address;
		struct IntuiMessage *message, *GetMsg();

		Wait(1 << Window->UserPort->mp_SigBit);

		while (message = GetMsg(Window->UserPort))
		{	class = message->Class;
			code = message->Code;
			address = (APTR)message->IAddress;
			mx = message->MouseX;
			my = message->MouseY;
			ReplyMsg(message);

			if (class == MENUPICK)
			{	if (code == MENUNULL) ;
				else if (MENUNUM(code)==0)
				{	switch (ITEMNUM(code)) {
					case 2: break;
					case 1: break;
					case 0: SCAT;
					}
				}
			}
			else if (class == MOUSEBUTTONS)
			{	if (code == SELECTDOWN)
				{	if (ADD_POINTS)
					{	/* number of points is zero, then define a point at
						the mouse click, and another one dragged by the mouse.
						If number of points is 1, then add a dragged one at
						the mouse click.
						else look for the nearest edge, and "break" it.
						*/
						if (editcount < 2)
						{	if (editcount == 0)
							{	editpoints[0].x = mx;
								editpoints[0].y = my;
							}
							SetAPen(rp,0);		/* erase existing poly */
							draw_poly();
							editpoints[1].x = mx;
							editpoints[1].y = my;
							editcount = 2;
							dragpoint = 1;
							shadow_poly();
						}
						else if (editcount < 50)
						{	short i, point;
						/*	point_test(mx,my); */

							point = find_edge(mx,my);
							if (point >= 0)
							{	SetAPen(rp,0);		/* erase existing poly */
								draw_poly();
								for (i= editcount; i>point; i--)
									editpoints[i] = editpoints[i-1];
								editpoints[point].x = mx;
								editpoints[point].y = my;
								editcount++;
								dragpoint = point;
								shadow_poly();
							}
						}
					}
					else if (MOVE_POINTS)
					{	short point;
						/* look for a point to move, mark as a dragger. */
						if ((point = find_point(mx,my)) >= 0)
						{	SetAPen(rp,0);		/* erase existing poly */
							draw_poly();
							shadow_poly();
							dragpoint = point;
						}
					}
					else if (DEL_POINTS)
					{	short point;

						/* look for a point to delete, re-draw */

						if ((point = find_point(mx,my)) >= 0)
						{	SetAPen(rp,0);		/* erase existing poly */
							draw_poly();
							while (point < editcount)
							{	editpoints[point] = editpoints[point+1];
								point++;
							}
							editcount--;
							SetAPen(rp,1);
							draw_poly();
						}
					}
				}
				else if (code == SELECTUP)
				{	if (dragpoint >= 0)
					{	shadow_poly();
						dragpoint = -1;
						SetAPen(rp,1);
						draw_poly();
					}
				}
			}
		}
		if (dragpoint >= 0)
		{	shadow_poly();
			editpoints[dragpoint].x = mx + delta_x;
			editpoints[dragpoint].y = my + delta_y;
			shadow_poly();
		}
	}
exit_pgm:
	if (Window){ ClearMenuStrip(Window); CloseWindow(Window); }
	if (Screen) CloseScreen(Screen);
	if (GfxBase) CloseLibrary(GfxBase);
	if (IntuitionBase) CloseLibrary(IntuitionBase);
}

int find_point(x,y) short x,y;
{	short dist = 10, newdist;
	short i, foundpoint = -1;

	for (i=0; i<editcount; i++)
	{	newdist = ABS(editpoints[i].x - x) + ABS(editpoints[i].y - y);

		if (newdist < dist)
		{	dist = newdist;
			foundpoint = i;
			delta_x = editpoints[i].x - x;
			delta_y = editpoints[i].y - y;
		}
	}
	return foundpoint;
}

int find_edge(x,y) short x,y;
{	short	newdist, dist = 10;
	short	foundline = -1, i;

	for (i=1; i<editcount; i++)
	{	newdist = line_dist(
			editpoints[i-1].x,editpoints[i-1].y,
			editpoints[i].x,editpoints[i].y,
			x,y);

		if (newdist < dist)
		{	dist = newdist;
			foundline = i;
		}
	}

	newdist = line_dist(
		editpoints[0].x,editpoints[0].y,
		editpoints[editcount-1].x,editpoints[editcount-1].y,
		x,y);

	if (newdist < dist)
	{	dist = newdist;
		foundline = 0;
	}
	return foundline;
}

shadow_poly()
{	SetDrMd(rp,COMPLEMENT);
	draw_poly();
	SetDrMd(rp,JAM1);
}

draw_poly()
{	short i;

	Move(rp,editpoints[0].x,editpoints[0].y);

	for (i=1; i<editcount; i++)
		Draw(rp,editpoints[i].x,editpoints[i].y);

	/* the condition allows us to not re-draw the same line when there is
		only 2 points. */

	if (editcount != 2) Draw(rp,editpoints[0].x,editpoints[0].y);
}

#if 0
point_test(x3,y3) short x3,y3;
{	short	x1 = editpoints[0].x,
			y1 = editpoints[0].y,
			x2 = editpoints[1].x,
			y2 = editpoints[1].y;
	long	x,y;

	short	a,b;

	long	aa,bb,ab;

	a = x2 - x1;
	b = y2 - y1;

	aa = a*a;
	bb = b*b;
	ab = a*b;

	x = (bb * x1 + aa * x3 + ab * (y3-y1)) / (bb+aa);
	y = (aa * y1 + bb * y3 + ab * (x3-x1)) / (bb+aa);
}
#endif

line_dist(x1,y1,x2,y2,mx,my) short x1,y1,x2,y2,mx,my;
{	long	x,y,t;

	short	a,b;

	long	aa,bb,ab;

	a = x2 - x1;
	b = y2 - y1;

	aa = a*a;
	bb = b*b;
	ab = a*b;

	x = (bb * x1 + aa * mx + ab * (my-y1)) / (bb+aa);
	y = (aa * y1 + bb * my + ab * (mx-x1)) / (bb+aa);

	if (x1 > x2) { t = x1; x1 = x2; x2 = t; }
	if (mx < x1 || mx > x2) return 100;

	if (y1 > y2) { t = y1; y1 = y2; y2 = t; }
	if (my < y1 || my > y2) return 100;

	return ABS(mx-x) + ABS(my-y);
}

ptest()
{	short i, x, y;

	Move(rp,points[0].x,points[0].y);

	for (i=0; i<NUMPOINTS-1; i++)
		Draw(rp,points[i+1].x,points[i+1].y);

	Draw(rp,points[0].x,points[0].y);

	for (x=35; x<200; x++)
	{	for (y=40; y<170; y++)
		{	if (point_in_poly(x,y))
				pixel(rp->BitMap,x,y,2);
		}
	}
}

point_in_poly(x,y) long x,y;
{	short			lleft=0;				/* lines to the left */
	register short	i,
					px,py,					/* current point */
					ox,oy;					/* previous point */

	/* we need to know if the point is to the left of an even number of lines. */

	i=0;									/* start at 0th vertex */
	px = points[0].x;						/* get current point */
	py = points[0].y;

	if (py > y) goto startbelow;			/* if below line then start below */
	/* Q: If we start on a horizontal line, what happens? */

startabove:
	ox = px;								/* set old point to current */
	oy = py;
	i++;									/* next vertex */
	if (i < NUMPOINTS)						/* if not last edge */
	{	px = points[i].x;					/* get new vertex */
		py = points[i].y;
	}
	else if (i == NUMPOINTS)				/* if last edge */
	{	px = points[0].x;					/* use first vertex */
		py = points[0].y;
	}
	else return lleft;						/* else if done, return */

	if (py <= y) goto startabove;			/* if still above, then loop */

	if (px < x)								/* if new point to the left */
	{	if (ox < x) lleft = !lleft;			/* and old one too, then mark */
		else								/* else within bounding box, do slope */
			if ( (px - ox)*(y - oy) < (py - oy)*(x - ox) ) lleft = !lleft;
	}
	else
	{	if ((ox < x) &&						/* else if within bound box, slope calc */
			(px - ox)*(y - oy) < (py - oy)*(x - ox) ) lleft = !lleft;
	}
/*	goto startbelow;	*/					/* next line starts below point */

startbelow:
	ox = px;								/* set old point to current */
	oy = py;
	i++;									/* next vertex */
	if (i < NUMPOINTS)						/* if not last edge */
	{	px = points[i].x;					/* get new vertex */
		py = points[i].y;
	}
	else if (i == NUMPOINTS)				/* if last edge */
	{	px = points[0].x;					/* use first vertex */
		py = points[0].y;
	}
	else return lleft;						/* else if done, return */

	if (py > y) goto startbelow;			/* if still below, then loop */

	if (px < x)								/* if new point to the left */
	{	if (ox < x) lleft = !lleft;			/* and old one, then it's left */
		else								/* else it's in bounds, do slope calc */
			if ( (px - ox)*(y - oy) > (py - oy)*(x - ox) ) lleft = !lleft;
	}
	else		/* if it's in the bounds, do slope calc */
	{	if (ox < x && (px - ox)*(y - oy) > (py - oy)*(x - ox) ) lleft = !lleft;
	}
	goto startabove;
}

#asm

; pixel(bitmap,x,y,color); - parameters at 4, 8, 12, 16

BMWidth			equ	0		; bit map width
BMRows			equ	2		; bit map height
BMFlags			equ	4		; bit map flags
BMDepth			equ	5		; bit map depth
BMPlanes		equ	8		; bit map planes

BMAP			equ	4		; bit map param
XC				equ	8+2
YC				equ	12+2
COLOR			equ	16+2

		public	_pixel
_pixel
		move.l	BMAP(sp),a0			; address of bit map
		move.w	YC(sp),d1			; y coord (word)

		mulu.w	BMWidth(a0),d1		; y * width in bytes
		move.w	XC(sp),d0			; x coord
		lsr.w	#3,d0				; x / 8
		add.w	d0,d1

		move.w	XC(sp),d0			; x coord
		not.w	d0
		and.w	#7,d0				; x & 7 = x mod 8
		move.w	COLOR(sp),d2		; color

		clr.w	d3					; clear upper byte of low word
		move.b	BMDepth(a0),d3		; do (depth) times
		lea		BMPlanes(a0),a0
		bra		3$

1$		move.l	(a0)+,a1			; get nth bit plane address
		lsr.w	#1,d2				; shift color by 1 bit
		bcc.s	2$

		bset	d0,(a1,d1.w)		; set the bit
		dbra	d3,1$
		rts

2$		bclr	d0,(a1,d1.w)		; clear the bit
3$		dbra	d3,1$
		rts

#endasm