pssw@warwick.UUCP (P S Swanson) (04/18/88)
I am writing an asteroids game, and need an algorithm to say whether a single point is enclosed by, or lies on the perimeter of a closed polygon, defined by an unspecified number of line segments. Any offers ? 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. NUFC OK !
scott@applix.UUCP (Scott Evernden) (04/20/88)
In article <615@ubu.warwick.UUCP> pssw@diamond.UUCP (P S Swanson) writes: > ... need an algorithm to say whether a single >point is enclosed by, or lies on the perimeter of a closed polygon, ... Oooh nooo. not again!? -scott
flaig@cit-vlsi.Caltech.Edu (Charles M. Flaig) (04/20/88)
In article <615@ubu.warwick.UUCP> pssw@diamond.UUCP (P S Swanson) writes: >I am writing an asteroids game, and need an algorithm to say whether a single >point is enclosed by, or lies on the perimeter of a closed polygon, defined by >an unspecified number of line segments. Any offers ? Whimper.... I assume you don't follow this group regularly if you are asking this question. It has been covered *repeatedly* and is well past the satura- tion point. Does your site really flush old articles that quickly? Some very good references and suggestions were repeatedly posted. If you no longer have them at your site, you can try asking if anyone in your area saved them or knows of any references. I wouldn't touch this question with a 10-foot pole (and hope no one else does, either...). >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). I take no responsibility for typos, and disclaim any knowledge of this response. ______________________________________________________________________________ ___ , , ,;,;;;, / Y /| /| Charles Flaig ;/@-@\; | |/ __, ,__ |/ flaig@csvax.caltech.edu | ^ | | /^\ / | | | / /\ /\ \=/ \____/| \_/|_/\_/ \_/ \_\/_/_/_/ "What, you think they PAY me for this?"
cjp@antique.UUCP (Charles Poirier) (04/21/88)
In article <6196@cit-vax.Caltech.Edu> flaig@cit-vlsi.UUCP (Charles M. Flaig) writes: >Whimper.... I assume you don't follow this group regularly if you are asking >this question. It has been covered *repeatedly* and is well past the satura- >tion point. Does your site really flush old articles that quickly? Hey man, wanna chill out? Some sites really do have to flush articles two weeks old. Since the recurrence period of the point-inside-polygon question is a good three weeks, ... you get the picture. Grin and bear it. Reply to such questions by email if possible. -- Charles Poirier (decvax,ihnp4,attmail)!vax135!cjp "Docking complete... Docking complete... Docking complete..."
richard@gryphon.CTS.COM (Richard Sexton) (04/21/88)
In article <690@applix.UUCP> scott@applix.UUCP (Scott Evernden) writes: >In article <615@ubu.warwick.UUCP> pssw@diamond.UUCP (P S Swanson) writes: >> ... need an algorithm to say whether a single >>point is enclosed by, or lies on the perimeter of a closed polygon, ... > >Oooh nooo. not again!? > >-scott Oh yes. Why not ? it's been at least 30 days. What more convincing argument for comp.graphics.newusers could you ask for ? If this poor fu... uhh, soul was able to look in a permanent posting at his site, and get his answer, he'd say to himself "gee, what a neat bunch of people, thay've magically put all the answers to the questions i was about to ask RIGHT HERE on mysite. Instead, he'll probably get all indignent and wonder why his pefectly valid question was met with all the appeal of squid juice. Hang in there folks, in about a day or two there's gonna be a "where can i get references to ray tracing" posting. I can feel it in my bones. -- Five tacos, one taco burger. Do you know where the American Dream is ? richard@gryphon.CTS.COM rutgers!marque!gryphon!richard
rustcat@csli.STANFORD.EDU (Vallury Prabhakar) (04/21/88)
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