From:	tom burgess <tburgess AT drao DOT nrc DOT ca>
Newsgroups:	comp.os.msdos.djgpp
Subject:	Re: ALLEGRO : check for Line intersecting a point . . . how?
Date:	Sat, 23 Aug 1997 20:22:45 -0700
Organization:	BCTEL Advanced Communications
Lines:	65
Message-ID:	<33FFA905.2F11@drao.nrc.ca>
References:	<33f340d2 DOT 7053399 AT news DOT btinternet DOT com> <33F38369 DOT 606CE0E9 AT spectra DOT net> <33FE7B69 DOT 669 AT drao DOT nrc DOT ca>
NNTP-Posting-Host:	pntn02m02-101.bctel.ca
Mime-Version:	1.0
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp

tom burgess wrote:
> 
(some silly stuff)
Someone was kind enough to point out that my beautiful algorithm was
not going to work. I had hoped to avoid sqrts. To make amends, I offer
the following excellent link and some code that should work.

http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/algorithms-faq/faq.html

From the ACM graphics gems code pool (see above FAQ for link).

/* 
A Fast 2D Point-On-Line Test
by Alan Paeth
from "Graphics Gems", Academic Press, 1990
*/

#include "GraphicsGems.h"

int PntOnLine(px,py,qx,qy,tx,ty)
   int px, py, qx, qy, tx, ty;
   {
/*
 * given a line through P:(px,py) Q:(qx,qy) and T:(tx,ty)
 * return 0 if T is not on the line through      <--P--Q-->
 *        1 if T is on the open ray ending at P: <--P
 *        2 if T is on the closed interior along:   P--Q
 *        3 if T is on the open ray beginning at Q:    Q-->
 *
 * Example: consider the line P = (3,2), Q = (17,7). A plot
 * of the test points T(x,y) (with 0 mapped onto '.') yields:
 *
 *     8| . . . . . . . . . . . . . . . . . 3 3
 *  Y  7| . . . . . . . . . . . . . . 2 2 Q 3 3    Q = 2
 *     6| . . . . . . . . . . . 2 2 2 2 2 . . .
 *  a  5| . . . . . . . . 2 2 2 2 2 2 . . . . .
 *  x  4| . . . . . 2 2 2 2 2 2 . . . . . . . .
 *  i  3| . . . 2 2 2 2 2 . . . . . . . . . . .
 *  s  2| 1 1 P 2 2 . . . . . . . . . . . . . .    P = 2
 *     1| 1 1 . . . . . . . . . . . . . . . . .
 *      +--------------------------------------
 *        1 2 3 4 5 X-axis 10        15      19
 *
 * Point-Line distance is normalized with the Infinity Norm
 * avoiding square-root code and tightening the test vs the
 * Manhattan Norm. All math is done on the field of integers.
 * The latter replaces the initial ">= MAX(...)" test with
 * "> (ABS(qx-px) + ABS(qy-py))" loosening both inequality
 * and norm, yielding a broader target line for selection.
 * The tightest test is employed here for best discrimination
 * in merging collinear (to grid coordinates) vertex chains
 * into a larger, spanning vectors within the Lemming editor.
 */


    if ( ABS((qy-py)*(tx-px)-(ty-py)*(qx-px)) >=
        (MAX(ABS(qx-px), ABS(qy-py)))) return(0);
    if (((qx<px)&&(px<tx)) || ((qy<py)&&(py<ty))) return(1);
    if (((tx<px)&&(px<qx)) || ((ty<py)&&(py<qy))) return(1);
    if (((px<qx)&&(qx<tx)) || ((py<qy)&&(qy<ty))) return(3);
    if (((tx<qx)&&(qx<px)) || ((ty<qy)&&(qy<py))) return(3);
    return(2);
    }

         regards, tom (tburgess AT drao DOT nrc DOT ca)

- Raw text -