Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!bloom-beacon!apple!bionet!agate!ucbvax!decwrl!sun!pitstop!sundc!seismo!uunet!mcvax!hp4nl!mhres!hst
From: hst@mhres.mh.nl (Klaas Hemstra)
Newsgroups: comp.graphics
Subject: Re: 2-D clipping
Summary: An integer clipline routine
Keywords: integer algorithms
Message-ID: <2462@mhres.mh.nl>
Date: 6 Oct 88 09:36:45 GMT
References: <5760@utah-cs.UUCP>
Reply-To: hst@mhres.mh.nl (Klaas Hemstra)
Organization: Multihouse N.V., The Netherlands
Lines: 172

Included is the source of a clip_line routine I wroten recently.

The coordinates may be "int"egers or "long"s, and both positive and negative.
Also the ranges to clip the coordinates in can be in the negative range of
an int or long.

I hope this is useful to you and maybe to others too,

				    Klaas Hemstra


File: clip_line.c
---------------------------------------------------------------------------
/* This file contains routines to clip a line into a specified border   */
/*									*/
/*  Made By  K.Hemstra  it's in the Public Domain  Use at your own risk */

/* All computations are done with integer arithmetic.
/* The only restrictions are that the border to clip the line into can not  */
/* have a height or width larger then the square root of the largest long,  */
/*  and for a line (x1,y1) - (x2,y2) to clip: abs(x2 - x1) * abs(y2 - y1),  */
/*   may not exceed the largest long.					    */

/* So for C-implementations with int = 16 bits and long = 32 bits the       */
/* largest "clip"-box can be 32767x32767 coordinates.		      */

/* The border is defined by the two points (minx,miny) and (maxx,maxy) */
/* All comment if based on the following graph */
/*

			   Above the border
	(minx,miny)  *--------------------------*
		     |			        |
Left of the border   |	Within the border       | Right of the border
		     |			        |
		     *--------------------------* (maxx,maxy)
			   Below the border

*/


#typedef int COOR

/* COORdinate type: This can be int or long.
    The routine will work ok in both cases.
    However it is best too choose "int" if the coordinates allow it, because
    "int"s are faster on some machines, specially 16-bits like MS-DOS.
Note:    For Turbo-C the #typedef will not work.
	Use "#define COOR int" instead, it works fine.
*/



COOR    minx = 0,maxx = 719;	/* initialized to hercules screen */
COOR    miny = 0,maxy = 347;
COOR    imaxx = 719,imaxy = 347;


/* This routine is should be called to initialize the border
    The clip_line routine will "clip" the line into (x1,y1) - (x2,y2)  */

int set_clip_borders(x1,y1,x2,y2)
COOR    x1,y1,x2,y2;
{
    minx = x1, miny = y1, maxx = x2, maxy = y2;
    imaxx = maxx - minx;
    imaxy = maxy - miny;
}


/* The clip_line routine */

int clip_line(x1,y1,x2,y2)
COOR x1,y1,x2,y2;
{
    if (clip_coordinates(&x1,&y1,&x2,&y2) != 0)
    {

/* Here the machine specific line drawing routine is called */

	draw_line(x1,y1,x2,y2);

    }
}



/* The clip_coordinates routine must be called with four addresses to
    COORdinates.
   These COORdinates are changed to fall into the range
	(minx,miny) - (maxx,maxy)
   If the line will not be within the defined border the returned
    integer value will be 1.
*/

int clip_coordinates(ix1,iy1,ix2,iy2)
COOR *ix1,*iy1,*ix2,*iy2;
{
    COOR	x1,y1,x2,y2;
    long	dx,dy,temp;
    long	signdy;

    if (ix2 < ix1)	    /* Always make (x1,y1) the most left point */
	x1 = *ix2 -minx, y1 = *iy2 -miny, x2 = *ix1 -minx, y2 = *iy1 -miny;
    else
	x1 = *ix1 -minx, y1 = *iy1 -miny, x2 = *ix2 -minx, y2 = *iy2 -miny;

	/* Now the coordinates x1,y1,x2,y2 are relatife to (0,0) */
	/*    which is the upper left corner of the border	 */


	/* If line is completely left or right of the border      */

    if ((x2 < 0) || (x1 > imaxx))
	return 1;

	/* If line is completely above or below the border */
    if (((y1 < 0) && (y2 < 0)) || ((y1 > imaxy) && (y2 > imaxy)))
	return 1;

    /* Ok , the line is (maybe partly) in the border, work to do */

    /* Ok, The line is partly above or below border (or both) */
    dx = (x2 - x1);	    /* Distance between two x values */
    dy = abs(y2 - y1);	/* Distance between two y values */
    signdy = (((y2 - y1) < 0) ? -1 : 1);    /* sign of y2-y1 */

	    /* If y1 lies above border then correct */
    if (y1 < 0)
    {    x1 += ((long)dx * (long)(- y1)) / (long) dy;
	y1 = 0;
    }
	/* If y1 lies below border then correct */
    if (y1 > imaxy)
    {    x1 += ((long)dx * (long)(y1 - imaxy)) / (long) dy;
	y1 = imaxy;
    }
	/* If y2 lies above border then correct */
    if (y2 < 0)
    {    x2 -= ((long)dx * (long)(- y2)) / (long) dy;
	y2 = 0;
    }
	/* If y1 lies below border then correct */
    if (y2 > imaxy)
    {    x2 -= ((long)dx * (long)(y2 - imaxy)) / (long) dy;
	y2 = imaxy;
    }

	/* If x1 lies left of border then correct */
    if (x1 < 0)
    {    y1 += signdy * (((long)dy * (long)(- x1)) / (long) dx);
	x1 = 0;
    }
	/* If x2 lies right of border then correct */
    if (x2 > imaxx)
    {    y2 -= signdy * (((long)dy * (long)(x2 - imaxx)) / (long) dx);
	x2 = imaxx;
    }
	/* If line now is completely above or below the border */
    if ((y1 < 0) || (y2 < 0) || (y1 > imaxy) || (y2 > imaxy))
	return 1;

    *ix1 = x1+minx, *iy1 = y1+miny, *ix2 = x2+minx, *iy2 = y2+miny;
    return 0;
}
----------------------------------End of file clip_line.c


-- 
Klaas Hemstra  (hst@mh.nl)                   |    /  / ,~~~  ~~/~~
uucp: ..{uunet!}mcvax!mh.nl!hst              |   /--/  `-,    /  ___  |_/ |__|
Multihouse N.V., Gouda, the Netherlands      |  /  / ___/    /   ---  | \ |  |