Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!pasteur!ucbvax!decwrl!labrea!csli!rustcat
From: rustcat@csli.STANFORD.EDU (Vallury Prabhakar)
Newsgroups: comp.graphics
Subject: Re: polygon enclosing point
Message-ID: <3548@csli.STANFORD.EDU>
Date: 20 Apr 88 21:56:38 GMT
References: <615@ubu.warwick.UUCP> <6196@cit-vax.Caltech.Edu>
Reply-To: rustcat@csli.UUCP (Vallury Prabhakar)
Distribution: comp.graphics
Organization: Yonder, the Apocalyptic Horizons
Lines: 29

In article <6196@cit-vax.Caltech.Edu> flaig@cit-vlsi.UUCP (Charles M. Flaig) writes:

# # In addition, is there a very simple routine I have overlooked for finding
# # whether two line segments intersect.  Mine is not too bad, but I feel sure
# # there must be a blatantly obvious solution I have missed.
# 
# This is probably in any elementary computer graphics text (page 4 in mine).
# Using the the slope-intercept line equation (b=y-mx) we get an intercept at
# y=(b2-b1)/(m1-m2) and x=(b2m1-b1m2)/(m1-m2) if one exists.  Then check if
# this point is within the boundaries of the line segments.  Using the general
# line equation (rx+sy+t=0) we get an intercept at x=(s1t2-s2t1)/(s2r1-s1r2)
# and y=(t1r2-t2r1)/(s2r1-s1r2).

Depends on how many lines you're going to be checking for.  If it is just
two lines in your entire code, then maybe the above is okay.  But it's hardly
the most efficient when there are a large number of lines involved.  It is
pretty standard practice to perform boxing tests on the line segments before
actually solving for intersections.

The slope-intercept equation will choke over vertical lines and you'll have
to have a routine to check whether either of the two segments are vertical
or not.  A better way might to be represent the two line segments in the
parametric form and solve for the values of the parameters.  The intersection
is valid only if they lie within 0.0 and 1.0.  

I don't know if your "elementary computer graphics text" has these things in
it, but any basic geometry book will.  Look up "A programmer's geometry" by
Adrian Bowyer and John Woodwark (Butterworths).

							-- Vallury